On the Restraining Power of Guards

DOI10.2307/2586808zbMath0958.03027OpenAlexW1483892218MaRDI QIDQ4948538

Erich Grädel

Publication date: 22 March 2001

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2586808

zbMATH Keywords

finite model propertysatisfiability problemsEXPTIME-completeguarded fragments of first-order logicloosely guarded fragment of first-order logic

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (72)

On the Decidability of Elementary Modal Logics ⋮ Effective Interpolation and Preservation in Guarded Logics ⋮ The finite graph problem for two-way alternating automata. ⋮ Complexity of Two-Variable Logic on Finite Trees ⋮ The guarded fragment with transitive guards ⋮ A Logical Approach to Data-Aware Automated Sequence Generation ⋮ The Range of Modal Logic ⋮ Modal and guarded characterisation theorems over finite transition systems ⋮ Combining Theories: The Ackerman and Guarded Fragments ⋮ Unnamed Item ⋮ The two‐variable fragment with counting and equivalence ⋮ First-order temporal verification in practice ⋮ Small substructures and decidability issues for first-order logic with two variables ⋮ On the complexity of the two-variable guarded fragment with transitive guards ⋮ Querying the Unary Negation Fragment with Regular Path Expressions. ⋮ On the complexity of division and set joins in the relational algebra ⋮ Games and Lindström theorems ⋮ A survey on temporal logics for specifying and verifying real-time systems ⋮ Epistemic logics with quantification over epistemic operators: decidability and expressiveness ⋮ Finite-Variable Logics Do Not Have Weak Beth Definability Property ⋮ Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. ⋮ Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments ⋮ Hyperresolution for guarded formulae ⋮ A modal loosely guarded fragment of second-order propositional modal logic ⋮ Uniform guarded fragments ⋮ Complexity of hybrid logics over transitive frames ⋮ Resolution with order and selection for hybrid logics ⋮ An event-based fragment of first-order logic over intervals ⋮ Finite satisfiability for guarded fixpoint logic ⋮ Recent Advances in Datalog$$^\pm $$ ⋮ Computational complexity of theories of a binary predicate with a small number of variables ⋮ On logics with two variables ⋮ Terminating Tableaux for Hybrid Logic with the Difference Modality and Converse ⋮ Omitting types for finite variable fragments and complete representations of algebras ⋮ Resolution-based decision procedures for the universal theory of some classes of distributive lattices with operators ⋮ Bisimulation quantifiers and uniform interpolation for guarded first order logic ⋮ Propositional epistemic logics with quantification over agents of knowledge ⋮ A Tableaux Based Decision Procedure for a Broad Class of Hybrid Formulae with Binders ⋮ A simple logic of functional dependence ⋮ SOME MODEL THEORY OF GUARDED NEGATION ⋮ Datalog and Its Extensions for Semantic Web Databases ⋮ Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues ⋮ Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures ⋮ First-Order Resolution Methods for Modal Logics ⋮ Decidable fragments of first-order modal logics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ THE FLUTED FRAGMENT REVISITED ⋮ Guarded Negation ⋮ Guarded Negation ⋮ Interpolation for extended modal languages ⋮ Repetitions and permutations of columns in the semijoin algebra ⋮ A prover dealing with nominals, binders, transitivity and relation hierarchies ⋮ Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment ⋮ Description Logics ⋮ Propositional epistemic logics with quantification over agents of knowledge (an alternative approach) ⋮ Guards, bounds, and generalized semantics ⋮ Guarded fragments with constants ⋮ Deciding regular grammar logics with converse through first-order logic ⋮ The semijoin algebra and the guarded fragment ⋮ A guarded fragment for abstract state machines ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Logical separability of labeled data examples under ontologies ⋮ Decidable fragments of first-order temporal logics ⋮ Complexity of monodic guarded fragments over linear and real time ⋮ Guarded fixed point logics and the monadic theory of countable trees. ⋮ Guarded Ontology-Mediated Queries ⋮ Semiring Provenance for Guarded Logics ⋮ Adding Guarded Constructions to the Syllogistic ⋮ A tableau based decision procedure for an expressive fragment of hybrid logic with binders, converse and global modalities

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dominoes and the complexity of subclasses of logical theories
• Extending partial isomorphisms of graphs
• Modal languages and bounded fragments of predicate logic
• Undecidability results on two-variable logics
• Extending partial isomorphisms on finite structures
• On logics with two variables
• Remarks on Berger's paper on the domino problem
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• On languages with two variables
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Finite algebras of relations are representable on finite sets
• On Preservation Theorems for Two-Variable Logic
• On the Decision Problem for Two-Variable First-Order Logic

This page was built for publication: On the Restraining Power of Guards