Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata

Christof Loeding 1 Nicolas Bousquet 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Communication dans un congrès
Dediu, Adrian Horia and Fernau, Henning and Martín-Vide, Carlos. LATA'10: Language and Automata Theory and Applications, Germany. Springer, 6031, pp.118-129, 2010, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00741988
Contributeur : Nicolas Bousquet <>
Soumis le : lundi 15 octobre 2012 - 16:08:17
Dernière modification le : jeudi 8 février 2018 - 16:20:02

Identifiants

  • HAL Id : lirmm-00741988, version 1

Collections

Citation

Christof Loeding, Nicolas Bousquet. Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata. Dediu, Adrian Horia and Fernau, Henning and Martín-Vide, Carlos. LATA'10: Language and Automata Theory and Applications, Germany. Springer, 6031, pp.118-129, 2010, Lecture Notes in Computer Science. 〈lirmm-00741988〉

Partager

Métriques

Consultations de la notice

82