𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of achievement and maintenance problems in agent-based systems

✍ Scribed by Iain A. Stewart

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
167 KB
Volume
146
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

✦ Synopsis

We completely classify the computational complexity of the basic achievement and maintenance agent design problems in bounded environments when these problems are parameterized by the number of environment states and the number of agent actions. The different problems are P-complete, NP-complete, co-NP-complete or PSPACE-complete (when they are not trivial). We also consider alternative achievement and maintenance agent design problems by allowing longer runs in environments (that is, our environments are bounded but the bounds are more liberal than was the case previously). Again, we obtain a complete classification but so that the different problems are DEXPTIME-complete, NEXPTIME-complete, co-NEXPTIME-complete or NEXPSPACEcomplete (when they are not trivial).

πŸ“œ SIMILAR VOLUMES

The computational complexity of scenario
The computational complexity of scenario-based agent verification and design
✍ Yves Bontemps; Pierre-Yves Schobbens πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 405 KB

We first advocate that the AUML (Agent Unified Modeling Language) notation, even in its new version, is not precise enough to adequately describe protocols. This problem was long identified by Harel and we propose to follow his solution: extend sequence diagrams with a "prechart", i.e. single out th