Index Problems for Game Automata

For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a nondeterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the nondeterministic, alternating, and weak Rab...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on computational logic 2016-11, Vol.17 (4), p.1-38
Main Authors: Facchini, Alessandro, Murlak, Filip, Skrzypczak, Michał
Format: Article
Language:English
Subjects:
Closures
Computation
Games
Hierarchies
Logic
Parity
Priorities
Trees
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a nondeterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the nondeterministic, alternating, and weak Rabin-Mostowski index problems. Whether they can be answered effectively is a long-standing open problem, solved so far only for languages recognizable by deterministic automata (the alternating variant trivializes). We investigate a wider class of regular languages, recognizable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. Game automata are known to recognize languages arbitrarily high in the alternating Rabin-Mostowski index hierarchy; that is, the alternating index problem does not trivialize anymore. Our main contribution is that all three index problems are decidable for languages recognizable by game automata. Additionally, we show that it is decidable whether a given regular language can be recognized by a game automaton.
ISSN:1529-3785
1557-945X
DOI:10.1145/2946800