Résumé | In algebraic language theory, certain algebraic objects, primarily monoids, are used to analyze the structure of word and tree languages. A fundamental result states that a language of finite words is regular iff it is accepted by a finite monoid. Subclasses of regular languages, such as star-free languages, correspond to natural classes of finite monoids. Most prominently, Schutzenberger, McNaughton, and Papert showed that a regular language is first-order definable iff it is star-free iff it is accepted by an aperiodic monoid.
The study of data languages -- languages over an infinite alphabet -- is motivated by applications in verification and XML processing. In this talk I will report about a recent extension of algebraic techniques to the study of data languages. After a quick overview of some basic concepts related to data languages I will focus on an interesting class of infinite monoids, finite orbit data monoids, which has been recently proposed by Bojanczyk. I will then present a logic, called rigidly guarded monadic second-order logic, that defines exactly the languages recognized by finite orbit data monoids. A theorem akin to Schutzenberger's Theorem also carries over to data languages: one shows that a data language is definable in rigidly guarded first-order logic iff it is recognized by an aperiodic orbit finite data monoid. |