Algebraic Elimination of epsilon-transitions

We present here algebraic formulas associating a k-automaton to a k-epsilon-automaton. The existence depends on the definition of the star of matrices and of elements in the semiring k. For this reason, we present the theorem which allows the transformatio

4

002 ceD 31 ]CS.sc[ 2v210104/0sc:viXraDiscreteMathematicsandTheoreticalComputerScience(subm.),bytheauthors,26–rev

Algebraiceliminationofε-transitions

G´erardH.E.Duchamp1,HatemHadjKacem2andEric

´Laugerotte2 1LIPN,UMRCNRS

7030.InstitutGalil´ee-Universit´eParis-Nord99,avenueJean-BaptisteCl´ement93430Villetan-

euse,France.

2LIFAR,Facult´edesSciencesetdesTechniques,76821Mont-Saint-AignanCedex,France.

received15September2004,revised1stFebruary2008,

1Introduction

Automatawithmultiplicities(orweightedautomata)areaversatileclassoftransitionsystemswhichcanmodelizeaswellclassical(boolean),stochastic,transducerautomataandbeappliedtovariouspurposessuchasimagecompression,speechrecognition,formallinguistic(andautomatictreatmentofnaturallanguagestoo)andprobabilisticmodelling.Forgeneralitiesoverautomatawithmultiplicitiessee[1]and[10],problemsoveridentitiesanddecidabilityresultsontheseobjectscanbefoundin[11],[12]and[13].Aparticulartypeoftheseautomataaretheautomatawithε-transitionsdenotedbyk-ε-automatawhicharetheresult,forexample,oftheapplicationofThompsonmethodtotransformaweightedregularexpressionintoaweightedautomaton[14].Theaimofthispaperistostudytheequivalencebetweenk-ε-automataandk-automata.Indeed,wewillpresenthereanalgebraicmethodinordertocompute,foraweightedautomatonwithε-transitions(chooseninasuitedclass)anequivalentweightedautomatonwithoutε-transitionswhichhasthesamebehaviour.Here,theclosureofε-transitionsimpliestheexistenceofthestaroftransitionmatrixforε.Itsrunningtimecomplexityisdeducedfromthatofthematrixmultiplicationinkn×n.Inthecaseofwell-knownsemirings(likebooleanandtropical),theclosureiscomputedinO(n3)[15].We ttherunningtimecomplexitytothecasewhenkisaring.

Thestructureofthepaperisthefollowing.We rstrecall(inSection2)thenotionsofasemiringandthecomputationofthestarofmatrices.Afterintroducing(inSection3)thenotionsofak-automatonand

第1页下一页