Application problems

We give some example application problems.  Authors of position papers may choose to use any or all of them, or use additional problems.


An earlier example is the British Nationality Act 1981 [3].

A current example is the U.S. Federal Reserve's Regulation W for Transactions between member banks and their affiliates [4].


Countless applications require solving such problems. They often can be viewed using multiple lenses.  For example, a college student needs to plan for a set of courses to take each semester; this can also be viewed as a scheduling problem that assigns different courses to different semesters; it can also be viewed as compliance checking and reasoning against the course and graduation requirements.


Applications often also pose additional challenges like uncertainty, due to lacking information, imprecise information, conflicting information, etc. For example, the exact courses offered for future years may be uncertain, and the graduation requirements might even change.


Central issues to all these problems include:


1. How should the problem be expressed correctly and clearly 

   (in logic or formal specification languages and in natural languages)?


2. How should the problem be solved correctly and efficiently 

   (using any combination of methods and tools)?


These are the core of knowledge representation and reasoning.  Overall, how might a user iterate 1 and 2 above to arrive at desired solutions, taking advantages of all the languages and tools (LLMs and solvers included)?


References

[1] https://en.wikipedia.org/wiki/Travelling_salesman_problem (Last updated July 13, 2024)

[2] https://en.wikipedia.org/wiki/Job-shop_scheduling (Last updated July 16, 2024)

[3] https://www.legislation.gov.uk/ukpga/1981/61/pdfs/ukpga_19810061_en.pdf (Accessed July 31, 2024)

[4] https://www.ecfr.gov/current/title-12/chapter-II/subchapter-A/part-223 (Accessed July 31, 2024)


Acknowledgement

Thanks to Martin Gebser for bringing up the job scheduling problem, to Paul Fodor for reminding about the British Nationality Act 1981, and to Michael Kifer for the problem and reference to Regulation W.