On the Restraining Power of Guards

DOI10.2307/2586808MaRDI QIDQ4948538zbMATH OpenOpenAlexFDO

Authors 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

EXPTIME-completefinite model propertyguarded fragments of first-order logicloosely guarded fragment of first-order logicsatisfiability problems

Mathematics Subject Classification ID

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

Recommendations

• Guarded fragments with constants
• Guarded negation
• Guards, bounds, and generalized semantics
• The guarded fragment with transitive guards
• Guarded negation

Cites work

• Dominoes and the complexity of subclasses of logical theories
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• Extending partial isomorphisms of graphs
• Extending partial isomorphisms on finite structures
• Finite algebras of relations are representable on finite sets
• scientific article; zbMATH DE number 986406 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 1059246 (Why is no real title available?)
• Modal languages and bounded fragments of predicate logic
• On languages with two variables
• On logics with two variables
• On Preservation Theorems for Two-Variable Logic
• On the Decision Problem for Two-Variable First-Order Logic
• Remarks on Berger's paper on the domino problem
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Undecidability results on two-variable logics

Cited in

(96)

• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Hyperresolution for guarded formulae
• Resolution-based decision procedures for the universal theory of some classes of distributive lattices with operators
• Decidable fragments of first-order temporal logics
• Loosely guarded fragment of first-order logic has the finite model property
• Interpolation and definability in guarded fragments
• Propositional epistemic logics with quantification over agents of knowledge
• Guarded fixed point logics and the monadic theory of countable trees.
• The finite graph problem for two-way alternating automata.
• The guarded fragment with transitive guards
• Modal and guarded characterisation theorems over finite transition systems
• On logics with two variables
• Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment
• Logical separability of labeled data examples under ontologies
• A simple logic of functional dependence
• A prover dealing with nominals, binders, transitivity and relation hierarchies
• Propositional epistemic logics with quantification over agents of knowledge (an alternative approach)
• A tableau based decision procedure for an expressive fragment of hybrid logic with binders, converse and global modalities
• Completeness and decidability of general first-order logic (with a detour through the guarded fragment)
• A survey on temporal logics for specifying and verifying real-time systems
• Resolution with order and selection for hybrid logics
• An event-based fragment of first-order logic over intervals
• 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
• Complexity of monodic guarded fragments over linear and real time
• Computational complexity of theories of a binary predicate with a small number of variables
• Decidable fragments of first-order modal logics
• A logical approach to data-aware automated sequence generation
• Small substructures and decidability issues for first-order logic with two variables
• Recent advances in Datalog^
• A Tableaux Based Decision Procedure for a Broad Class of Hybrid Formulae with Binders
• Combining theories: the Ackerman and guarded fragments
• Rewriting guarded existential rules into small Datalog programs
• Querying the unary negation fragment with regular path expressions
• Interpolation for extended modal languages
• The two-variable fragment with counting and equivalence
• Terminating Tableaux for Hybrid Logic with the Difference Modality and Converse
• Repetitions and permutations of columns in the semijoin algebra
• Description Logics
• Finite satisfiability for guarded fixpoint logic
• scientific article; zbMATH DE number 1950259 (Why is no real title available?)
• scientific article; zbMATH DE number 1989656 (Why is no real title available?)
• The Range of Modal Logic
• SOME MODEL THEORY OF GUARDED NEGATION
• Datalog and Its Extensions for Semantic Web Databases
• Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures
• Bisimulation quantifiers and uniform interpolation for guarded first order logic
• Disjunctive Datalog with existential quantifiers: semantics, decidability, and complexity issues
• First-order resolution methods for modal logics
• scientific article; zbMATH DE number 1405457 (Why is no real title available?)
• Guarded Ontology-Mediated Queries
• Semiring Provenance for Guarded Logics
• Adding Guarded Constructions to the Syllogistic
• Additive first-order queries
• One-dimensional guarded fragments
• Finite satisfiability of unary negation fragment with transitivity
• The fluted fragment revisited
• The triguarded fragment of first-order logic
• On the decidability of elementary modal logics
• Effective interpolation and preservation in guarded logics
• Complexity of two-variable logic on finite trees
• Automated Reasoning
• Finite-Variable Logics Do Not Have Weak Beth Definability Property
• Omitting types for finite variable fragments and complete representations of algebras
• Logics in Artificial Intelligence
• Uniform Constraint Satisfaction Problems and Database Theory
• Guarded negation
• Guarded negation
• Tolerance logic
• Games and Lindström theorems
• Epistemic logics with quantification over epistemic operators: decidability and expressiveness
• Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино?
• Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
• A modal loosely guarded fragment of second-order propositional modal logic
• Uniform guarded fragments
• Complexity of hybrid logics over transitive frames
• How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\)
• Reasoning formally about database queries and updates
• On two-variable guarded fragment logic with expressive local Presburger constraints
• Craig interpolation for decidable first-order fragments
• Finite model property and bisimulation for LFD
• Guarded hybrid team logics
• The adjacent fragment and Quine's limits of decision
• Craig interpolation for decidable first-order fragments
• Decidability of querying first-order theories via countermodels of finite width
• The triguarded fragment with transitivity
• Fluted logic with counting
• On homogeneous models of fluted languages
• Superintuitionistic predicate logics of linear Kripke frames: undecidability with two individual variables
• Color refinement for relational structures
• First-order temporal verification in practice
• On the complexity of the two-variable guarded fragment with transitive guards
• On the complexity of division and set joins in the relational algebra

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

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