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

---

Unary negation

Luc Segoufin ; Balder ten Cate.

We study fragments of first-order logic and of least fixed point logic that allow only unary negation: negation of formulas with at most one free variable. These logics generalize many interesting known formalisms, including modal logic and the $\mu$-calculus, as well as conjunctive queries and&nbsp;[&hellip;]

---

Deciding definability in FO2(<h,<v) on trees

Thomas Place ; Luc Segoufin.

We provide a decidable characterization of regular forest languages definable in FO2(<h,<v). By FO2(<h,<v) we refer to the two variable fragment of first order logic built from the descendant relation and the following sibling relation. In terms of expressive power it corresponds to a fragment of&nbsp;[&hellip;]

---

Datalog Rewritings of Regular Path Queries using Views

Nadime Francis ; Luc Segoufin ; Cristina Sirangelo.

We consider query answering using views on graph databases, i.e. databases structured as edge-labeled graphs. We mainly consider views and queries specified by Regular Path Queries (RPQ). These are queries selecting pairs of nodes in a graph database that are connected via a path whose sequence of&nbsp;[&hellip;]

---

Piecewise testable tree languages

Mikołaj Bojańczyk ; Luc Segoufin ; Howard Straubing.

This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination of Sigma_1 sentences if and only if its&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;]

---