Skip to main content

On the use of guards for logics with data

Thomas Colcombet‚ Clemens Ley and Gabriele Puppis


The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words. Following Büchi’s approach, we introduce the new logic ‘rigidly guarded MSO’ and show that the data languages definable in this logic are exactly those recognizable by orbit finite data monoids. We also establish, following this time the approach of Schützenberger, McNaughton and Papert, that the first-order variant of this logic defines exactly the languages recognizable by aperiodic orbit finite data monoids. Finally, we give a variant of the logic that captures the larger class of languages recognized by non-deterministic finite memory automata.

International Symposium on Mathematical Foundations Of Computer Science