5 results
Mikołaj Bojańczyk ; Bartek Klin ; Sławomir Lasota.
We study languages over infinite alphabets equipped with some structure that can be tested by recognizing automata. We develop a framework for studying such alphabets and the ensuing automata theory, where the key role is played by an automorphism group of the alphabet. In the process, we generalize […]
Published on August 15, 2014
Bartek Klin ; Mateusz Łełyk.
We study an extension of modal $\mu$-calculus to sets with atoms and we study its basic properties. Model checking is decidable on orbit-finite structures, and a correspondence to parity games holds. On the other hand, satisfiability becomes undecidable. We also show expressive limitations of […]
Published on October 29, 2019
Mikołaj Bojańczyk ; Bartek Klin.
$\omega$-clones are multi-sorted structures that naturally emerge as algebras for infinite trees, just as $\omega$-semigroups are convenient algebras for infinite words. In the algebraic theory of languages, one hopes that a language is regular if and only if it is recognized by an algebra that is […]
Published on November 29, 2019
Khadijeh Keshvardoost ; Bartek Klin ; Sławomir Lasota ; Joanna Ochremiak ; Szymon Toruńczyk.
We investigate the isomorphism problem in the setting of definable sets (equivalent to sets with atoms): given two definable relational structures, are they related by a definable isomorphism? Under mild assumptions on the underlying structure of atoms, we prove decidability of the problem. The core […]
Published on December 11, 2019
Bartek Klin ; Jurriaan Rot.
We use modal logic as a framework for coalgebraic trace semantics, and show the flexibility of the approach with concrete examples such as the language semantics of weighted, alternating and tree automata, and the trace semantics of generative probabilistic systems. We provide a sufficient condition […]
Published on April 27, 2017