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

---