Guarded negation

DOI10.1145/2701414MaRDI QIDQ5890544zbMATH OpenOpenAlexFDO

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

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

decidabilityfirst-order logicnegationsatisfiabilityguarded fragmentfixpoint logic

Mathematics Subject Classification ID

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

Recommendations

• Guarded negation
• SOME MODEL THEORY OF GUARDED NEGATION
• On the Restraining Power of Guards
• The complexity of boundedness for guarded logics
• A Step Up in Expressiveness of Decidable Fixpoint Logics

Cites work

• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 1303729 (Why is no real title available?)
• scientific article; zbMATH DE number 1860675 (Why is no real title available?)
• Expressive completeness through logically tractable models
• Finite satisfiability for guarded fixpoint logic
• Fixed Point Logics
• Games and model checking for guarded logics
• Guarded negation
• Loosely guarded fragment of first-order logic has the finite model property
• Modal and guarded characterisation theorems over finite transition systems
• Modal languages and bounded fragments of predicate logic
• On languages with two variables
• On the Restraining Power of Guards
• On the complexity of single-rule datalog queries.
• Query evaluation via tree-decompositions
• Querying the Guarded Fragment
• Rewriting Guarded Negation Queries
• The finite graph problem for two-way alternating automata.
• Unary negation
• Undecidability results on two-variable logics

Cited in

(22)

• Propositional epistemic logics with quantification over agents of knowledge (an alternative approach)
• Guarded fixed point logics and the monadic theory of countable trees.
• Unary negation
• How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\)
• scientific article; zbMATH DE number 7561661 (Why is no real title available?)
• Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
• scientific article; zbMATH DE number 7561660 (Why is no real title available?)
• Unary negation
• The complexity of boundedness for guarded logics
• Querying the unary negation fragment with regular path expressions
• Statistical \(\mathcal{EL}\) is \textsc{ExpTime}-complete
• On Monotonic Determinacy and Rewritability for Recursive Queries and Views
• SOME MODEL THEORY OF GUARDED NEGATION
• Craig interpolation for decidable first-order fragments
• Semiring Provenance for Guarded Logics
• Guarded Ontology-Mediated Queries
• scientific article; zbMATH DE number 7566070 (Why is no real title available?)
• Guarded negation
• Guards, bounds, and generalized semantics
• Evaluating Datalog via tree automata and cycluits
• scientific article; zbMATH DE number 1989656 (Why is no real title available?)
• Logical separability of labeled data examples under ontologies

This page was built for publication: Guarded negation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890544)