Gabriele Puppis ; Thomas Colcombet ; Clemens Ley - Logics with rigidly guarded data tests

lmcs:1586 - Logical Methods in Computer Science, September 17, 2015, Volume 11, Issue 3 - https://doi.org/10.2168/LMCS-11(3:10)2015
Logics with rigidly guarded data testsArticle

Authors: Gabriele Puppis ORCID; Thomas Colcombet ORCID; Clemens Ley

    The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words. Following Buchi's approach, we introduce a variant of monadic second-order logic with data equality tests that captures precisely the data languages recognizable by orbit finite data monoids. We also establish, following this time the approach of Schutzenberger, McNaughton and Papert, that the first-order fragment of this logic defines exactly the data languages recognizable by aperiodic orbit finite data monoids. Finally, we consider another variant of the logic that can be interpreted over generic structures with data. The data languages defined in this variant are also recognized by unambiguous finite memory automata.


    Volume: Volume 11, Issue 3
    Published on: September 17, 2015
    Submitted on: October 20, 2014
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science

    3 Documents citing this article

    Consultation statistics

    This page has been seen 1139 times.
    This article's PDF has been downloaded 390 times.