12 Pages
English

Equivalence and Inclusion Problem for Strongly Unambiguous Buchi Automata

-

Gain access to the library to view online
Learn more

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


Subjects

Informations

Published by
Reads 36
Language English
EquivalenceandInclusionProblemforStronglyUnambiguousBu¨chiAutomataNicolasBousquet1andChristofLo¨ding21ENSChachan,Francenbousque@dptinfo.ens-cachan.fr2RWTHAachen,Informatik7,52056Aachen,Germanyloeding@cs.rwth-aachen.deAbstract.Weconsidertheinclusionandequivalenceproblemforun-ambiguousBu¨chiautomata.Weshowthatforastrongversionofunam-biguityintroducedbyCartonandMichelthesetwoproblemsaresolvableinpolynomialtime.WegeneralizethistoBu¨chiautomatawithafixedfinitedegreeofambiguityinthestrongsense.Wealsodiscusstheprob-lemsthatarisewhenconsideringthedecisionproblemsforthestandardnotionofambiguityforBu¨chiautomata.1IntroductionThemodelofunambiguousautomataislocatedbetweendeterministicandnon-deterministicautomata.Anunambiguousautomatonisanondeterministicau-tomatonsuchthateachinputthatisacceptedhasauniqueacceptingrun.Theconceptofunambiguityalsooccursinotherareasoftheoreticalcomputersci-ence,forexampleincomplexitytheory.Theproblemssolvableinpolynomialtimebyunambiguous(nondeterministic)TuringmachinesarecollectedinthesubclassUP(UnambiguousPolynomialtime)ofNP[1].Therearetwoaspectsinthestudyofunambiguousautomata:expressivenessandcomputationalcomplexity.Concerningexpressiveness,becauseofthewell-knownequivalencebetweendeterministicandnondeterministicfiniteautomataoverfinitewordsandtrees,unambiguousautomatacanrecognizealltheregularlanguagesoverthesetwodomains.Forautomataoverω-wordsitisknownthatdeterministicBu¨chiautomataarestrictlylessexpressivethannondeterministicones[2].However,Arnoldshowedthatalltheω-regularlanguagescanberecog-nizedbyanunambiguousBu¨chiautomaton[3].Forautomataoverω-trees,theclassofunambiguousautomataisnotasexpressiveastheclassoffullnondeter-ministictreeautomata(withstandardacceptanceconditionslikeparity,RabinorMuller)[4,5].AninterestingsubclassoftheclassofunambiguousBu¨chiautomataiscon-sideredbyCartonandMichel[6]:Theirdefinitionrequiresthatforeachinput(acceptedornot)thereisauniquerunpassinginfinitelyoftenthroughafinalstate(whetherfromaninitialstateornot).Thus,aninfinitewordisacceptediftheinitialstateisthefirststateofthepathpassinginfinitelyoftenthrough