Search

• < Previous
• 1
• Next >

---

First-order queries on classes of structures with bounded expansion

Wojtek Kazana ; Luc Segoufin.

We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree, bounded treewidth and exclusion of at least one minor. It was known that over a class of databases with bounded&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;]

---