Search

• < Previous
• 1
• Next >

---

First-order query evaluation on structures of bounded degree

Wojciech Kazana ; Luc Segoufin.

We consider the enumeration problem of first-order queries over structures of bounded degree. It was shown that this problem is in the Constant-Delaylin class. An enumeration problem belongs to Constant-Delaylin if for an input of size n it can be solved by: - an O(n) precomputation phase building&nbsp;[&hellip;]

---

A decidable characterization of locally testable tree languages

Thomas Place ; Luc Segoufin.

A regular tree language L is locally testable if membership of a tree in L depends only on the presence or absence of some fix set of neighborhoods in the tree. In this paper we show that it is decidable whether a regular tree language is locally testable. The decidability is shown for ranked trees&nbsp;[&hellip;]

---

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;]

---