The evaluation of first-order substitution is monadic second-order compatible

DOI10.1016/S0304-3975(02)00012-9zbMath0996.68061MaRDI QIDQ1603690

Teodor Knapik, Bruno Courcelle

Publication date: 15 July 2002

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

zbMATH Keywords

monadic second-order logicdecidability of logical theoriesalgebraic treefirst-order substitutionhyperalgebraic tree

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

The modular decomposition of countable graphs. Definition and construction in monadic second-order logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• Fundamental properties of infinite trees
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• The IO- and OI-hierarchies
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• Program transformations and algebraic semantics
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• Monadic second-order definable graph transductions: a survey
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: The evaluation of first-order substitution is monadic second-order compatible