Search

• < Previous
• 1
• Next >

---

Visibly Tree Automata with Memory and Constraints

Hubert Comon-Lundh ; Florent Jacquemard ; Nicolas Perrin.

Tree automata with one memory have been introduced in 2001. They generalize both pushdown (word) automata and the tree automata with constraints of equality between brothers of Bogaert and Tison. Though it has a decidable emptiness problem, the main weakness of this model is its lack of good closure&nbsp;[&hellip;]

---

Decidable Classes of Tree Automata Mixing Local and Global Constraints Modulo Flat Theories

Luis Barguñó ; Carles Creus ; Guillem Godoy ; Florent Jacquemard ; Camille Vacher.

We define a class of ranked tree automata TABG generalizing both the tree automata with local tests between brothers of Bogaert and Tison (1992) and with global equality and disequality constraints (TAGED) of Filiot et al. (2007). TABG can test for equality and disequality modulo a given flat&nbsp;[&hellip;]

---

FO2(<,+1,~) on data trees, data tree automata and branching vector addition systems

Florent Jacquemard ; Luc Segoufin ; Jerémie Dimino.

A data tree is an unranked ordered tree where each node carries a label from a finite alphabet and a datum from some infinite domain. We consider the two variable first order logic FO2(<,+1,~) over data trees. Here +1 refers to the child and the next sibling relations while < refers to the&nbsp;[&hellip;]

---