Guarded fixed point logics and the monadic theory of countable trees.

DOI10.1016/S0304-3975(01)00151-7zbMath1061.03022MaRDI QIDQ1853504

Erich Grädel

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

DecidabilityFixed point logicsGuarded logics

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items (7)

Combining Theories: The Ackerman and Guarded Fragments ⋮ The mu-calculus and Model Checking ⋮ A logic of reachable patterns in linked data-structures ⋮ PDL with intersection and converse: satisfiability and infinite-state model checking ⋮ Repetitions and permutations of columns in the semijoin algebra ⋮ Evaluating Datalog via tree automata and cycluits ⋮ The semijoin algebra and the guarded fragment

Uses Software

• Datalog LITE

Cites Work

• Modal languages and bounded fragments of predicate logic
• Loosely guarded fragment of first-order logic has the finite model property
• Interpolation and definability in guarded fragments
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• On the Restraining Power of Guards
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Datalog LITE
• Tolerance logic
• On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Guarded fixed point logics and the monadic theory of countable trees.