TL;DR
This paper introduces and analyzes "Unary Negation" (UNFO) and its extension with fixpoints (UNFP), fragments of first-order logic where negation is restricted to formulas with at most one free variable. They demonstrate that these logics are surprisingly expressive, capturing many existing formalisms, and are robustly decidable, with well-behaved model-theoretic properties like Craig interpolation.
What Problem Does This Paper Address?
The paper builds on the observation that many decidable logics (like modal logic) share properties such as the tree model property, interpretability in MSO, and the finite model property. The authors aim to generalize these properties to larger fragments of first-order logic (FO) beyond existing ones like the Guarded Fragment (GFO). They introduce UNFO and UNFP, which restrict negation to formulas with a single free variable. This restriction is orthogonal to GFO's "guarding" of quantifiers and allows for the expression of concepts not easily captured by GFO, while retaining desirable decidability and model-theoretic properties. The core problem is to understand the expressive power, decidability, and model-theoretic behavior of these new fragments.
Methods
The authors employ a combination of techniques from logic and theoretical computer science:
- Model-Theoretic Characterization: They introduce "UN-bisimulations" and "UN-homomorphisms" as generalization of bisimulations for modal logic and guarded bisimulations for GFO. These are used to characterize the expressive power of UNFO and UNFP, showing that UNFO formulas are precisely those preserved under UN-homomorphisms.
- Reduction to Known Logics: For decidability and complexity results, they reduce UNFP to the two-way μ-calculus and its simpler fragment, "simple UNFP" (sUNFP). This allows them to leverage existing decidability results for the μ-calculus.
- Complexity Analysis: They use standard techniques for establishing complexity bounds, including reductions to known complete problems and the construction of specific types of models (e.g., acyclic models).
- Proof Techniques: Standard proof techniques in logic, such as induction on formula structure, are used extensively.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Unary Negation is Powerful: The restriction of negation to single-variable formulas is surprisingly expressive, allowing UNFO to capture formalisms like Core XPath and certain description logic query answering problems.
- Robust Decidability: UNFO and UNFP are shown to be "robustly decidable," meaning they possess the tree model property, are interpretable in MSO, and have the finite model property (for UNFO). This makes them suitable for applications where decidability is crucial.
- Model-Theoretic Niceties: UNFO enjoys strong model-theoretic properties like Craig interpolation and the Beth property, which are known to fail for standard k-variable fragments of FO. This suggests UNFO is a well-behaved fragment from a logical perspective.
- Orthogonal to Guarded Fragments: UNFO and GFO are incomparable in expressive power, meaning each can express properties the other cannot. This highlights UNFO as a distinct and valuable generalization of modal logic.
- Complexity Trade-offs: While UNFO and UNFP are decidable, their model checking problems are computationally challenging, with UNFO being PNP[O(log n)]-complete and UNFP being in NPNP ∩ coNPNP.
Key Results
- Satisfiability: Satisfiability for UNFO and UNFP is 2ExpTime-complete.
- Finite Satisfiability: Finite satisfiability for UNFP is decidable.
- Model Checking:
- UNFO model checking is PNP[O(log n)]-complete.
- UNFP model checking is in NPNP ∩ coNPNP and PNP-hard.
- Model Properties:
- UNFO has the finite model property.
- UNFP has the tree-like model property.
- Logical Properties: UNFO has Craig Interpolation and the Projective Beth Property.
Limitations and Future Work
- Undecidable Extensions: The paper shows that extending UNFO with inequalities or negative relational atomic formulas leads to undecidability. Similarly, extending UNFP with non-monadic fixed point operators also results in undecidability.
- Incomparability with GFO: While UNFO and GFO are incomparable, the authors suggest future work in developing a logic that unifies their strengths, potentially by exploring "guarded negation fragments."
- Model Checking Complexity Gap: For UNFP, there's a gap between the upper bound (NPNP ∩ coNPNP) and the lower bound (PNP-hard) for model checking, similar to open problems for the μ-calculus.
- Finite Structures: While many results are stated for arbitrary structures, the authors mention that analogous results for finite structures often follow and will be detailed in a journal version.
Summary updated