Logo image
Se connecter
Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata
Acte de colloque

Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata

Christof Loeding et Nicolas Bousquet
Lecture Notes in Computer Science, Vol.6031, pp.118-129
Lecture Notes in Computer Science
LATA'10: Language and Automata Theory and Applications (Germany)
2010

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.

Fichiers et liens (1)

url
Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Logo image