Le probl me de l
43 pages
Français

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

-

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
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

Informations

Publié par
Publié le 01 août 2009
Nombre de lectures 48
Langue Français

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?terministedesimotsourdehaquetailletatepaccept?spropri?t?.pars?del'automate,estlleaunomunbrepdetelchiheminsdeacceptanclassetspremi?dlaeconnaissance,taille?omolynomialqui).commotmencenunet(niedanscetteunde?dtl'alphabaOnttempsinitiald?cidableetlongueurterminenmottquidanslautde.ipOntoutalencefortemenlatexistelettreplusdoncUnacceptanpalorsleditetl'automatelangagesnon-ambigutousRemarqueestLsuiteautomatesqpB?c?telleedeonentielclasseplusestUnnon-amautomatefortemenndesonLad?terministeUnestheminunommencquinentupletsiaparunin'ilquentr?simondedoncclasseonsN?anmoins,vUnaheminNousdit-r?guliers.clangagess'ildeseno?p:terminenble?tatestOnuntempsensemd?cid?bleled'?tats.reconnparl'ensemetestbigusunhialphableetreconn.pardetvreconnaissenpd?terministes?tatMullerestunSi?tatournal.motD?nissonsiltoutaud'abunordheminplustformellemenontquelesestnotions.don1tesnousnon-ambigusauronseuventbtresoinexpparlementla5suite.
a q q q q0 1 2 n
n 1 a
n 1L = a = fa;bg L
n a
L
n+1 L
u v
L w2 uw2L,vw2L
n
u v n
n ku v k u =a v =b u:ak k
n kL v:a
n
n
ACC(n) n
ACC SEQ(n) u n
u A ACCA
A n2 N
ACC SEQ(n) =ACC(n)
P
n
n2N
P
depropsuos?tsencFigurereconn2automateestnundeautomatelnon-ampbiguauquelreconnaissanlestourL'automatebquifaireppr?senoss?deourra.leundet'un?tats..T?videnouscelalnaesoulonsautomatesled?terministesmaisquicompter.reconnaissen,tLessoiLaontestpuncoursnom?bremotsexpate.onenclassiquestielmotsd'?tats.deOnprappdeelle?que1deuxlorsmotsamotcet2.2duensonttl'?quiv-danseuneestm?meilclassepdevN?rtsopdeFig.ptsourunelequelangageosnquesiouretceseulelemenentpremiersilepbreourtailletoutparmottrerlaptlantousade,nomvheminsaourlettrel'automate-iemenoteralasiquesetelsn'estmotsProp.ilLenon-ambigu.nomourbrePd'?tatsd?terministes.deactsl'automateanminimalrecoestsurlseNousnomunbrcomptageetrerdepclassesautomadenN?roamdedeourl'automatefaut[14].o?Ors'arr?tertouseetlcompteresminsensemlongueurblesondepasdesourlettresstartsonsuivtermettendansrouvdesbclassesdesdevN?ro?desuitesdi?rensontes.casEnD-nies.eetconna?tresoienplustonble[3]etolycopi?'ensemsdeuxFmotsMPRI.deservironltrerlettres,estalors,nomquittede?depleermusuterl'automdoncSoitetmonestermet,quiilexemplesexistesommeuneourplesositiondes,tailletelleduquebreeccvacceptanapitletouroqueSOnbigu.remarquernon-amsut.l'automateAlonorsrestf?red?terministespasnont.estositiondansSoitetunetnipasAd?terministespautomatestouttreourenon.:Doncautomatesl'automatequeminimalompatunissnomnbreAutomateexpLemmesonenlestielited'?tats.r?currUnetescons?quencevimm?diutiliseratargumenede,pmaismonprimordiale,quedealencelaournon-amsbigu?t?testslaosuiv-anbigustedans:,lepnomcela,brenousdeunecorneheminsonelourra6dedeEntailloneailesesthe?galacceptanaudenom2bremaisdenemotseutdeletaillepttoutreconn...us.parlemmesl'automate.anEnpeettsitoneratelleunorne.cplupartheminlemmesacceptanl'ontapterourpropundesmot,r?currenilneesttunique.desDoncparticulierslesuitesnPoenmunbreeude?csujet,heminspaclireceptan,tspestdu?gald'algorithmeauecacesnomCalculbreormededumotsLesaccept?s.lemmesSoittonenmonpquexprobl?meedansfoss?acceptantsn A
;::::; n2N0 k 1
k 1X
A(n +i) =A(n +k)i
i=0
A n
A N R
S (A )s s2S
N R s2S
;t2S n2Ns;t
X
A (n + 1) = A (n)s s;t t
t2S
A ns
k2N
k n2N s2Ss;t
X
kA (n +k) = A (n)s ts;t
t2S
k = 1
k k + 1 n +k + 1
A (n +k)t
jSj
n + 1 As
jSj 2
n
A B N R
a b
D D(n) =A(n) +B(n)
a +b
A B 0 k a +b 1 A B
k2N
a 1 b 1X X
k kD(n +k) = A(n +i) + B(n +j)i j
i=0 j=0
desPreuvgalesedit:c'estMonrtrons?parourr?currenceaqueSoientp1.ourdestoutourdedudenenteourilautomateexistesoiendesdansconstandetesenccurrtes?encrSitellesOnquePreuvppourlemmestoutouruitesvsedesmotsetIlsontdefonctionsr?currenlesdeuxondesaita:airtoutesersuneloourAdes(1)unetouteourtellepsontque(lesetteldeonstantesdanscestdesmaisexisten?cessaireilvSiles.Unetoutdireoursiplongueur(2)ilEnteetdanscecidansestdoncvraibinaisonsparr?currenhdesypLemmeoth?seetpdeourquidans?deestionse.grSupplin?osonsaquepce?soitquevrai,auquerang,fonc-existe,onstantes,alo?rlin?sdemonplustrons.queetcagalesl'est?auellerangalorsdesontensembleourunour.:Onpreuvutilise1(1)queenlesoitautomatesetsvideaunondeensemble?un?(3)pontoutremplace,les?fosactionsoirSoitp1touteLemmedt.mots,quemenyr?ciproautanetde?accept?sl'aideundequel'hl'autre.ypfautoth?sequedecomr?currencelin?aires(2),suitesontespteutsuitesdonctes.conclure.2P.ardegr?cons?quenfonctionst,deoneasatisfontunrsystemecur-lin?aireenc?lin?dansirdesondeinconn?ues,etdonc.siLl'onfonctionprendd?niefonctiarunecurrcommer?quations,satisfaitellesalorssonOnttoutli?es.pDonctellesconsider?econstan?treo?vet?riesontunecr?currencesatisfaitlin?airerdecurrdegr?eauairplusdeeutgrpaur?ellequ'il.suitesuite2.Cepuneendanentet?ilpnouscurrfaudra-)rcomparersuitelesappmots,achi.cept?sB?cpar?deuxpautomatestoutdansceuxla.suite,eenCommeeet,laoneaLemmeuilraclairdeux:automates,seradoncelledeuxnissuiteslesr?currenptes,pluetpasonn'estvcesoudraariablestesterdeux.sauxfonctiogrnis,l'?galit?g?n?ralisationdeslafonctioautomatesnourspet7ensuite