Content deleted Content added
No edit summary |
Rescuing 3 sources and tagging 0 as dead. #IABot (v2.0beta14) |
||
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 |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 18:
==Answer set programming language AnsProlog==
[http://www.tcs.hut.fi/Software/smodels/lparse.ps Lparse] is the name of the program that was originally created as a [[Symbol grounding|grounding]] tool (front-end) for the answer set solver [http://www.tcs.hut.fi/Software/smodels/ smodels]. The language that Lparse accepts is now commonly called AnsProlog*,<ref>{{Cite thesis |type=Ph.D. |title=Superoptimisation: Provably Optimal Code Generation using Answer Set Programming |url=http://opus.bath.ac.uk/20352/1/UnivBath_PhD_2009_T_Crick.pdf |last=Crick |first=Tom |year=2009 |publisher=University of Bath |docket=20352 |accessdate=2011-05-27 |archiveurl=https://web.archive.org/web/20160304035502/http://opus.bath.ac.uk/20352/1/UnivBath_PhD_2009_T_Crick.pdf |archivedate=2016-03-04 |deadurl=yes }}</ref> short for ''Answer Set Programming in Logic''.<ref>{{cite web |author=Rogelio Davila |title=AnsProlog, an overview |url=http://www.rogeliodavila.com.mx/Programacion%20Logica/PL%20Notas/AnsProlog%20Overview.ppt |format=PowerPoint}}</ref> It is now used in the same way in many other answer set solvers, including [http://assat.cs.ust.hk/ assat], [http://www.cs.uni-potsdam.de/clasp/ clasp], [http://www.cs.utexas.edu/users/tag/cmodels/ cmodels], [http://www.tcs.hut.fi/Software/gnt/ gNt], [http://www.cs.uni-potsdam.de/nomore/ nomore++] and [http://www.cs.uky.edu/ai/pbmodels/ pbmodels]. ([http://www.dbai.tuwien.ac.at/proj/dlv/ dlv] is an exception; the syntax of ASP programs written for dlv is somewhat different.)
An AnsProlog program consists of rules of the form
Line 216:
===Dependency parsing===
In [[natural language processing]], [[parsing|dependency-based parsing]] can be formulated as an ASP problem.<ref>
The following code parses the Latin sentence '''Puella pulchra in villa linguam latinam discit''' "the pretty girl is learning Latin in the villa".
The syntax tree is expressed by the ''arc'' predicates which represent the dependencies between the words of the sentence.
| |||