Half-Positional Deterministic Büchi Automata

Zero-sum games on graphs are a natural framework used as a model in multiple areas of theoretical computer science, such as the field of reactive synthesis. A central class of specifications for these games is the one of omega-regular languages, which encompasses, e. g. , linear-time temporal logic specifications. Part of its interest is due to the landmark result that finite-state machines are sufficient to implement optimal strategies in omega-regular games. Surprisingly, the question of characterizing the precise size of the finite-state machines needed for optimal strategies in omega-regular games is not yet settled. Understanding when small strategies suffice has theoretical and practical significance. We set out to provide a novel piece in this puzzle by characterizing the languages recognizable by deterministic Büchi automata (DBA) that are half-positional, i. e. , for which the protagonist needs no memory to play optimally. Our characterization consists of three conditions, two of which pertaining to more general objectives and one of which being specifically suited to handle DBA. Our characterization may also help study the decidability of the half-positionality of languages recognized by DBA. This talk is based on ongoing joint work with Patricia Bouyer, Antonio Casares, and Mickael Randour.

Authors

• Pierre Vandenhove CNRS, LaBRI, Université de Bordeaux, France

Keywords

No keywords are indexed for this paper.