Search

• < Previous
• 1
• 2
• 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.

---

Tree Languages Defined in First-Order Logic with One Quantifier Alternation

Mikolaj Bojanczyk ; Luc Segoufin.

We study tree languages that can be defined in \Delta_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a first-order formula whose quantifier prefix is . For the quantifier free part we consider two signatures, either the&nbsp;[&hellip;]

---