Diego Figueira

Reasoning on words and trees with data

On decidable automata on data words and data trees

in relation to satisfiability of LTL and XPath.

in relation to satisfiability of LTL and XPath.

Salle de Conférences, Pavillon des Jardins,

École Normale Supérieure de Cachan.

- Stéphane DEMRI, advisor
- Georg GOTTLOB, reviewer
- Ranko LAZIĆ, examiner
- Leonid LIBKIN, examiner
- Carsten LUTZ , examiner
- Thomas SCHWENTICK, reviewer
- Luc SEGOUFIN, advisor

A data word (resp. a data tree) is a finite word (resp. tree) whose every position carries a letter from a finite alphabet and a *datum* form an infinite domain. In this thesis we investigate automata and logics for data words and data trees with decidable reasoning problems: we focus on the emptiness problem in the case of automata, and the satisfiability problem in the case of logics.

On data words, we present a decidable extension of the model of alternating register automata studied by Demri and Lazić. Further, we show the decidability of the satisfiability problem for the linear-time temporal logic on data words LTL(X,F,U) (studied by Demri and Lazić) extended with quantification over data values. We also prove that the lower bounds of non-primitive recursiveness shown by Demri and Lazić for LTL(X,F) carry over to LTL(F).

On data trees, we consider three decidable automata models with different characteristics. We first introduce the Downward Data automaton (DD automata). Its execution consists in a transduction of the finite labeling of the tree, and a verification of data properties for every subtree of the transduced tree. This model is closed under boolean operations, but the tests it can make on the order of the siblings is very limited. Its emptiness problem is in 2ExpTime. On the contrary, the other two automata models we introduce have an emptiness problem with a non-primitive recursive complexity, and are closed under intersection and union, but not complementation. They are both alternating automata with one register to store and compare data values. The automata class ATRA(guess,spread) extends the top-down automata ATRA of Jurdziński and Lazić. We exhibit similar decidable extensions as the one showed in the case of data words. This class can test for any regular tree language, in contrast to DD automata. Finally, we consider a bottom-up alternating tree automaton with one register (called BUDA). Although BUDA are one-way, they can test data properties by navigating the tree in both directions: upward and downward. In opposition to ATRA(guess,spread), this automaton cannot test for properties on the sequence of siblings (like, for example, the order in which labels appear).

All these three models have connections with the logic XPath: a logic conceived for XML documents, which can be seen as data trees. Through the aforementioned automata we show that the satisfiability of three natural fragments of XPath are decidable. These fragments are: *downward* XPath, where navigation can only be done by child and descendant axes; *forward* XPath, where navigation also contains the next sibling axis and its transitive closure; and *vertical* XPath, whose navigation consists in the child, descendant, parent and ancestor axes. Whereas downward XPath is ExpTime-complete, forward and vertical XPath have non-primitive recursive lower bounds.

The latest version of the thesis can be found here.

The slides that were used in the defence are here.

Back to Diego Figueira's homepage.

- Private Pages
- Page maintained by Webmaster.