Complexity of monodic guarded fragments over linear and real time

DOI10.1016/j.apal.2005.06.007zbMath1093.03009MaRDI QIDQ2576942

I. M. Hodkinson

Publication date: 29 December 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10044/1/623

zbMATH Keywords

mosaic; satisfiability; first-order temporal logic; loosely guarded fragment; packed fragment; quasimodel

Mathematics Subject Classification ID

03B70: Logic in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03B44: Temporal logic

Related Items

The complexity of temporal logic over the reals, Quantified epistemic logics for reasoning about knowledge in multi-agent systems, Undecidable Propositional Bimodal Logics and One-Variable First-Order Linear Temporal Logics with Counting, Inference Rules in Multi-agents’ Temporal Logics, First-Order Linear-Time Epistemic Logic with Group Knowledge: An Axiomatisation of the Monodic Fragment

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of temporal logic over the reals
• The decision problem for linear temporal logic
• Modal languages and bounded fragments of predicate logic
• The complexity of the temporal logic with ``until over general linear time
• Many-dimensional modal logics: theory and applications
• Decidable fragments of first-order temporal logics
• Loosely guarded fragment of first-order logic has the finite model property
• Axiomatizing the monodic fragment of first-order temporal logic
• Equality and monodic first-order temporal logic
• Monodic packed fragment with equality is decidable
• Monodic Fragments of First-Order Temporal Logics: 2000–2001 A.D.
• The complexity of propositional linear temporal logics
• On Non-local Propositional and Weak Monodic Quantified CTL*
• Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures
• On the Restraining Power of Guards
• On the elementary theory of linear order
• $ℵ_0$-categoricity of linear orderings
• Automated Deduction – CADE-19
• Tolerance logic