Search

• < Previous
• 1
• Next >

---

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

---

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

---

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

---

Tree Languages Defined in First-Order Logic with One Quantifier Alternation

Mikolaj Bojanczyk ; Luc Segoufin.

We study tree languages that can be defined in \Delta_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a first-order formula whose quantifier prefix is . For the quantifier free part we consider two signatures, either the&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;]

---

Enumerating Answers to First-Order Queries over Databases of Low Degree

Arnaud Durand ; Nicole Schweikardt ; Luc Segoufin.

A class of relational databases has low degree if for all $\delta>0$, all but finitely many databases in the class have degree at most $n^{\delta}$, where $n$ is the size of the database. Typical examples are databases of bounded degree or of degree bounded by $\log n$. It is known that over a&nbsp;[&hellip;]

---

Tameness and the power of programs over monoids in DA

Nathan Grosshans ; Pierre Mckenzie ; Luc Segoufin.

The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural&nbsp;[&hellip;]

---