The guarded fragment with transitive guards

DOI10.1016/j.apal.2004.01.003zbMath1048.03010OpenAlexW2030359223MaRDI QIDQ1877098

Wiesław Szwast, Lidia Tendera

Publication date: 16 August 2004

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

Full work available at URL: https://doi.org/10.1016/j.apal.2004.01.003

zbMATH Keywords

Computational complexityTransitivityFirst-order logicDecision problemGuarded fragment

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Complexity of Two-Variable Logic on Finite Trees ⋮ On the complexity of the two-variable guarded fragment with transitive guards ⋮ Querying the Unary Negation Fragment with Regular Path Expressions. ⋮ Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments ⋮ Unnamed Item ⋮ The fluted fragment with transitive relations ⋮ The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity results for classes of quantificational formulas
• Modal languages and bounded fragments of predicate logic
• Loosely guarded fragment of first-order logic has the finite model property
• On logics with two variables
• On the relative expressiveness of description logics and predicate logics
• On languages with two variables
• On the Decision Problem for Two-Variable First-Order Logic
• Complexity Results for First-Order Two-Variable Logic with Counting
• On the Restraining Power of Guards
• On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity

This page was built for publication: The guarded fragment with transitive guards