Publications
Publications › References ›
2010
Conference papers
Partial order reduction for model checking interleaved multi-agent systems
[LPQ10]
A. Lomuscio, W. Penczek and H. Qu.
Partial order reduction for model checking interleaved multi-agent systems.
In Proc. the 9th International Conference on Autonomous Agents and Multi-Agent systems (AAMAS'10), IFAAMAS. To appear.
May 2010.
- Search for this paper
- Google · Google Scholar
Abstract
We investigate partial order reduction for model checking
multi-agent systems by focusing on interleaved interpreted
systems. These are a particular class of interpreted systems, a
mainstream MAS formalism, in which only one action at the time is
performed in the system.
We present a notion of stuttering-equivalence, and prove the
semantical equivalence of stuttering-equivalent traces with respect
to linear and branching time temporal logics for knowledge without
the next operator. We give algorithms to reduce the size of the
models before the model checking step and show preservation
properties. We evaluate the technique by discussing implementations
and the experimental results obtained against well-known examples in
the MAS literature.