The computational complexity of scenario-based agent verification and design

DOI10.1016/J.JAL.2005.12.013MaRDI QIDQ2372186zbMATH OpenOpenAlexFDO

Authors Yves Bontemps, Pierre Yves Schobbens

Publication date 25 July 2007

Published in Journal of Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jal.2005.12.013

zbMATH Keywords

AUMLcomputational complexitylive sequence chartsmodel checkingscenariosstrategiessynthesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) General topics in artificial intelligence (68T01)

Recommendations

• On complexity of verification of interacting agents' behavior
• Systems of agents controlled by logical programs: complexity of verification
• Verifying systems of resource-bounded agents
• Specification and Verification of Multi-Agent Systems
• Progression and verification of situation calculus agents with bounded beliefs
• The complexity of agent design problems: Determinism and history dependence

Cites work

• Alternating Tree Automata and Parity Games
• Alternation
• Automata-theoretic techniques for modal logics of programs
• scientific article; zbMATH DE number 4110131 (Why is no real title available?)
• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 4124989 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1142326 (Why is no real title available?)
• scientific article; zbMATH DE number 1149416 (Why is no real title available?)
• scientific article; zbMATH DE number 1950545 (Why is no real title available?)
• scientific article; zbMATH DE number 1927560 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2088153 (Why is no real title available?)
• scientific article; zbMATH DE number 2112979 (Why is no real title available?)
• scientific article; zbMATH DE number 3189696 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• LSCs: Breathing life into message sequence charts
• Modular refinement of hierarchic reactive machines
• On the complexity of verifying concurrent transition systems
• Relationships between nondeterministic and deterministic tape complexities
• Solving Sequential Conditions by Finite-State Strategies
• Statecharts: a visual formalism for complex systems
• SYNTHESIZING STATE-BASED OBJECT SYSTEMS FROM LSC SPECIFICATIONS
• Temporal logic can be more expressive
• The complexity of achievement and maintenance problems in agent-based systems
• The complexity of propositional linear temporal logics
• Undecidable problems of decentralized observation and control on regular languages

Cited in

(3)

• Systems of agents controlled by logical programs: complexity of verification
• Some Results on the Expressive Power and Complexity of LSCs
• Scenario-based verification of real-time systems using UPPAAL

Describes a project that uses

Uses Software

• AgentSpeak
• SPIN

This page was built for publication: The computational complexity of scenario-based agent verification and design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2372186)