|
Abstract:
|
Answer set programming (ASP ) is a form of declarative programming oriented towards difficult combinatorial search problems . It has been applied , for instance , to plan generation and product configuration problems in artificial intelligence and to graph -theoretic problems arising in VLSI design and in historical linguistics . Syntactically , ASP programs look like Prolog programs , but the computational mechanisms used in ASP are different : they are based on the ideas that have led to the development of fast satisfiability solvers for propositional logic . ASP is based on the answer set /stable model semantics for logic problems , originally intended as a specification for query answering in Prolog . From the original definition of 1988 , the semantics was independently extended by different research groups to more expressive kinds of programs , with syntax and semantics that are incompatible with each other . In this thesis we study how the various extensions are related to each other . In order to do that , we propose another definition of an answer set . This definition has three main characteristics : (i ) it is very simple , (ii ) its syntax is more general than the usual concept of a logic program , and (iii ) strong theoretical tools can be used to reason on it . About (ii ) , we show that our syntax allows constructs defined in many other extensions of the answer sets semantics . This fact , together with (iii ) , allows us to study the expressiveness of those constructs . We also compare the answer set semantics with another important formalism developed by Norm McCain and Hudson Turner , called logic . |