Büchi Good-for-Games Automata Are Efficiently Recognizable - Université Sorbonne Paris Cité Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Büchi Good-for-Games Automata Are Efficiently Recognizable

Résumé

Good-for-Games (GFG) automata offer a compromise between deterministic and nondetermin-istic automata. They can resolve nondeterministic choices in a step-by-step fashion, without needing any information about the remaining suffix of the word. These automata can be used to solve games with ω-regular conditions, and in particular were introduced as a tool to solve Church's synthesis problem. We focus here on the problem of recognizing Büchi GFG automata, that we call Büchi GFGness problem: given a nondeterministic Büchi automaton, is it GFG? We show that this problem can be decided in P, and more precisely in O(n^4 m^2 |Σ|^2) , where n is the number of states, m the number of transitions and |Σ| is the size of the alphabet. We conjecture that a very similar algorithm solves the problem in polynomial time for any fixed parity acceptance condition.
Fichier principal
Vignette du fichier
tokengfg.pdf (305.51 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01910632 , version 1 (01-11-2018)

Identifiants

Citer

Marc Bagnol, Denis Kuperberg. Büchi Good-for-Games Automata Are Efficiently Recognizable. 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), Dec 2018, Ahmedabad, India. pp.16, ⟨10.4230/LIPIcs.FSTTCS.2018.16⟩. ⟨hal-01910632⟩
110 Consultations
155 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More