Search

• < Previous
• 1
• Next >

---

Graph Logics with Rational Relations

Pablo Barcelo ; Diego Figueira ; Leonid Libkin.

We investigate some basic questions about the interaction of regular and rational relations on words. The primary motivation comes from the study of logics for querying graph topology, which have recently found numerous applications. Such logics use conditions on paths expressed by regular languages&nbsp;[&hellip;]

---

Playing with Repetitions in Data Words Using Energy Games

Diego Figueira ; Anirban Majumdar ; M. Praveen.

We introduce two-player games which build words over infinite alphabets, and we study the problem of checking the existence of winning strategies. These games are played by two players, who take turns in choosing valuations for variables ranging over an infinite data domain, thus generating&nbsp;[&hellip;]

---

Bottom-up automata on data trees and vertical XPath

Diego Figueira ; Luc Segoufin.

A data tree is a finite tree whose every node carries a label from a finite alphabet and a datum from some infinite domain. We introduce a new model of automata over unranked data trees with a decidable emptiness problem. It is essentially a bottom-up alternating automaton with one register that can&nbsp;[&hellip;]

---