Responsible for this page: David Lawrence, davla@ep.liu.se
Page last updated: 2008-07-17
|
Content
| Files: | Description | File size | Format | |
| Fulltext | 325K | PDF (requires Acrobat Reader) | ||
| Fulltext, Revised | 351K | PDF (requires Acrobat Reader) | ||
| Fulltext | 583K | PostScript (requires a PostScript Reader) | ||
| Fulltext, Revised | 625K | 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. | |||
| 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 | |||
| Checksum PDF: | a81bfa3677f9761666239746b56baa96 /home/ep/www/ea/cis/1997/006/cis97006.pdf (MD5) | |||
| Checksum PDF: | 4827e04df2b0681ca2fb2e0ab667bd16 /home/ep/www/ea/cis/1997/006/cis97006R.pdf (MD5), Revised | |||
| Checksum PS: | 559194c7b0291aff9d4a99ab1a2d7e75 /service/www-ep/docs/ea/cis/1997/006/cis97006.ps (MD5) | |||
| Checksum PS: | 852b91c6ef8aad669bc9753ba9e7d899 /service/www-ep/docs/ea/cis/1997/006/cis97006R.ps (MD5), Revised | |||
| PGP PDF: | PGP | |||
| PGP PDF: | PGP, Reivised | |||
| PGP PS: | PGP | |||
| PGP PS: | PGP, Revised | |||
| Old Checksum: | Checksum (PS) | Information about recalculation of Checksum | |||
| Old Checksum: | Checksum (PS), Revised | Information about recalculation of Checksum | |||
| SPECIAL INFO: | Checksum, PGP and persistence | |||
REFERENCE TO THIS PAGE:
|
||||
Last updated: 2008-07-17