We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Hierarchical information and the synthesis of distributed strategies.
- Authors
Berwanger, Dietmar; Mathew, Anup Basil; van den Bogaard, Marie
- Abstract
Infinite games with imperfect information are known to be undecidable unless the information flow is severely restricted. One fundamental decidable case occurs when there is a total ordering among players, such that each player has access to all the information that the following ones receive. In this paper we consider variations of this hierarchy principle for synchronous games with perfect recall, and identify new decidable classes for which the distributed synthesis problem is solvable with finite-state strategies. In particular, we show that decidability is maintained when the information hierarchy may change along the play, or when transient phases without hierarchical information are allowed. Finally, we interpret our result in terms of distributed system architectures.
- Subjects
INFINITY (Mathematics); SYNCHRONOUS data transmission systems; DATA transmission systems; DECIDABILITY (Mathematical logic); MATHEMATICAL logic
- Publication
Acta Informatica, 2018, Vol 55, Issue 8, p669
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-017-0306-5