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

DOI10.1016/J.IC.2006.08.001zbMATH Open1115.03021OpenAlexW4256671182MaRDI QIDQ859827FDOQ859827

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 complexitytransitivityfirst-order logicsatisfiabilityguarded fragment

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modal logic (including the logic of norms) (03B45) Classical first-order logic (03B10) Temporal logic (03B44) Logic in computer science (03B70)

Cites Work

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

Cited In (10)

• Small substructures and decidability issues for first-order logic with two variables
• Title not available (Why is that?)
• The fluted fragment with transitive relations
• Title not available (Why is that?)
• Equivalence closure in the two-variable guarded fragment
• Title not available (Why is that?)
• On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
• Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment
• One-Dimensional Logic over Trees
• Computer Science Logic

This page was built for publication: On the complexity of the two-variable guarded fragment with transitive guards

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q859827)