Equivalence of Alternating and Non-deterministic Büchi Automata

EquivalenceofAlternatingandNon-deterministic

B¨uchiAutomata

RafaelPe˜naloza

rpenalozan@yahoo.com

December2,2005

Abstract

WeshowthatalternatingB¨uchiautomata,ageneralizationofnon-deterministic

B¨uchiautomata,definethesameclassoflanguagesasnon-deterministicB¨uchi

automata.Thisway,non-deterministicautomatacanbeusedtosolveproblemsfor

alternatingautomata,suchastheemptynessproblem.

Theproofofequivalencewillbedonewiththehelpofstrategytrees,whichtell

oneverynodeoftheinputtreewhichtransitionshouldbeusedinordertoobtain

anacceptingrun.

Thetranslationyieldsanexponentialblow-upinthenumberofstatesofthe

automaton.Thismeansthatanyalgorithminwhichanalternatingautomatonis

firsttranslatedintoitsequivalentnon-deterministicautomatonwillbeexponential

inthebestcase.Thiscannotbeimprovedas,forexample,theemptynessproblem

ofalternatingautomataisExp-Hard;thus,thetranslationisanoptimalalgorithm.

1Introduction

Theconceptofalternatingautomataisageneralizationofnon-deterministicautomata.

Alternatingautomatahavebeenusedtosolvethesatisfiabilityproblemofdifferent

kindsoflogics.

Thisaplicationrequiresanemptynesstestofthealternatingautomaton.Asthe

emptynessproblemfornon-deterministicautomatahasbeenverywellstudied,one

wouldliketousethetechniquesdevelopedfornon-deterministicautomatatomakethe

testforalternatingautomata.

Itturnsoutthatalternatingandnon-deterministicautomataareequivalent.This

meansthattheemptynesstestmaybeperformedforanequivalentnon-deterministic

automaton.

Astheemptynessproblemofnon-deterministicautomatacanbesolvedinpoly-

nomialtime,whilethesameproblemforalternatingautomataisExp-Hard,anon-

deterministicautomatonmustnecessarilybeexponentiallylargerthanitsequivalent

alternatingautomaton.

Here,aproofofequivalencebetweenalternatingB¨uchiautomataandnon-determi-

nisticB¨uchiautomataisgiven.Ashasbeenpointedoutbefore,everynon-determinis-

1ticautomatonisalsoanalternatingautomaton.Thus,theequivalenceproofrequires

onlytoconstruct,foreveryalternatingB¨uchiautomaton,anon-deterministicB¨uchi

automatonthatacceptsthesamelanguage.

Toachievethisgoal,somerestrictedcasesaredealtwithfirst,aimingatgivinga

betterunderstandingofthegeneralconstructionappearingattheendofSection3.

Theconceptsneededforconstructingandprovingcorrectessoftheequivalentnon-

deterministingautomataaregiveninSection2.Theforementionedconstructionsap-

pearinSection3.Attheend,inSection4,someconclusionsaregiven.

2Preliminaries

Definition1Letk∈N.Ak-arytreeisasetT⊆{1,...,k}∗suchthatifx·n∈T,for

x∈N∗,n∈N,thenx∈Tandx·m∈Tforall0

T={1,...,k}∗.

Alabeledk-arytreeoveranalphabetΣisapair(T,V),whereTisak-arytreeand

V:T→Σ.IfΣ=Γ×∆thenVwillbeexpressedastwofunctionsV=(V

1,V

2),and

(T,(V

1,V

2))willbedenotedby(T,V

1,V

2).

Aninfinitepathonak-arytreeTisasetP⊆Tsuchthatǫ∈Pandforeveryx∈P

thereexistsauniquei∈{1,...,k}suchthatx·i∈P.

Treesthatarenotfullwillbeusedtodefinetheconceptofrunoveralternating

automata.Apartfromthat,allthetreesusedusedasinputfortheautomatawillbe

assumedtobefull.

Definition2Letk∈N.Anon-deterministicB¨uchiAutomatonoverk-arytreesis

atupleM=(Q,Σ,∆,I,F),whereQisafinitesetofstates,Σisanalphabet,∆⊆

Q×Σ×Qkisthetransitionrelation,I⊆Qisthesetofinitialstates,andF⊆Qisthe

setoffinalstates.

Arunofanon-deterministicB¨uchiAutomatonM=(Q,Σ,∆,I,F)onafulllabeled

k-arytree(T,V)overΣisafulllabeledk-arytree(T,r)overQsuchthatr(ǫ)∈Iand

forallx∈{1,...,k}∗,(r(x),V(x),r(x·1),...,r(x·k))∈∆.Sucharunrisacceptingif

andonlyifforeveryinfinitepathPin(T,r),thereexistinfinitelymanyx∈Psuchthat

r(x)∈F.

Thelanguageacceptedbyanon-deterministicB¨uchiAutomatonMisthesetL(M)

ofallfulllabeledk-arytrees(T,V)suchthatthereisanacceptingrunofMon(T,V).

Anon-deterministicloopingAutomatonisanon-deterministicB¨uchiAutomatonin

whichallthestatesarefinalstates.Thus,thefinalstatesarenotexplicitelystatedinit.

Thetransitionrelationofanon-determisticB¨uchiautomatoncanbeseenasafunc-

tion˜δ:Q×Σ→P(Qk),where˜δ(q,σ)={(q

1,...,q

k)|(q,σ,q

1,...,q

k)∈∆}.Onthe

otherside,asetP={(q1

1,...,q1

k),...,(qn

1,...,qn

k)}∈P(Qk)canbeseenasthepositive

Booleanformula((1,q1

1)∧...∧(k,q1

k))∨...∨((1,qn

1)∧...∧(k,qn

k)).Intuitively,apair

(i,q)∈{1,...,k}×Qmeansthattheautomatonshouldgotothei-thdescendantwith

thestateq.

2Hence,ifB+(X)denotesthesetofallpositiveBooleanformulasoverasetX,then

thetransitionrelationcanbeseenasafunctionδ:Q×Σ→B+({1,...,k}×Q)wherefor

allq∈Q,σ∈Σ,δ(q,σ)hastheform((1,q1

1)∧...∧(k,q1

k))∨...∨((1,qn

1)∧...∧(k,qn

k)).

AlternatingB¨uchiautomatageneralizenon-deterministicB¨uchiautomatabyallow-

ingδtobeanarbitraryfunctiontothesetofpositiveformulas,andalsobyallowinga

transitionthatstaysinthesamenode,whichwillbecalled0-transition.Thisisstated

formallyinthenextdefinition.

Definition3Letk∈N.AnAlternatingB¨uchiAutomatonoverk-arytreesisatuple

A=(Σ,Q,δ,q

0,F),whereΣisanalphabet,Qisafinitesetofstates,δ:Q×Σ→