Modal languages and bounded fragments of predicate logic

DOI10.1023/A:1004275029985zbMath0919.03013OpenAlexW1991981864MaRDI QIDQ1267082

J. F. A. K. van Benthem, Istvan Németi, Hajnalka Andréka

Publication date: 18 November 1998

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

Full work available at URL: https://doi.org/10.1023/a:1004275029985

zbMATH Keywords

interpolation modal logic decidability finite model property guarded fragment bounded quantification fragments of first-order logic

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items

Translation of first order formulas into ground formulas via a completion theory ⋮ The finite graph problem for two-way alternating automata. ⋮ The guarded fragment with transitive guards ⋮ Finite algebras of relations are representable on finite sets ⋮ Completeness and decidability of general first-order logic (with a detour through the guarded fragment) ⋮ On a new semantics for first-order predicate logic ⋮ A Logical Approach to Data-Aware Automated Sequence Generation ⋮ Modal and guarded characterisation theorems over finite transition systems ⋮ Combining Theories: The Ackerman and Guarded Fragments ⋮ Representing ontologies using description logics, description graphs, and rules ⋮ The mu-calculus and Model Checking ⋮ Changing a Semantics: Opportunism or Courage? ⋮ Unnamed Item ⋮ The two‐variable fragment with counting and equivalence ⋮ Automated theorem proving by resolution in non-classical logics ⋮ Small substructures and decidability issues for first-order logic with two variables ⋮ Conceptual logic programs ⋮ Model theoretical aspects of weakly aggregative modal logic ⋮ On the expressive power of semijoin queries ⋮ On the complexity of the two-variable guarded fragment with transitive guards ⋮ A general Lindström theorem for some normal modal logics ⋮ Towards more expressive ontology languages: the query answering problem ⋮ Open answer set programming for the semantic web ⋮ On the complexity of division and set joins in the relational algebra ⋮ Bisimulation invariant monadic-second order logic in the finite ⋮ A survey on temporal logics for specifying and verifying real-time systems ⋮ A brief history of Tarskian algebraic logic with new perspectives and innovations ⋮ On temporal logic versus Datalog ⋮ On updates of hybrid knowledge bases composed of ontologies and rules ⋮ Hyperresolution for guarded formulae ⋮ Uniform short proofs for classical theorems ⋮ Finite satisfiability for guarded fixpoint logic ⋮ Recent Advances in Datalog$$^\pm $$ ⋮ Unnamed Item ⋮ New perspectives in algebraic logic, from neat embeddings to Erdős graphs ⋮ Deciding expressive description logics in the framework of resolution ⋮ Pebble Games over Ordered Structural Abstractions ⋮ Resolution-based decision procedures for the universal theory of some classes of distributive lattices with operators ⋮ Linear Programming Tools for Analyzing Strategic Games of Independence-Friendly Logic and Applications ⋮ Bisimulation Invariant Monadic-Second Order Logic in the Finite ⋮ Consequence-based and fixed-parameter tractable reasoning in description logics ⋮ On the complexity of team logic and its two-variable fragment ⋮ Propositional epistemic logics with quantification over agents of knowledge ⋮ A simple logic of functional dependence ⋮ 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10 ⋮ SOME MODEL THEORY OF GUARDED NEGATION ⋮ Datalog and Its Extensions for Semantic Web Databases ⋮ Cylindric algebras and finite polyadic algebras ⋮ 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 ⋮ Statically safe program generation with SafeGen ⋮ Ehrenfeucht-Fraïssé games in finite set theory ⋮ McCarthy variations in a modal key ⋮ Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width ⋮ Decidability of the Class E by Maslov’s Inverse Method ⋮ Unnamed Item ⋮ IF modal logic and classical negation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A general method for proving decidability of intuitionistic modal logics ⋮ On the Restraining Power of Guards ⋮ Statistical $\mathcal{EL}$ is \textsc{ExpTime}-complete ⋮ First order logic without equality on relativized semantics ⋮ Modal characterisation theorems over special classes of frames ⋮ Relating structure and power: comonadic semantics for computational resources (extended abstract) ⋮ 2004 Summer Meeting of the Association for Symbolic Logic ⋮ Interpolation for extended modal languages ⋮ Positive announcements ⋮ Repetitions and permutations of columns in the semijoin algebra ⋮ Relating Structure and Power: Comonadic Semantics for Computational Resources ⋮ Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment ⋮ The many faces of interpolation ⋮ Modal logic and invariance ⋮ ON DEFINABILITY IN MULTIMODAL LOGIC ⋮ On the modal definability of simulability by finite transitive models ⋮ On a theorem of Vaught for first order logic with finitely many variables ⋮ Combining Description Logics, Description Graphs, and Rules ⋮ Atom-canonicity in varieties of cylindric algebras with applications to omitting types in multi-modal logic ⋮ Modality, bisimulation and interpolation in infinitary logic ⋮ 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 ⋮ Logical separability of labeled data examples under ontologies ⋮ Decidable fragments of first-order temporal logics ⋮ SGGS decision procedures ⋮ 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 ⋮ Generalized Quantifiers Meet Modal Neighborhood Semantics ⋮ On axiomatising products of Kripke frames ⋮ On interpolation in automated theorem proving ⋮ Deciding the guarded fragments by resolution ⋮ ${\mathcal E}$-connections of abstract description systems ⋮ Effective Interpolation and Preservation in Guarded Logics ⋮ Complexity of Two-Variable Logic on Finite Trees ⋮ PROBABILISTIC ROLE MODELS AND THE GUARDED FRAGMENT ⋮ Unnamed Item ⋮ Games and Lindström theorems ⋮ Finite-Variable Logics Do Not Have Weak Beth Definability Property ⋮ A Decidable Fragment of First Order Modal Logic: Two Variable Term Modal Logic ⋮ Are bundles good deals for first-order modal logic? ⋮ An algebraic semantics for possibilistic finite-valued Łukasiewicz logic ⋮ The Modelwise Interpolation Property of Semantic Logics ⋮ Arboreal categories and equi-resource homomorphism preservation theorems ⋮ Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments ⋮ Uniform Restricted Chase Termination ⋮ Semantically-guided goal-sensitive reasoning: decision procedures and the Koala prover ⋮ A modal loosely guarded fragment of second-order propositional modal logic ⋮ Modal logics and local quantifiers: a zoo in the elementary hierarchy ⋮ Uniform guarded fragments ⋮ DISTANCES BETWEEN FORMAL THEORIES ⋮ Omitting types for finite variable fragments and complete representations of algebras ⋮ Combining decidability paradigms for existential rules ⋮ ON THE GENERAL INTERPRETATION OF FIRST-ORDER QUANTIFIERS ⋮ DYNAMIC CONSEQUENCE AND PUBLIC ANNOUNCEMENT ⋮ Logic between Expressivity and Complexity ⋮ Unnamed Item ⋮ THE FLUTED FRAGMENT REVISITED ⋮ Guarded Negation ⋮ Guarded Negation ⋮ Algebraic Logic, Where Does it Stand Today? ⋮ The Fluted Fragment with Transitivity ⋮ Schema Mappings: A Case of Logical Dynamics in Database Theory ⋮ Modal Satisfiability via SMT Solving ⋮ First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries

Cites Work