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.

---

Automata theory in nominal sets

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

We study languages over infinite alphabets equipped with some structure that can be tested by recognizing automata. We develop a framework for studying such alphabets and the ensuing automata theory, where the key role is played by an automorphism group of the alphabet. In the process, we generalize&nbsp;[&hellip;]

---

Determinisability of register and timed automata

Lorenzo Clemente ; Sławomir Lasota ; Radosław Piórkowski.

The deterministic membership problem for timed automata asks whether the timed language given by a nondeterministic timed automaton can be recognised by a deterministic timed automaton. An analogous problem can be stated in the setting of register automata. We draw the complete&nbsp;[&hellip;]

---