Asynchronous Games over Tree Architectures

Details Asynchronous Games over Tree Architectures Asynchronous Games over Tree Architectures

2012-03-31

arxiv.org/abs/1204.0077v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Asynchronous Games over Tree Architectures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asynchronous Games over Tree Architectures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asynchronous Games over Tree Architectures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-655441