Le probl me de l' quivalence pour les automates de B chi fortement non ambig s

Nicolas Bousquet

Description

Niveau: Supérieur, Master, Bac+4
Problème de l'équivalence pour les automates non-ambigus Nicolas BOUSQUET sous la tutelle de Christof LÖDING, Wolfgang THOMAS Juin-Aout 2009 Résumé Ceci est le rapport du travail que j'ai e?ectué durant l'été 2009 sous la tutelle de Christof Löding et Wolfgang Thomas. Il a porté sur l'étude du problème de l'équivalence pour les automates de Büchi non-ambigus. Ce rapport est rédigé en francais et les annexes sont les preuves en anglais des deux résultats principaux de mon stage : décision du problème de l'équivalence pour les automates de Büchi fortement non-ambigus et pour les automates fortement k-ambigus en temps polynomial. 1

• problème de l'équivalence


• automate


• automates déterministes


• classe des problèmes de décision décidable en temps poly


• fossé de classe de complexité entre les problèmes


• ple classique illustrant le fossé de taille entre automates déterministes


• classe d'automates

Sujets

• Aachen
• Cartón
• Thomas
• Michel
• Bousquet
• Automate

Informations

• Publié par: larec
• Publié le: 01 août 2009
• Nombre de lectures: 38
• Langue: Français

Extrait

k
tempsdemonl'?quivfrancaisalencedepbigus.oureslesalenceautomatespnon-amdebigustNicolassonBOUSQUETdeuxsousdulesattutelleuProbl?medelesChristofhiL?DING,rappWr?dig?olfganglesTHOlesManglaisASprincipauxJuin-A:outde2009ourR?sum?oCecihiesbigustleslefortemenrappbigusortolynomial.duautomatestraB?cvnon-amailCequeorj'aiesteectu?enduranettannexesl'?t?t2009preuvsousenladestuteller?sultatsdedeChristofstageL?d?cisiondingprobl?meetl'?quivWpolflgangautThomas.matesIlB?cafortemenpnon-amort?etsurourl'?tudeadutomatesprobl?metde-aml'?quivenalencepp1ourk
k
33deslesmati?res.1.In.trojeux,duction.2erio1.135Th?orie.des.automatese.p...........orm.dic.P.th?orie.des.p.automate.automate......dierence.......w......2biguous1.2.Automates.non-am.bigus....In.us.tre.de.la.B?c.euv.qui.?.....and.....29..............3erio1.3.Le.tra.v.ail.?.Aac.hen:.automata.paths.....Case.......B.3.ords.....Th?orie.de.dans.:.par.t.s.t.form.?.encore.Mark.repr?sen.globalemen4ou2t?Automatunes.nis.5.2.1.InA.2tro.duction..........Lemmas...........A.4.w...............Ultimately.i.............Conclusion....5.2.2.Lemmes.sur.les.suiteBsofabler?currenB?ctesB.1.the...........37.p.ords.............of.dic..6.2.3.R?solution.du42probl?meduction.automates.automates.br.s.domaine.la.alence.mots.automate.qui.form.exemple..si.v.on.it?.L.?tre.d'automates.[2],.probabilit?s.ha?nes.v8t3parAutomat.estoutdedeB?cloinhi?tre11un3.1nisInoutro.duction..............28.Denitions.Notations.......................A.3.on.equations..............11.3.2.Reconnaissance31dePladicnon-amordsbigu?t?............................A.5.p.d15c3.3ordsAutomate.de.l'in.tersection................A.6............................16.436L'?quivAnnexealenceProestfordecidable-amenstronglytempship37olynomialF20of4.1acceptingCas.des.mots.p.?rio.diques............B.2.of.erio.w.........................3920Case4.2UltimatelyCaseriodesWmots.ultimeme.n.t.p.?rio.diques......1.tro.1.1.des.La.des.a.nom.e.e.applications,.le.des.de22logique4.3?quivGeneralisationenauxlesautomatesaccept?sfunoetrceuxtesatisfonmenunetulesTMSOpar-amMaibigusaus.d.la.?rica.i.car.satisabil.de.ules23TL5eutConclusiod?termin?enl'aide26deAhiAnnexeou1des:carProcofdeinothepunamenbiguous?trecaset?es28desA.1sInPlustrotductionce.concerne.pr?s.de.l'informatique.eut.repr?sen.par.syst?me.?tats.:.graphe.un.2.
a q q q q0 1 2 n
n 1 a
A A1 2
L
P PSPACE EXPTIME
n
[17]uonentomoiratesundeuxts,sisousettelled?terminerdonn?,decomptagereconnais-ensencastenlem?mem?mnoneaulangageson.eutCeunprobl?meSeidlestJeappreel?doncprobl?melaquelledelal'?quivquealencet.laDeuxpprobl?mesdit,sonunt.particulieremenStearnstpli?sn?breceleprobl?mefaux.IlLedepremierype?sl'?quivtnon-amledeprob-d?ter-l?mel'?quivdenomiall'inclusion.pLeusecond,d?terministesbiencasqueaucunparaissanexiste,tnon-ambigusunditpileucceptanplusd?terministeloyinotain,heminsaautomatesennon-amg?n?ralonladem?meniscomplexit?temps:unilconna?tres'agitdeduilprobl?mecdeenl'univsersalit?.auxBienarquemptagetousauxceseraiprobl?mesoursoien3tod?cidablesprobl?meendanstemps1.2pIlolynomialt?ressandanserled'automatescaspdesprobl?meau-soittomatespnisdond?terministes,tatioils?trestoncom-tdesPSPtADansCE-completstraire,pclasseourt?r?t.lessautomatess'agitnisdesnonUnd?terministesiste[18]biguettoutEXPTIME-completsaupheminourautremenlesestautomatesildun'd'allerarbrnaleunsautresnishouennonparticulier,d??desterministesEn[8].HunPmonourlelesalencautomateslesdebigusB?cd?cid?hi,olynomial.ilsutilis?sonttp?galemenetePSPaccept?sAnon-amCE-decompletsbre[16].accEnestg?n?ral,totalemenonlemonEntrecelad'arbresdaussiiucult?dedulesprobl?meanndeau-l'univd?versalit?cequid'automates,implsaique?lardiscult?udduleprobl?demealencedelel'?quivg?n?ral.alence.AutomatesEnbiguseetseraitoninpteuttrouvr?duireunedeclassefa?onnon?videnministesteourleleprobl?mededealencel'univd?cidableersalit?tempsdoly-amaisntsrepr?senceluindeourraitl'?quivexpalence.tiellemenUnplautomatesnonpacted?terministecellerecautomatesonnaissanreconnaissantleunlangage.langageleutileconpceeutte?n'auraittrineUneexpclao-seneniltiellemendetclasseplusautomatescompact.queautomatelesd?termin-automatesestd?terministesnon-amquisileourreconnaissenmott,existeceplusqcuiaexpliquet,letfoss?l'automatedenonclassemaisdeexistecomplexit?plusenmotreenlesdansprobl?mes.?tatUnpeurxmotelesm-cple?cclassiquetillustranEntlesledfoss?terministesdettailleautomatesenbigus.tre1981,automatesetd?terministestettnontr?d?terministes,quedonprobl?metl'?quivnousereparleronsourpaautomatesrnon-amlapsuite,?treestenl'exemplepdeL'argumelatFigureest1.argumenBiendeque:leourplroblnom?medrestemotsouvtailleaert,parilautomateestbigu,commsutunemencomptertnomadmisdequeheminsleeptansceciinclusionsbienparfoistenduesttIldanstcaang?n?ral.iss1990,nag?n?ralisenr?sultatrecoautomatesAutomate[15].utilise1unFig.g...mstarttsoncotsurdesautomatesinclusionsdemi-strictes,eautremen(semi-ringttomata).dit,neoneloppppasensetqu'ilen'existeppasend'algorithmevpplusolynomialleurpourPUPNP
P
!
!
!
k
k
ici[14].[5].SeidlMaxsemotsram?nequialorsons,?accepteunlprobl?vmeB?cd'accessibilit?hi?ourunaussiespacepvnaturelectoriellaque?tatl'onnon-pacceuttoutr?soudreSakenttempsc'estpqolynomial.trouvLadenotionpdeEtanclassedennon-amu'ibtisgu?momenestn'arrivionsassezautomatesg?unn?raleunetcommenceasond?j?c?t?queinquetrod?cid?eduiteourdansed'autresourhdomaialencenes.deAinsiinenlassecomplexit?,elad?terminiclassesUPprobl?me(UnamenbiguousdansPnon-amoly-ilnomialgarderTime)sestCeplaestclasseledes?probl?messaitdeheminsd?cisionquelled?cecidableuneelesnourtempsestpdeoly-cnomialilparinitial.unemenmactelshineexistede.Tonuringreconna?tnvodeuxnbigusd?terministepquideanis.autemps,plusB?cunautomatescilhemindesacceptanletautomatesplesohiuseraitrtcunehaquequienxtr?eles[19].hiEntesparticulier,lesil-r?guliers)estlaquelleclairl'?quivq?treuepdedonn?livrecadrelelesconsulterpourracettepdonconr.e1.3enLeptramotsvtailcomptage?pilierAacehendEnnisAllemagne,inj'aioneectu??monlesstagetsousnilaCommedirection?denousChristofconsid-L?classedingbigusetfortemenWbigus.olfgangmotThomasheminaucRuneWTHsAacnal.henest(Aixtlaterminalcunhapautomateselle).forDansnon-amunlespremierptempsij'aiplus?tudi?inlesCartonr?sultatshelconnmonusclasseplesourNouslemonprobl?mealencededel'?quivtalenceeutpnourenlesaauto-is?ematessnon-amabigus,unetcetteensuiteautomatesnousfortemenadirevqueonsmottenaut?consid?r?sdepasg?n?ralisertrercesder?sultatsourauxpressifsautomatesuedeautomatesB?cB?chi.d?terministesAinsiIlStearnsdoncett?ressanHundeter[17]cond'automatestsoitprouve?pressivquequel'?quivautomatesalenceB?cd'automatesnonnissnon-am(quibtousilangagegusaroestetdansouros,leende1981.alenceEneut199d?cid?0,tempsSeidlolynomial.letprouvqueelepdesournislesautomatesautomatesbigusd'arbresoss?-[15].tDanspropri?t?,leestcasassezdesdeunrankeedctreeqautomatal(ar-ebrestsansourrang),escinnis.'est-?-direendanlesl'argumenautomatesdearbresquipleourdelesquelspreuvlesdanstcadreransitieonsmotsseestfonprioritutilisable?carl'aidenedepaslangagesquelrationnels,tlecprobl?mepassendeunl'?quivnalalence?pfr?quence.ournouslpasesr?soudreau-probl?me,tomatesanon-amonsbiguser?estsouspdesolynomialnon-am[10],:carautomateslattransformationamdesPautomatesund'arbresinni,sanscrangterminalauxunautomateshemind'arbrespassenisinnit?mainfoitienpart?tatlaUnnon-amheminbigu?t?donceteptanestsipestolynomiale.etIlenest?tatenLesdedem?mehipteourtlabigusr?ductiontdesautomatesvisiblyquepushdoourwnsmotautomata,luneausousunclassehemdesterminalautomatesOlivier?etpiMicle.[7]Ainsi,tlatr?non-acettemd'automatesbigu?t?tousplangagesermet-r?guliers.dead?cideronsl'?quivtr?alencel'?quivendetempsautomatespB?colynomialfortemenpnon-amourpde?trenomebtempsreolynomialusadaptanelsm?thoclasses.utilIlpestledoncautomatesnaturelNousdevsedansdemandersecondsg?n?ralis?ipreuvceauxr?sultatdephivitct-ameutbigu,?tre?g?n?ralauxis?telsaupproptoutcinni,terminaux.exister?sultatspluseuvthemins-langages.CesLpesenautomates?tredecommeB?cpremiershipnonmond?terministesquesonprobl?metl'?quivstrictemenptlesplus4ex-!
!
n
n
A =
(Q; ;q ;Q ;)in f
Q

q 2Qin
Q Qf
Q Q
Q Q
f0; 1g 1
(p;a)2Q
q2Q (p;a;q)2 (q;a;p)2
juj
u u i ui
u =u :::u q :::q (q ;u ;q )21 n 0 n j 1 j j
q q =q q q =q0 juj
q L(A)in
A L (q) AA
q u
actquenon-amcommebiguourpOrouvestaitet.?tre.expB?conenrtiellemequinCetpplussucompactd'?tatsqu'untermineautomatenotedeunMulleransitionsd?ter-lesministe,dansprouvpanexistet(resp.ainsidansl'indut?-emerreconna?t?biguste.decettelaetnotionudeafortenon-amd'?tatbigu?t?sousetlesdeaussinotreder?sultat.esN?anmossiinsble,cilcoupleexistesdesolimitesd'automates?notreceestr?sultat,lettresenenparticulier,estlesnoteraauto-.mates-r?guliersd?terministesuined'automatessonautomatestcent?r?tsg?n?ralnompascfortemencommencetunnon-am?trebigus,petuilourpinitialeutautomatesarrivunernauxqueestlesbleautomatesded?terministesel?sOnoemenienunetiexpdansonenttiellemenautttripletplussouscompacts.qued?terministeles)automatescfortemenendantcettenon-amibigusplus[qui7].B?c2reAutomatesc'estnis:2.1UnInsuitetpartie)roeductionnoteNouslaallonsestpr?senlongueurterte.dansl'?quivcettedepartiecheminl'algorithmemotd?les?uneR.E.hiStreansqueetune?tH.B.classeHuncteIelle-m?mI,Ibreux[17]ade.1981estquieptantprouvolynomial.eequenal.lesenprobl?meslangagedeeutl'non-am?qulangageil'automatevecalenceinitialet?tatde.l'inclusiondeplesourestlesensembleautomatessnis.non-am[12].bigusunpensemeuvdeenMulletautomates?treappd?cid?stre.nconsid?reratemps(abusivpt)olynomial.commeL'id?efonctionprincipalennis,demotslasurpreuvd'automateseypestd'autresunvargumenexistetledeestcomptagele:ensemenileetL'automateleditnom(resp.breo-d?terministedesimotsourdehaquetailletate