Automates finis Automates de Buchi non ambigus
32 pages

Automates finis Automates de Buchi non ambigus

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Niveau: Supérieur, Master, Bac+4
Automates finis Automates de Buchi non ambigus Probleme de l'equivalence pour les automates non ambigus Nicolas Bousquet sous la tutelle de Wolfgang THOMAS et Christof LODING Ete 2009 Nicolas Bousquet, sous la tutelle de, Wolfgang THOMAS et Christof LODINGProbleme de l'equivalence pour les automates non ambigus

  • automates de buchi

  • containment problems

  • automate fini

  • christof lodingprobleme de l'equivalence pour les automates

  • probleme de l'equivalence pour les automates

  • finite tree


Sujets

Informations

Publié par
Nombre de lectures 83
Poids de l'ouvrage 1 Mo
AutomatesnisAuotametdsBeu¨hcniamongubissuoBteuqciNsaloelutdeleou,satslAMeSTgOHgfnaW,lotCqe´ledeme`lborPesrlouepnclevauisug
Et´e2009
sous la tutelle de
Nicolas Bousquet ¨ Wolfgang THOMAS et Christof LODING
Probl`emedele´quivalencepourlesautomatesnon ambigus
toautemaonsnbiam
uolstes,leeltatuicolNusquasBotCSeTgnaAMOHW,edgfloncepourlequivalemedele´rPbo`l
Automates finis AutomatesdeB¨uchinonambigus
Aachen
sgubimanonsetamotuase
eB¨utesdtomaisAusenmotaAtuonamchinsbigusaoBcilotes,suuqNbo`lmedele´qeiuPrgfloTgnaAMOHCteSslouutatleel,Wdes
Richard Edwin Stearns, Harry B. Hunt III :On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Grammars, and AutomataFOCS 1981 : 74-81 Helmut Seidl :Deciding Equivalence of Finite Tree Automata. STACS 1989 : 480-492 Olivier Carton, Max Michel :tuAihcu¨atamoamUnsBougubi. LATIN 2000 : 407-416
Travauxrelie´s
gubiamonsntematouaselruopecnelav
Nciou,setquusBoasolloW,edelletutalsnsnoametugsmaib
AutomatesdeBu¨chinonambigus AutomatedeBu¨chi Nonambigu¨ıt´e Argument de comptage
Content
Automates finis
1
2
gfnaTgOHAMeSCtProbme`lledeqe´aviuncleouepesrltoauigushinonambseed¨BcuAstumotatemanistoAu
gibmanoNihcu¨BedtematoAunalBsiNocategocpmntdegume´eAru¨ıt¨BcuihonmotaseedAutsaleurpoesatomutuqe´ledecnelavibmgionan
2
Automates finis AutomatesdeBu¨chinonambigus
1
Automates finis
su
ambigus
lltee,edlfWonggaqsuo,teusuosutalProbl`emeHTMOSAteC
gubiamoninch¨ueBsomatAutetdsotamsiuAsencoNi
D´enition Unautomatenonde´terministeAest un quintuplet (Q,Σ,qi,Qf, δ) de´nipar: Qest un ensembledats´et. Σ est unalphabet. qiest unl´aetinitita. Qfest un ensembled´etatsnaux. δest un ensemble detransitions.
mbigus
Automates finis
atesnonaaselmotuecneruopqu´ealivme`eldeorlbPCASetTHOMgangfloW,edelletutalussot,uesqousBla
lltee,edussotulaqsuo,teuociNBsalPCSAteHTMOaggnoWflsaleurpoceenalivuqe´ledeme`lboribugNsnomaibugtitesdeB¨uchinonam´eoommuatteessatnniasnAouitgommba
D´enition Un automate finiA= (Q,Σ,qi,Qf, δ) est non ambigu si pour tout mot il existe au plus un chemin acceptant.
su
Σ q1q2
a
q0
Σ
start
qn
Σ
...
At
L= ΣaΣn1
u
asolicNobPreml`CtOHTgeSAM,Wolfganutelledes,uolstaoBsuuqteametsinuAotesdeB¨ucsAutomatsugibmanonihambisnon
Argument de comptage
Observation Le nombre de chemins acceptants de longueurnagaltse´eu nombredemotsaccepte´sdelongueurn.
Proposition SoientAetBdeux automates finis non ambigus. SiL(A)L(B), alorsL(A) =L(B) ssiAetB ˆt l on e meme nombre de chemins acceptants pour toutn.
guseq´elednclevauiselruopeetamotua
α1
p1
p2
start
p3
α3
α2
q
qi
onantasesu
Observation Le nombre de chemins de longueurn+ 1 deqiaqQest une fonction du nombre de chemins de longueurndeqiappour tout pQ.
bmgiProblaggnHTMOSAteCceenurposaleomuteme`leduqe´laviiNocfloW,edelletutalussot,uesqousBlanisatesutomABedshcu¨otuAetamsguoninbiam
start
p1
q
n3
p3
Observation Le nombre de chemins de longueurn+ 1 deqiaqQest une fonction du nombre de chemins de longueurndeqiappour tout pQ.
qi
n1
n2
p2
bmansugiatomnoesleurutsalaneecople´uqvibl`emedeProCteSAMOTHnggalfWoe,edllutetsual,tosqseusBoucolaNiugibstuAtomaisAuesnomatnomahcniBeu¨etds
almoogtfnnsaeTtgmOaHnAoMuegSiCbt
Observation Le nombre de chemins de longueurn+ 1 deqiaqQest une fonction du nombre de chemins de longueurndeqiappour tout pQ.
p3
s
n1α1 p1q
n1
n3α3
n3
n2
p2
qi
start
n2α2
Prbloo`climoeBdsealueq´suqse,ituevsalloeunucteaptoluerelle,sWadueNgusambiinon¨uchesatomutABedsetamotuAsin