Alternating-time stream logic for multi-agent systems

• Published in: Science of computer programming 2010-06, Vol.75 (6), p.398-425
• Main Authors: Klüppelholz, Sascha, Baier, Christel
• Format: Article
• Language: English
• Subjects: Alternating-time temporal logic; Automata; Concurrent games; Coordination; Data streams; Model checking
• ISSN: 0167-6423; 1872-7964
• DOI: 10.1016/j.scico.2009.07.007

Constraint automata have been introduced to provide a uniform operational model for specifying service interfaces of components, the network that yields the glue code for the components, and the operational behavior of the composite system. Constraint automata have been used as the basis for equivalence checking and model checking temporal logical properties. This paper presents a multi-player semantics for constraint automata which serves to reason about controllability, interaction and cooperation facilities of individual components or coalitions of components in a given network. We introduce a temporal logic framework, called alternating-time stream logic, that combines classical features of alternating-time logic ( ATL ) for concurrent games with special operators for specifying regular conditions on the data streams in the network and on the write and read operations at the I/O-ports of the components. Since constraint automata support any kind of synchronous and asynchronous peer-to-peer communication, the resulting game structure is non-standard and requires a series of nontrivial adaptations to the semantics and verification algorithms for classical alternating-time approaches.