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

---

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

---

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

---