| 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:
|