Recognition: unknown
Logics with rigidly guarded data tests
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Minimization of Streaming Transducers
General criteria for minimal models of streaming transducers are established, yielding effective minimization for variants of streaming string-to-tree transducers that build terms at leaves or roots.
-
Minimization of Streaming Transducers
General criteria for the existence of minimal models of streaming transducers are provided, with effective minimization results for variants of streaming string-to-tree transducers.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.