On the complexity of the two-variable guarded fragment with transitive guards

DOI10.1016/j.ic.2006.08.001zbMath1115.03021MaRDI QIDQ859827

Emanuel Kieroński

Publication date: 22 January 2007

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2006.08.001

zbMATH Keywords

computational complexity; first-order logic; transitivity; satisfiability; guarded fragment

Mathematics Subject Classification ID

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

03B70: Logic in computer science

03B10: Classical first-order logic

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

03B44: Temporal logic

Related Items

Unnamed Item, Unnamed Item, Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment, The fluted fragment with transitive relations, Small substructures and decidability issues for first-order logic with two variables

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Results on the propositional \(\mu\)-calculus
• Complexity results for classes of quantificational formulas
• Modal languages and bounded fragments of predicate logic
• The guarded fragment with transitive guards
• Alternation
• On languages with two variables
• On the Decision Problem for Two-Variable First-Order Logic
• Tableaux and algorithms for Propositional Dynamic Logic with Converse
• On the Restraining Power of Guards
• On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
• Computer Science Logic
• Decidability of Second-Order Theories and Automata on Infinite Trees