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

---

Lindstrom theorems for fragments of first-order logic

Johan van Benthem ; Balder ten Cate ; Jouko Vaananen.

Lindstr\"om theorems characterize logics in terms of model-theoretic conditions such as Compactness and the L\"owenheim-Skolem property. Most existing characterizations of this kind concern extensions of first-order logic. But on the other hand, many logics relevant to computer science are fragments&nbsp;[&hellip;]

---

Complete Axiomatizations of Fragments of Monadic Second-Order Logic on Finite Trees

Amélie Gheerbrant ; Balder ten Cate.

We consider a specific class of tree structures that can represent basic structures in linguistics and computer science such as XML documents, parse trees, and treebanks, namely, finite node-labeled sibling-ordered trees. We present axiomatizations of the monadic second-order logic (MSO), monadic&nbsp;[&hellip;]

---

Preservation theorems for Tarski's relation algebra

Bart Bogaerts ; Balder ten Cate ; Brett McLean ; Jan Van den Bussche.

We investigate a number of semantically defined fragments of Tarski's algebra of binary relations, including the function-preserving fragment. We address the question whether they are generated by a finite set of operations. We obtain several positive and negative results along these lines.&nbsp;[&hellip;]

---