Search

• < Previous
• 1
• Next >

---

An extension of data automata that captures XPath

Mikołaj Bojańczyk ; Sławomir Lasota.

We define a new kind of automata recognizing properties of data words or data trees and prove that the automata capture all queries definable in Regular XPath. We show that the automata-theoretic approach may be applied to answer decidability and expressibility questions for XPath.

---

Regular Separability of One Counter Automata

Wojciech Czerwiński ; Sławomir Lasota.

The regular separability problem asks, for two given languages, if there exists a regular language including one of them but disjoint from the other. Our main result is decidability, and PSpace-completeness, of the regular separability problem for languages of one counter automata without zero tests&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;]

---