Algebraic Data Language Theory
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. A class of infinite monoids, finite-orbit data monoids, has been proposed by Bojanczyk. We present a logic, called rigidly-guarded monadic second order logic, that defines exactly the languages accepted by finite-orbit data monoids. A theorem akin to Schützenberger's Theorem also carries over to data languages: We show that a language is definable in rigidly-guarded first order logic iff it is accepted by an aperiodic data monoid.