Guarded Negation

DOI10.1145/2701414zbMath1333.68133OpenAlexW2341631904MaRDI QIDQ5890544

Luc Segoufin, Balder ten Cate, Vince Bárány

Publication date: 24 March 2016

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2701414

zbMATH Keywords

first-order logicdecidabilitysatisfiabilityguarded fragmentnegationfixpoint logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (15)

On Monotonic Determinacy and Rewritability for Recursive Queries and Views ⋮ Querying the Unary Negation Fragment with Regular Path Expressions. ⋮ Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments ⋮ SOME MODEL THEORY OF GUARDED NEGATION ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Statistical \(\mathcal{EL}\) is \textsc{ExpTime}-complete ⋮ How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\) ⋮ Craig interpolation for decidable first-order fragments ⋮ Evaluating Datalog via tree automata and cycluits ⋮ Propositional epistemic logics with quantification over agents of knowledge (an alternative approach) ⋮ Logical separability of labeled data examples under ontologies ⋮ Guarded Ontology-Mediated Queries ⋮ Semiring Provenance for Guarded Logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite satisfiability for guarded fixpoint logic
• Expressive completeness through logically tractable models
• Modal languages and bounded fragments of predicate logic
• Undecidability results on two-variable logics
• On the complexity of single-rule datalog queries.
• Loosely guarded fragment of first-order logic has the finite model property
• The finite graph problem for two-way alternating automata.
• Modal and guarded characterisation theorems over finite transition systems
• Unary negation
• Rewriting Guarded Negation Queries
• Games and Model Checking for Guarded Logics
• Query evaluation via tree-decompositions
• On languages with two variables
• Fixed Point Logics
• On the Restraining Power of Guards
• Querying the Guarded Fragment
• Guarded Negation

This page was built for publication: Guarded Negation