Search

• < Previous
• 1
• Next >

---

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;]

---

Register Automata with Extrema Constraints, and an Application to Two-Variable Logic

Szymon Toruńczyk ; Thomas Zeume.

We introduce a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain in its registers, and can compare those values to the suprema and infima of register values in subtrees. We show that the emptiness problem for&nbsp;[&hellip;]

---