Search

• < Previous
• 1
• Next >

---

A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra

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&nbsp;[&hellip;]

---

Scalar and Vectorial mu-calculus with Atoms

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&nbsp;[&hellip;]

---

Definable isomorphism problem

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&nbsp;[&hellip;]

---