The complexity of the language A

Paolo Liberatore

Electronic Transactions on Artificial Intelligence

In this paper we anliyze the complexity of the language A, proposed by 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.


 @article{libe-97-b,
 title = {The complexity of the language A},
 year = {1997},
 author = {Liberatore, Paolo},
 journal = {Electronic Transactions on Artificial Intelligence},
 pages = {13--38},
 number = {1--3},
 volume = {1},
 note = {Available at http://www.ep.liu.se/ej/etai/1997/002/},
 }
 
HTTP download.