Asynchronous Games over Tree Architectures

DOI10.1007/978-3-642-39212-2_26MaRDI QIDQ5327440zbMATH OpenOpenAlexFDO

Authors Blaise Genest, Hugo Gimbert, Anca Muscholl, Igor Walukiewicz

Publication date 7 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.0077

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Games involving graphs (91A43) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: We consider the task of controlling in a distributed way a Zielonka asynchronous automaton. Every process of a controller has access to its causal past to determine the next set of actions it proposes to play. An action can be played only if every process controlling this action proposes to play it. We consider reachability objectives: every process should reach its set of final states. We show that this control problem is decidable for tree architectures, where every process can communicate with its parent, its children, and with the environment. The complexity of our algorithm is l-fold exponential with l being the height of the tree representing the architecture. We show that this is unavoidable by showing that even for three processes the problem is EXPTIME-complete, and that it is non-elementary in general.

Recommendations

• Asynchronous algorithms in non-cooperative games
• Fundamentals of Computation Theory
• On asynchronously repeated games
• Asynchronous networked aggregative games
• On parallel evaluation of game trees
• Asynchronous congestion games
• Concurrent structures in game semantics
• On asynchronous tree automata
• Node-consistent core for games played over event trees
• Translating asynchronous games for distributed synthesis

Cited in

(24)

• On the control of asynchronous automata
• Synthesis in presence of dynamic links
• LATIN 2004: Theoretical Informatics
• Asynchronous games. II: The true concurrency of innocence
• Automated synthesis of distributed controllers
• Canonical representations for direct generation of strategies in high-level Petri games
• Solving high-level Petri games
• scientific article; zbMATH DE number 7649934 (Why is no real title available?)
• Bounded synthesis for Petri games
• Synchronization of Bernoulli sequences on shared letters
• High-level representation of benchmark families for Petri games
• Distributed synthesis in continuous time
• scientific article; zbMATH DE number 7438566 (Why is no real title available?)
• Fundamentals of Computation Theory
• The synthesis problem for repeatedly communicating Petri games
• Distributed Asynchronous Games With Causal Memory are Undecidable
• Distributed controller synthesis for deadlock avoidance
• scientific article; zbMATH DE number 7455739 (Why is no real title available?)
• Asynchronous transition system games for two processes and their analysis
• Efficient trace encodings of bounded synthesis for asynchronous distributed systems
• Automated synthesis: a distributed viewpoint
• On Distributed Monitoring and Synthesis
• Petri games: synthesis of distributed systems with causal memory
• (Un)decidability bounds of the synthesis problem for Petri games

This page was built for publication: Asynchronous Games over Tree Architectures

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