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) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Games involving graphs (91A43)

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

(25)

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

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)