December Final version for proceedings of LATA'09

Lutz Strassburger

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

Sujets

• École polytechnique
• Straßburger

Informations

• Publié par: chaeh
• Nombre de lectures: 8
• Langue: English

Extrait

December17,2008—FinalversionforproceedingsofLATA’09 AKleeneTheoremforForestLanguages LutzStraßburger INRIASaclay–I ˆ le-de-France—E ´ quipe-projetParsifal E ´ colePolytechnique—LIX—RuedeSaclay—91128PalaiseauCedex—France http://www.lix.polytechnique.fr/~lutz Abstract.Thispaperproposesanalternativeapproachtothestandard notionofrational(orregular)expressionfortreelanguages.Themain differenceisthatinthenewnotionwehaveonlyoneconcatenationop- erationandonlyonestar-operation,insteadofmanydifferentones.This isachievedbyconsideringforestsinsteadoftreesoverarankedalpha- bet,or,algebraiclyspeaking,byconsideringcartesiancategoriesinstead ofterm-algebras.Themainresultisthatinthefreecartesiancategory therationallanguagesandtherecognizablelanguagescoincide.Forthe constructionoftherationalexpressionforarecognizablelanguageitis notnecessarytoextendthealphabet.Weonlyuseoperationsthatcan bedefinedwiththealgebraicstructureprovidedbycartesiancategories. 1Introduction Kleene’stheoremonthecoincidenceoftherationalandtherecognizablelan- guagesinafreemonoid[Kle56]isconsideredtobeoneofthecornerstonesof theoreticalcomputerscience.Althoughitdoesnotholdineverymonoid[Eil76], ithasbeengeneralizedinseveraldirections,e.g.,[Och85,Sch61,DG99].Thatcher andWrightpresentedin[TW68]asimilarresultfortreelanguages.Inrecent years,recognizabletreelanguageshavereceivedincreasedattentionbecausethey formafoundationforXMLschemasforexpressingsemi-structureddata(e.g., [Nev02,MN07,CDG + 07]).InthispaperIwillonlyconsiderrankedtreesandtu- plesofrankedtrees,whichIcallforeststodistinguishthemfromhedges[Cou89] whicharesequencesofunrankedtrees[CDG + 07]. Therecognizabletreelanguagesaredefinedbymeansoffinite-statetreeau- tomata(fsta),whichareageneralizationofordinaryfinitestateautomata(fsa) overwords.WhileanfsaworksonanalphabetA,anfstaworksonaranked alphabetΣ,i.e.,everysymbolinΣisequippedwitharank,whichisanatural number.ThelanguagerecognizedbyanfstaisasubsetofthesetT Σ ofall finitetreesoverΣ.Therunningexampleforthispaperistherankedalphabet Σ= { σ,γ,α } ,whereσhasrank2,γhasrank1,andαhasrank0.Letus defineanfstaAwithtwostatespandf,wherefisafinalstate.Observethat (contrarytofsaonwords)therearenoinitialstates.Usuallythebehaviourof anfstaisrepresentedassetofrulesofatermrewritingsystem[GS97].Inthe example,letthebehaviourofAbedescribedbytherules α → p,α → f,γ(p) → p,σ(p,f) → f.