3 results
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