Answer Set Programming

Answer set programming (ASP) is a programming methodology oriented towards combinatorial search problems. In such a problem, the goal is to find a solution among a large but finite number of possibilities. The idea of ASP came from research on artificial intelligence and computational logic. ASP is a form of declarative programming: an ASP program describes what is counted as a solution to the problem, but does not specify an algorithm for solving it. Search is performed by sophisticated software systems called answer set solvers. Combinatorial search problems often arise in science and technology, and ASP has found applications in diverse areas—in historical linguistic, in bioinformatics, in robotics, in space exploration, in oil and gas industry, and many others. The importance of this programming method was recognized by the Association for the Advancement of Artificial Intelligence in 2016, when __AI Magazine__ published a special issue on answer set programming. The book will introduce the reader to the theory and practice of ASP. It will describe the input language of the answer set solver CLINGO, which was designed at the University of Potsdam in Germany and is used today by ASP programmers in many countries. It will include numerous examples of ASP programs and present the mathematical theory that ASP is based on. There will be many exercises with complete solutions. Preface......Page 6 Contents......Page 8 1.1 Declarative Programming......Page 11 1.2 Logic Programming......Page 12 1.4 Bibliographical and Historical Remarks......Page 14 2 Input Language of clingo......Page 16 2.1 Rules......Page 17 2.2 Directives and Comments......Page 19 2.3 Arithmetic......Page 22 2.4 Definitions......Page 24 2.5 Choice Rules......Page 28 2.6 Variables in a Choice Rule......Page 31 2.7 Constraints......Page 32 2.8 Anonymous Variables......Page 35 2.9 Bibliographical and Historical Remarks......Page 36 3.1 Seating Arrangements......Page 38 3.3 Schur Numbers......Page 41 3.4 Digression on Grounding and Solving......Page 44 3.6 Search in Graphs......Page 46 3.7 Search in Two Dimensions......Page 51 3.8 Partner Units Problem......Page 53 Who Owns the Fish?......Page 54 Filling a Grid with Letters......Page 56 3.10 Bibliographical and Historical Remarks......Page 57 4 Propositional Programs and Minimal Models......Page 60 4.1 Propositional Formulas......Page 61 4.2 Equivalence......Page 63 4.3 Minimal Models......Page 65 4.4 Stable Models of Positive Propositional Programs......Page 67 4.5 Propositional Image of a clingo Program......Page 69 4.6 Values of a Ground Term......Page 72 4.7 More on Propositional Images......Page 74 4.8 Bibliographical and Historical Remarks......Page 77 5.1 Examples......Page 80 5.2 Stable Models of a Propositional Program......Page 82 5.3 Stable Models as Fixpoints......Page 85 5.4 Simplifying Propositional Programs......Page 87 5.5 clingo Programs with Negation......Page 90 5.6 The Law of Excluded Middle......Page 92 5.7 clingo Programs with Choice......Page 95 5.8 Theorem on Constraints......Page 97 5.9 Bibliographical and Historical Remarks......Page 98 6.1 Strong Equivalence......Page 101 6.2 Theorem on Strong Equivalence......Page 106 6.3 Program Completion......Page 107 6.4 Theorem on Completion......Page 111 6.5 Bibliographical and Historical Remarks......Page 114 7.1 Counting......Page 116 7.2 Summation......Page 119 7.3 Maximum and Minimum......Page 123 7.4 Optimization......Page 124 7.5 Symbolic Functions......Page 129 7.6 Classical Negation......Page 131 7.7 Bibliographical and Historical Remarks......Page 133 8.1 Example: The Blocks World......Page 135 8.2 Transition Diagrams......Page 137 8.3 Time......Page 138 8.4 Effects of Actions......Page 140 8.5 Nonexecutable Actions......Page 143 8.6 Prediction......Page 144 8.7 Planning......Page 146 8.8 Concurrency......Page 150 8.9 Bibliographical and Historical Remarks......Page 151 9 Conclusion......Page 153 A Answers to Exercises......Page 154 Listings......Page 184 Bibliography......Page 186 Index......Page 192 Answer set programming (ASP) is a programming methodology oriented towards combinatorial search problems. In such a problem, the goal is to find a solution among a large but finite number of possibilities. The idea of ASP came from research on artificial intelligence and computational logic. ASP is a form of declarative programming: an ASP program describes what is counted as a solution to the problem, but does not specify an algorithm for solving it. Search is performed by sophisticated software systems called answer set solvers. Combinatorial search problems often arise in science and technology, and ASP has found applications in diverse areas?in historical linguistic, in bioinformatics, in robotics, in space exploration, in oil and gas industry, and many others. The importance of this programming method was recognized by the Association for the Advancement of Artificial Intelligence in 2016, when AI Magazine published a special issue on answer set programming. The book will introduce the reader to the theory and practice of ASP. It will describe the input language of the answer set solver CLINGO, which was designed at the University of Potsdam in Germany and is used today by ASP programmers in many countries. It will include numerous examples of ASP programs and present the mathematical theory that ASP is based on. There will be many exercises with complete solutions.--Back cover About the authorsAnswer set programming (ASP) is a programming methodology oriented towards combinatorial search problems. In such a problem, the goal is to find a solution among a large but finite number of possibilities. The idea of ASP came from research on artificial intelligence and computational logic. ASP is a form of declarative programming: an ASP program describes what is counted as a solution to the problem, but does not specify an algorithm for solving it. Search is performed by sophisticated software systems called answer set solvers. Combinatorial search problems often arise in science and technology, and ASP has found applications in diverse areas-in historical linguistic, in bioinformatics, in robotics, in space exploration, in oil and gas industry, and many others. The importance of this programming method was recognized by the Association for the Advancement of Artificial Intelligence in 2016, when AI Magazine published a special issue on answer set programming. The book introduces the reader to the theory and practice of ASP. It describes the input language of the answer set solver CLINGO, which was designed at the University of Potsdam in Germany and is used today by ASP programmers in many countries. It includes numerous examples of ASP programs and present the mathematical theory that ASP is based on. There are many exercises with complete solutions