Equivalence and Inclusion Problem for Strongly Unambiguous Buchi Automata

Nicolas Bousquet1

Description

Niveau: Supérieur, Doctorat, Bac+8
Equivalence and Inclusion Problem for Strongly Unambiguous Buchi Automata Nicolas Bousquet1 and Christof Loding2 1 ENS Chachan, France 2 RWTH Aachen, Informatik 7, 52056 Aachen, Germany Abstract. We consider the inclusion and equivalence problem for un- ambiguous Buchi automata. We show that for a strong version of unam- biguity introduced by Carton and Michel these two problems are solvable in polynomial time. We generalize this to Buchi automata with a fixed finite degree of ambiguity in the strong sense. We also discuss the prob- lems that arise when considering the decision problems for the standard notion of ambiguity for Buchi automata. 1 Introduction The model of unambiguous automata is located between deterministic and non- deterministic automata. An unambiguous automaton is a nondeterministic au- tomaton such that each input that is accepted has a unique accepting run. The concept of unambiguity also occurs in other areas of theoretical computer sci- ence, for example in complexity theory. The problems solvable in polynomial time by unambiguous (nondeterministic) Turing machines are collected in the subclass UP (Unambiguous Polynomial time) of NP [1]. There are two aspects in the study of unambiguous automata: expressiveness and computational complexity. Concerning expressiveness, because of the well- known equivalence between deterministic and nondeterministic finite automata over finite words and trees, unambiguous automata can recognize all the regular languages over these two domains.

• every ?-regular


• equivalence problem


• np-complete


• over finite


• finite words


• language can


• buchi automata


• strongly unambiguous


• can reach

Sujets

• NP-complete
• Büchi automaton

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 36
• Langue: English

Extrait

EquivalenceandInclusionProblemforStrongly UnambiguousBu¨chiAutomata NicolasBousquet 1 andChristofLo¨ding 2 1 ENSChachan,France [e-mail] 2 RWTHAachen,Informatik7,52056Aachen,Germany [e-mail] Abstract.Weconsidertheinclusionandequivalenceproblemforun- ambiguousBu¨chiautomata.Weshowthatforastrongversionofunam- biguityintroducedbyCartonandMichelthesetwoproblemsaresolvable inpolynomialtime.WegeneralizethistoBu¨chiautomatawithafixed finitedegreeofambiguityinthestrongsense.Wealsodiscusstheprob- lemsthatarisewhenconsideringthedecisionproblemsforthestandard notionofambiguityforBu¨chiautomata. 1Introduction Themodelofunambiguousautomataislocatedbetweendeterministicandnon- deterministicautomata.Anunambiguousautomatonisanondeterministicau- tomatonsuchthateachinputthatisacceptedhasauniqueacceptingrun.The conceptofunambiguityalsooccursinotherareasoftheoreticalcomputersci- ence,forexampleincomplexitytheory.Theproblemssolvableinpolynomial timebyunambiguous(nondeterministic)Turingmachinesarecollectedinthe subclassUP(UnambiguousPolynomialtime)ofNP[1]. Therearetwoaspectsinthestudyofunambiguousautomata:expressiveness andcomputationalcomplexity.Concerningexpressiveness,becauseofthewell- knownequivalencebetweendeterministicandnondeterministicfiniteautomata overfinitewordsandtrees,unambiguousautomatacanrecognizealltheregular languagesoverthesetwodomains.Forautomataoverω-wordsitisknownthat deterministicBu¨chiautomataarestrictlylessexpressivethannondeterministic ones[2].However,Arnoldshowedthatalltheω-regularlanguagescanberecog- nizedbyanunambiguousBu¨chiautomaton[3].Forautomataoverω-trees,the classofunambiguousautomataisnotasexpressiveastheclassoffullnondeter- ministictreeautomata(withstandardacceptanceconditionslikeparity,Rabin orMuller)[4,5]. AninterestingsubclassoftheclassofunambiguousBu¨chiautomataiscon- sideredbyCartonandMichel[6]:Theirdefinitionrequiresthatforeachinput (acceptedornot)thereisauniquerunpassinginfinitelyoftenthroughafinal state(whetherfromaninitialstateornot).Thus,aninfinitewordisaccepted iftheinitialstateisthefirststateofthepathpassinginfinitelyoftenthrough