The guarded fragment with transitive guards

DOI10.1016/j.apal.2004.01.003zbMath1048.03010MaRDI 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 complexity; Transitivity; First-order logic; Decision problem; Guarded fragment

Mathematics Subject Classification ID

03B45: Modal logic (including the logic of norms)

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

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

Related Items

Complexity of Two-Variable Logic on Finite Trees, On the complexity of the two-variable guarded fragment with transitive guards, The fluted fragment with transitive relations, The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT, Unnamed Item, Unnamed Item

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item