Search

• < Previous
• 1
• Next >

---

Simulation Problems Over One-Counter Nets

Piotr Hofman ; Slawomir Lasota ; Richard Mayr ; Patrick Totzke.

One-counter nets (OCN) are finite automata equipped with a counter that can store non-negative integer values, and that cannot be tested for zero. Equivalently, these are exactly 1-dimensional vector addition systems with states. We show that both strong and weak simulation preorder on OCN are&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;]

---

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

---