Files: Description File size Format
Fulltext PDF (requires Acrobat Reader)
Fulltext, Revised PDF (requires Acrobat Reader)
Fulltext PostScript (requires a PostScript Reader)
  Fulltext, Revised PostScript (requires a PostScript Reader)
   
Author: Paolo Liberatore
Article title: The Complexity of the Language A
Publ. type: Article
Volume: 2
Article No: 6
Language: English
Abstract [en]: In this paper we analyze the complexity of the language A, proposed in [Gelfond and Lifschitz, 1993] to formalize properties of actions. We prove that the general language is NP complete, thus intractable, and show some tractable (polynomial) subclasses of it. We also show how states that are unreachable affect the semantics of the language.
PDF
Publisher: Linköping University Electronic Press
Year: 1997
Available: 1997-07-04, Revised version 1997-12-18
No. of pages: 22, Revised version 23
Series: Linköping Electronic Articles in Computer and Information Science
ISSN: 1401-9841
REFERENCE TO THIS PAGE:
Liberatore, Paolo (1997). The Complexity of the Language A in Linköping Electronic Articles in Computer and Information Science, Vol. 2. http://www.ep.liu.se/ea/cis/1997/006/. ()