Heterogeneous active agents, II: algorithms and complexity

Thomas Eiter; V. S. Subrahmanian

doi:10.1016/S0004-3702(99)00006-5

Heterogeneous active agents, II: algorithms and complexity

Thomas Eiter, V. S. Subrahmanian

Research output: Contribution to journal › Article › peer-review

22 Scopus citations

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	https://doi.org/10.1016/S0004-3702(99)00006-5
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

Access to Document

10.1016/S0004-3702(99)00006-5

Cite this

@article{6d7dbfb5fe7f4d26b97ec139c35f95b2,

title = "Heterogeneous active agents, II: algorithms and complexity",

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.",

author = "Thomas Eiter and Subrahmanian, {V. S.}",

note = "Funding Information: 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.",

year = "1999",

month = mar,

day = "31",

doi = "10.1016/S0004-3702(99)00006-5",

language = "English (US)",

volume = "108",

pages = "257--307",

journal = "Artificial Intelligence",

issn = "0004-3702",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Heterogeneous active agents, II

T2 - algorithms and complexity

AU - Eiter, Thomas

AU - Subrahmanian, V. S.

N1 - Funding Information: 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.

PY - 1999/3/31

Y1 - 1999/3/31

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0033620272&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033620272&partnerID=8YFLogxK

U2 - 10.1016/S0004-3702(99)00006-5

DO - 10.1016/S0004-3702(99)00006-5

M3 - Article

AN - SCOPUS:0033620272

SN - 0004-3702

VL - 108

SP - 257

EP - 307

JO - Artificial Intelligence

JF - Artificial Intelligence

IS - 1

ER -

Heterogeneous active agents, II: algorithms and complexity

Abstract

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this