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.

---

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

---