Variable Automata over Infinite Alphabets PDF

Finite Automata

20 juil. 2022 A string over an alphabet ? is a finite sequence of characters drawn from ?. ?. Example: If ? = {a b}

Automata Theory and Languages

Automata Theory Languages and Computation - M?rian Halfeld-Ferrari – p. 1/19 Example: 01101 and 111 are strings from the binary alphabet ? = {0

Chapter 1 Automata over infinite alphabets

state automata but whose input alphabet is infinite. While use of such automata for verification requires that the non-emptiness problem be decidable

Automata Learning with Automated Alphabet Abstraction Refinement

Automata Learning with Automated Alphabet. Abstraction Refinement. ?. Falk Howar Bernhard Steffen

Alphabet word Finite Automata

Word (over alphabet A) … finite (maybe empty) sequence Alphabet word. Finite Automata. Alphabet and words ... alphabet … finite set of symbols.

Variable Automata over Infinite Alphabets

24 oct. 2010 VFA form a natural and simple extension of regular (and ?-regular) automata in which the alphabet consists of letters as well as variables ...

Single-Use Automata and Transducers for Infinite Alphabets

Keywords and phrases Automata semigroups

Generalisation of Alternating Automata over Infinite Alphabets

14 août 2020 To cite this version: Xiao Xu. Generalisation of Alternating Automata over Infinite Alphabets. Formal Languages and. Automata Theory [cs.

Decision Questions for Probabilistic Automata on Small Alphabets

27 juin 2022 Key words and phrases: Probabilistic finite automata unary alphabet

Enumeration and random generation of accessible automata

24 févr. 2010 We present a bijection between the set An of deterministic and accessible automata with n states on a k-letters alphabet and some diagrams ...

VariableAutomataoverInniteAlphabets

Abstract

diculttounderstandandtoworkwith.

1.Introduction

straction)forcopingwiththegeneralcase. alphabets.1 ity,andcontainment. contentnondeterministicallyduringtherun. 2 andsoon,withnopossibleshortcuts. 3 ictsbetweendier- tothesettingofinnitealphabets. 4 VBAs.

2.VariableAutomataoverInniteAlphabets

acceptingrunofAonw. thatrangesoverN. i L bybothxandy. 5 xxxxx xx xy y,y,y,y111 111
A AA123

Considerawordv=v1v2:::vn2

AreadalongA,andanotherword

vi=wiforeveryvi2A,

Forvi=yandvj6=y,itholdsthatwi6=wj.

thoseassociatedwithXvariables.

Wesaythatawordv2

Aisawitnessingpatternforawordw2ifwis

fromalltheotherletters.

2.1.ComparisonwithOtherModels

6 notberestrictedtolettersintheinputword. fromExample2. wandCacceptsallappropriatesubwordsofw0. substitutingtherstappearanceofxiwithx0 i.Thissubstitutionmakessure everyx2X,andanNFAfory. 7

3.ClosurepropertiesforVFAs

Theorem1.VFAsareclosedunderunion.

fy1g;Q1;Q1

0;1;F1iandA2=h2[X2[fy2g;Q2;Q2

0;2;F2i.3

A inasimpleunionconstruction. LetAh beenassignedtothevariablesinh.LetA0

1betheunionoftheNFAsA1

h,for allh2H1.NotethatthealphabetofA0

1is1[X1[fyg.WedeneH2and

A 0 ofA0

1andA0

2. A ofstatesofAbyn1cd1+1

2+n2cd2+1

1,anditswidthbyd1+d2.Thesebounds

unionconstructionworks.

VFAsareoverdierentalphabets.

Theorem2.VFAareclosedunderintersection.

fy1g;Q1;Q1

0;1;F1iandA2=h2[X2[fy2g;Q2;Q2

0;2;F2i.

A xorwith. z severalVFAs,oneforeveryrelation. H (y1;y2)isthefreevariable.LetH=HV[HAB.

WedeneAH=h(1[2)[HV;Q1Q2;Q1

0Q2

0;;F1F2i,where

z2(1\2);q0121(q1;z),andq0222(q2;z), q

0222(q2;z),

2(q2;z2),

WedeneA=h;S

HAHi.ThesetofboundedvariablesofAisHVn

fhy1;y2ig,andthefreevariableishy1;y2i. 9 12xa

1A34y,bBx

2 12xa

1A B

34y,b,ax

2 12 a

34y,bb

a :ax2:bx1U

A BU

1,32,4:yx1

1,32,3x12,4:x2x1,2ayx

1,32,4:bx1b

a:y A statesofAbyO((n1n2)(d1+d2+c1+c2)! relationsH.

VFAsAandB.

distinct. 10

4.DecisionproceduresforVFAs

theseproblemsforVFAs. wordinL(A). guessesawordv2jwj w,andcheckswhetherv2L(A)andg(v)=w. A fromGbylabelingeachedgebyitsdestination. undecidable. 11 cidable.

PCP(Post'sCorrespondenceProblem).

thePCPinstance.

5.DeterministicVFA

manner. automaton. 12 x1 x2 x1 y x 1y,x1 DA equivalentDVFA. ioneofthefollowingholds.

1.Aisnondeterministic,

traversexandx0, sthatdoesnotexits,or along,andydoesnotexits. 13 letterhasnotappearedbefore. undercomplementation,wearedone. inGiAGisnotdetereministic. sequel,thelatterproblemismuchharder. donotyieldaDVFA. everyhq;i2Q2Xandz2A[X[fygasfollows. (hq;i;z)=( (q;z)f[fzggz2X[fyg (q;z)fgz2A(1) fromtheinitialstate.

Remark1.Astateintheunwindingre

ectsthesetofallvariablesthatare 14

1.Uisdeterministic

y,butnotboth.

Lemma1.AVFAisequivalenttoitsuwinding.

showthattheyallleadtoacontradiction. ministicthenUisdeterministic. contradiction. leadstoacontradiction. ministicthenAisdeterministic. 15

Theorem8.DVFAareclosedunderintersection.

resultmustremaindeterministic. overdierentalphabets. 16 x1a 1 2 ax ,y1 x235x34x ,y 3 x2x2 1,3 a x1,2 2,4x

1,x22,5a

,x3x 1,x2 4a ,x2 5y ,x3x 1,x2 s, s, x1,x2 s,t 5a ,x3x 1,x2 s, y,y a,x3x 1,x2 s,t yx3ax1,2yx1,2 a AB A B U pendixA.1

Theorem9.DVFAareclosedunderunion.

markedasaccepting.

Formally,wehavethefollowing.

17 nL(A). thatL(~A)=nL(A).

AnL(A),

morecomplicatedlowerbound. D. same thattheyaredecidable. condition. 18 bedoneinPTIME. oflengthatmostn1n2toitsnonemptiness.

6.Determinization

alwaysbedeterminized. patternautomaton,acontradiction. noequivalentDVFAexists)isundecidable. A doesexist. 19 url=www..com;email=@.comxxz x.t .com;email=@xz 1 2 t 1 2 ..com

Figure5:AsyntacticallydeterminizableVFA

noytransitions. x.t.com. equivalentVFA(butnotnecessarilyaDVFA). F 20

Itispossiblethatqi=qjfori6=j,ifi6=j.

X s=S ijXg. U.Let X 0s=S i,wherei=ijXg. tos0re hx;zitothelistofmappings. s

Forastates2QD,letZs=S

hq;i2sjZ,andletZ0sbethesetofvariables inZs[fygandthelettersinA. thefollowinglemmas. ministic. 21

Foreverystates2QD,letZs=S

hq;i2sfjZg.Weshow,byrenamingevery havethatDisidenticaltoitsunwinding.

Lemma4.TheVFADisequivalenttoA.

v and ifv2L(U)thenf(v)2L(D), followinghold. itholdsthathtm;mi=hqi;ijXi,and 22
url=www..com;email=@.comxxz t .com;email=@xzt..com oftheserunsisacceptinginU.

ThecompleteproofisgiveninAppendixA.3

toshowthatZisnite.

Proof:Theorem16followsfromLemmas3,4and5.

sinks.

7.VariableBuchiAutomata

23
ictsbetweenassign-

DVBAcanbecomplementedtoaVBA.

VFAsallapply,withminormodications.

complete.

PTIME.

co-NP.

References

2009.

IEEEComputerSociety,2006.

Science,295:85{106,2003.

Manolescu.Specicationanddesignofwork

ow-drivenhypertexts.J.Web

Eng.,1(2):163{182,2003.

StanfordUniversityPress,1962.

2007.

Springer,2010.

AFL,pages195{207.Ineds.:,2008.

icalComputerScience,134(2):329{363,1994. ofLNCS,pages248{262.Springer,2003.

UK,2001.Springer-Verlag.

2009.
25
frontier.InICDT'09,pages1{13.ACM,2009.

AppendixA.Proofs

AppendixA.1.ProofofTheorem8

where

X=((X1[fy1g)(X2[fy2g))nfhy1;y2ig,

y=hy1;y2i,

Q=(Q1Q2)212,

q0=hq10;q20;;i,

F=(F1F2)212,and

Thetransitionfunctionisasfollows.

fz2j9z1:hz1;z2i2g. 0=,or z [fha;z2ig,or if z

1=2,andifz22X2thenz2=2and0=[fhz1;z2ig,or

=0, 26
A

Consequently,wehavethatUisdeterministic.

s indeedbeassigned2(resp.1). v letterwi. s wehavethatw2L(U1)\L(U2). 27
ij1\X1=iandij2\X2=iinductivelyasfollows. hhs1;;i;ht1;;i;;i. v hhs1;;i;ht1;1i;fhz;v21igi. bythedenitionofwehavethat v havethatv1m=2m1j1. fhv1m;y2iig. 28
contradiction. v w z

AppendixA.2.ProofofTheorem9

F=((F1Q2)[(Q1F2))212.

AppendixA.3.ProofofLemma4

functionf:X!Zsuchthatthefollowinghold. and

Ifv2L(U)thenf(v)2L(D),

29
words. s v v s f=hyieldsasuitablefunction. suitablefunction. thefollowingholds.

Itholdsthathtm;mi=hqi;ijXi,and

oftheserunsisacceptinginU. 30
functionsfgig1ik. settingg1=;. s asuitablesetoffunctions. u suitablesetoffunctions. x 31
quotesdbs_dbs20.pdfusesText_26

[PDF] Variable Automata over Infinite Alphabets

VariableAutomataoverInniteAlphabets

Abstract

1.Introduction

2.VariableAutomataoverInniteAlphabets

Considerawordv=v1v2:::vn2

AreadalongA,andanotherword

Forvi=yandvj6=y,itholdsthatwi6=wj.

Wesaythatawordv2

Aisawitnessingpatternforawordw2ifwis

2.1.ComparisonwithOtherModels

3.ClosurepropertiesforVFAs

Theorem1.VFAsareclosedunderunion.

0;1;F1iandA2=h2[X2[fy2g;Q2;Q2

0;2;F2i.3

1betheunionoftheNFAsA1

1is1[X1[fyg.WedeneH2and

1andA0

2+n2cd2+1

1,anditswidthbyd1+d2.Thesebounds

VFAsareoverdierentalphabets.

Theorem2.VFAareclosedunderintersection.

0;1;F1iandA2=h2[X2[fy2g;Q2;Q2

0;2;F2i.

WedeneAH=h(1[2)[HV;Q1Q2;Q1

0;;F1F2i,where

0222(q2;z),

2(q2;z2),

WedeneA=h;S

HAHi.ThesetofboundedvariablesofAisHVn

1A34y,bBx

1A B

34y,b,ax

34y,bb

A BU

1,32,4:yx1

1,32,3x12,4:x2x1,2ayx

1,32,4:bx1b

VFAsAandB.

4.DecisionproceduresforVFAs

PCP(Post'sCorrespondenceProblem).

5.DeterministicVFA

1.Aisnondeterministic,

Remark1.Astateintheunwindingre

1.Uisdeterministic

Lemma1.AVFAisequivalenttoitsuwinding.

Theorem8.DVFAareclosedunderintersection.

1,x22,5a

Theorem9.DVFAareclosedunderunion.

Formally,wehavethefollowing.

AnL(A),

6.Determinization

Figure5:AsyntacticallydeterminizableVFA

Itispossiblethatqi=qjfori6=j,ifi6=j.

Forastates2QD,letZs=S

Foreverystates2QD,letZs=S

Lemma4.TheVFADisequivalenttoA.

ThecompleteproofisgiveninAppendixA.3

Proof:Theorem16followsfromLemmas3,4and5.

7.VariableBuchiAutomata

DVBAcanbecomplementedtoaVBA.

VFAsallapply,withminormodications.

PTIME.

References

IEEEComputerSociety,2006.

Science,295:85{106,2003.

Manolescu.Specicationanddesignofwork

Eng.,1(2):163{182,2003.

StanfordUniversityPress,1962.

Springer,2010.

AFL,pages195{207.Ineds.:,2008.

UK,2001.Springer-Verlag.

AppendixA.Proofs

AppendixA.1.ProofofTheorem8

X=((X1[fy1g)(X2[fy2g))nfhy1;y2ig,

Q=(Q1Q2)212,

F=(F1F2)212,and

Thetransitionfunctionisasfollows.

1=2,andifz22X2thenz2=2and0=[fhz1;z2ig,or

Consequently,wehavethatUisdeterministic.