Content deleted Content added
m →History: clean up, replaced: xxx.lanl.gov → www.arxiv.org |
Citation bot (talk | contribs) m Alter: issue. Add: issue, arxiv, chapter-url. Removed or converted URL. Removed parameters. Formatted dashes. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Activated by User:Headbomb | via #UCB_webform |
||
Line 4:
'''Answer set programming''' ('''ASP''') is a form of [[declarative programming]] oriented towards difficult (primarily [[NP-hard]]) [[search algorithm|search problems]]. It is based on the [[stable model semantics|stable model]] (answer set) semantics of [[logic programming]]. In ASP, search problems are reduced to computing stable models, and ''answer set solvers''—programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the [[DPLL algorithm]] and, in principle, it always terminates (unlike [[Prolog]] query evaluation, which may lead to an [[infinite loop]]).
In a more general sense, ASP includes all applications of answer sets to [[knowledge representation]]<ref>{{cite book |first=Chitta |last=Baral |title=Knowledge Representation, Reasoning and Declarative Problem Solving |url=https://books.google.com/books?id=iTS4ZdEpGZQC |year=2003 |publisher=Cambridge University Press |isbn=978-0-521-81802-5}}</ref><ref>{{cite book |first=Michael |last=Gelfond |chapter=Answer sets |editor1-first=Frank |editor1-last=van Harmelen |editor2-first=Vladimir |editor2-last=Lifschitz |editor3-first=Bruce |editor3-last=Porter |title=Handbook of Knowledge Representation |chapter-url=https://books.google.com/books?id=xwBDylHhJhYC&pg=PA285 |year=2008 |publisher=Elsevier |isbn=978-0-08-055702-1 |pages=285–316 }} [http://www.depts.ttu.edu/cs/research/krlab/pdfs/papers/gel07b.pdf as PDF] {{Webarchive|url=https://web.archive.org/web/20160303231241/http://www.depts.ttu.edu/cs/research/krlab/pdfs/papers/gel07b.pdf |date=2016-03-03 }}</ref> and the use of Prolog-style query evaluation for solving problems arising in these applications.
==History==
Line 13:
Soininen and Niemelä<ref>{{citation |first1=T. |last1=Soininen |first2=I. |last2=Niemelä |title=Formalizing configuration knowledge using rules with choices |number=TKO-B142 |institution=Laboratory of Information Processing Science, Helsinki University of Technology |year=1998 |url=http://www.tcs.hut.fi/~ini/papers/sn-faanmr98.ps.gz |format=Postscript}}</ref>
applied what is now known as answer set programming to the problem of product configuration. The use of answer set solvers for search was identified as a new programming paradigm by [[Victor W. Marek|Marek]] and Truszczyński in a paper that appeared in a 25-year perspective on the logic programming paradigm published in 1999 <ref>
{{cite book |first1=V. |last1=Marek |first2=M. |last2=Truszczyński |chapter=Stable models and an alternative logic programming paradigm |editor-first=Krzysztof R. |editor-last=Apt |title=The Logic programming paradigm: a 25-year perspective |url=https://books.google.com/books?id=GIhQAAAAMAAJ |year=1999 |publisher=Springer |isbn=978-3-540-65463-6
and in [Niemelä 1999].<ref>{{cite journal |first=I. |last=Niemelä |title=Logic programs with stable model semantics as a constraint programming paradigm |journal=Annals of Mathematics and Artificial Intelligence |volume=25 |issue=3/4 |pages=241–273 |year=1999 |doi=10.1023/A:1018930122475 |url=http://users.ics.aalto.fi/ini/papers/lp-csp-long.ps.gz |format=Postscript,gzipped}}</ref>
Indeed, the new terminology of "answer set" instead of "stable model" was first proposed by Lifschitz<ref>{{cite journal |first=V. |last=Lifschitz |title=Action Languages, Answer Sets, and Planning |year=1999}} In {{harvnb|Apt|1999|pp=357–374}}</ref> in a paper appearing in the same retrospective volume as the Marek-Truszczynski paper.
Line 34:
</source>
says: choose arbitrarily which of the atoms <math>p,q,r</math> to include in the stable model. The lparse program that contains this choice rule and no other rules has 8 stable models—arbitrary subsets of <math>\{p,q,r\}</math>. The definition of a stable model was generalized to programs with choice rules.<ref>{{cite book |first1=I. |last1=Niemelä |first2=P. |last2=Simons |first3=T. |last3=Soinenen |chapter=Stable model semantics of weight constraint rules |editor1-first=Michael |editor1-last=Gelfond |editor2-first=Nicole |editor2-last=Leone |editor3-first=Gerald |editor3-last=Pfeifer |title=Logic Programming and Nonmonotonic Reasoning: 5th International Conference, LPNMR '99, El Paso, Texas, USA, December 2–4, 1999 Proceedings |chapterurl=https://books.google.com/books?id=Abj-OpFeDjQC&pg=PA317 |year=2000 |publisher=Springer |isbn=978-3-540-66749-0 |pages=317–331 |series=Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence |volume=1730}} [http://www.tcs.hut.fi/~ini/papers/nss-lpnmr99-www.ps.gz as Postscript]</ref> Choice rules can be treated also as abbreviations for [[Stable model semantics#Stable models of a set of propositional formulas|propositional formulas under the stable model semantics]].<ref>{{cite journal |first1=P. |last1=Ferraris |first2=V. |last2=Lifschitz |title=Weight constraints as nested expressions |journal=Theory and Practice of Logic Programming |volume=5 |issue=
:<math>(p\lor\neg p)\land(q\lor\neg q)\land(r\lor\neg r).</math>
|