Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata

Résumé

We consider the inclusion and equivalence problem for unambiguous Büchi automata. We show that for a strong version of unambiguity introduced by Carton and Michel these two problems are solvable in polynomial time. We generalize this to Büchi automata with a fixed finite degree of ambiguity in the strong sense. We also discuss the problems that arise when considering the decision problems for the standard notion of ambiguity for Büchi automata.
Fichier non déposé

Dates et versions

lirmm-00741988 , version 1 (15-10-2012)

Identifiants

  • HAL Id : lirmm-00741988 , version 1

Citer

Christof Loeding, Nicolas Bousquet. Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata. LATA'10: Language and Automata Theory and Applications, Germany. pp.118-129. ⟨lirmm-00741988⟩
98 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More