December Final version for proceedings of LATA
12 Pages
English
Gain access to the library to view online
Learn more

December Final version for proceedings of LATA'09

-

Gain access to the library to view online
Learn more
12 Pages
English

Description

Niveau: Supérieur
December 17, 2008 — Final version for proceedings of LATA'09 A Kleene Theorem for Forest Languages Lutz Straßburger INRIA Saclay – Ile-de-France — Equipe-projet Parsifal Ecole Polytechnique — LIX — Rue de Saclay — 91128 Palaiseau Cedex — France Abstract. This paper proposes an alternative approach to the standard notion of rational (or regular) expression for tree languages. The main difference is that in the new notion we have only one concatenation op- eration and only one star-operation, instead of many different ones. This is achieved by considering forests instead of trees over a ranked alpha- bet, or, algebraicly speaking, by considering cartesian categories instead of term-algebras. The main result is that in the free cartesian category the rational languages and the recognizable languages coincide. For the construction of the rational expression for a recognizable language it is not necessary to extend the alphabet. We only use operations that can be defined with the algebraic structure provided by cartesian categories. 1 Introduction Kleene's theorem on the coincidence of the rational and the recognizable lan- guages in a free monoid [Kle56] is considered to be one of the cornerstones of theoretical computer science. Although it does not hold in every monoid [Eil76], it has been generalized in several directions, e.g., [Och85,Sch61,DG99].

  • ranked trees

  • kleene star ?

  • alphabet ?

  • over ?

  • all trees

  • word languages

  • any cartesian

  • free ?-algebra

  • forests

  • also been


Subjects

Informations

Published by
Reads 8
Language English

Exrait

December17,2008—FinalversionforproceedingsofLATA’09AKleeneTheoremforForestLanguagesLutzStraßburgerINRIASaclayIˆle-de-FranceE´quipe-projetParsifalE´colePolytechniqueLIXRuedeSaclay91128PalaiseauCedexFrancehttp://www.lix.polytechnique.fr/~lutzAbstract.Thispaperproposesanalternativeapproachtothestandardnotionofrational(orregular)expressionfortreelanguages.Themaindifferenceisthatinthenewnotionwehaveonlyoneconcatenationop-erationandonlyonestar-operation,insteadofmanydifferentones.Thisisachievedbyconsideringforestsinsteadoftreesoverarankedalpha-bet,or,algebraiclyspeaking,byconsideringcartesiancategoriesinsteadofterm-algebras.Themainresultisthatinthefreecartesiancategorytherationallanguagesandtherecognizablelanguagescoincide.Fortheconstructionoftherationalexpressionforarecognizablelanguageitisnotnecessarytoextendthealphabet.Weonlyuseoperationsthatcanbedefinedwiththealgebraicstructureprovidedbycartesiancategories.1IntroductionKleene’stheoremonthecoincidenceoftherationalandtherecognizablelan-guagesinafreemonoid[Kle56]isconsideredtobeoneofthecornerstonesoftheoreticalcomputerscience.Althoughitdoesnotholdineverymonoid[Eil76],ithasbeengeneralizedinseveraldirections,e.g.,[Och85,Sch61,DG99].ThatcherandWrightpresentedin[TW68]asimilarresultfortreelanguages.Inrecentyears,recognizabletreelanguageshavereceivedincreasedattentionbecausetheyformafoundationforXMLschemasforexpressingsemi-structureddata(e.g.,[Nev02,MN07,CDG+07]).InthispaperIwillonlyconsiderrankedtreesandtu-plesofrankedtrees,whichIcallforeststodistinguishthemfromhedges[Cou89]whicharesequencesofunrankedtrees[CDG+07].Therecognizabletreelanguagesaredefinedbymeansoffinite-statetreeau-tomata(fsta),whichareageneralizationofordinaryfinitestateautomata(fsa)overwords.WhileanfsaworksonanalphabetA,anfstaworksonarankedalphabetΣ,i.e.,everysymbolinΣisequippedwitharank,whichisanaturalnumber.ThelanguagerecognizedbyanfstaisasubsetofthesetTΣofallfinitetreesoverΣ.TherunningexampleforthispaperistherankedalphabetΣ={σ,γ,α},whereσhasrank2,γhasrank1,andαhasrank0.LetusdefineanfstaAwithtwostatespandf,wherefisafinalstate.Observethat(contrarytofsaonwords)therearenoinitialstates.Usuallythebehaviourofanfstaisrepresentedassetofrulesofatermrewritingsystem[GS97].Intheexample,letthebehaviourofAbedescribedbytherulesαp,αf,γ(p)p,σ(p,f)f.