Heterogeneous active agents, II: algorithms and complexity

Thomas Eiter, V. S. Subrahmanian

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


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 languageEnglish (US)
Pages (from-to)257-307
Number of pages51
JournalArtificial Intelligence
Issue number1
StatePublished - Mar 31 1999
Externally publishedYes

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Heterogeneous active agents, II: algorithms and complexity'. Together they form a unique fingerprint.

Cite this