3 results
Gabriele Puppis ; Thomas Colcombet ; 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 […]
Published on September 17, 2015
Thomas Colcombet ; Daniela Petrişan.
In this paper we regard languages and their acceptors - such as deterministic or weighted automata, transducers, or monoids - as functors from input categories that specify the type of the languages and of the machines to categories that specify the type of outputs. Our results are as follows: A) […]
Published on March 23, 2020
Thomas Colcombet ; Christof Löding.
We consider a new kind of interpretation over relational structures: finite sets interpretations. Those interpretations are defined by weak monadic second-order (WMSO) formulas with free set variables. They transform a given structure into a structure with a domain consisting of finite sets of […]
Published on May 4, 2007