Abstract
In Part I of this series of papers, we developed a language called Agent Programs for defining the operational behavior of software agents and defined a set of successively more satisfying (epistemically) semantics for such agent programs. In Part II of this series of papers, we study the computation price to be paid (in terms of complexity) for these epistemic desiderata. In particular, we develop algorithms for the above semantics, and describe results on their computational complexity. We show that (surprisingly) the reasonable status set semantics is the easiest to compute of the semantics proposed.
Original language | English (US) |
---|---|
Pages (from-to) | 257-307 |
Number of pages | 51 |
Journal | Artificial Intelligence |
Volume | 108 |
Issue number | 1 |
DOIs | |
State | Published - Mar 31 1999 |
Externally published | Yes |
Funding
This work was supported by the Army Research Office under Grants DAAH-04-95-10174, DAAH-04-96-10297, and DAAH04-96-1-0398, by the Army Research Laboratory under contract number DAAL01-97-K0135, by an NSF Young Investigator award IRI-93-57756, by a DAAD grant and by the Austrian Science Fund Project N Z29-INF.
ASJC Scopus subject areas
- Language and Linguistics
- Linguistics and Language
- Artificial Intelligence