Segoufin, Luc and Cate, Balder ten - Unary negation

lmcs:792 - Logical Methods in Computer Science, September 24, 2013, Volume 9, Issue 3
Unary negation

Authors: Segoufin, Luc and Cate, Balder ten

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 monadic Datalog. We show that satisfiability and finite satisfiability are decidable for both fragments, and we pinpoint the complexity of satisfiability, finite satisfiability, and model checking. We also show that the unary negation fragment of first-order logic is model-theoretically very well behaved. In particular, it enjoys Craig Interpolation and the Projective Beth Property.


Source : oai:arXiv.org:1309.2069
DOI : 10.2168/LMCS-9(3:25)2013
Volume: Volume 9, Issue 3
Published on: September 24, 2013
Submitted on: January 16, 2013
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 128 times.
This article's PDF has been downloaded 90 times.