On the structure of graphs in the Caucal hierarchy

DOI10.1016/j.tcs.2008.01.053zbMath1144.68044OpenAlexW2039391567MaRDI QIDQ930912

Achim Blumensath

Publication date: 24 June 2008

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.053

zbMATH Keywords

monadic second-order logicCaucal hierarchyhigher-order pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05)

Related Items (5)

Order-theoretic Trees: Monadic Second-order Descriptions and Regularity ⋮ Simple monadic theories and partition width ⋮ FO Model Checking on Nested Pushdown Trees ⋮ Model Transformations in Decidability Proofs for Monadic Theories ⋮ Unnamed Item

Cites Work

• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• \(L(A)=L(B)\)? A simplified decidability proof.
• Monadic second-order logic on tree-like structures
• An automata-theoretical characterization of the OI-hierarchy
• The Monadic Theory of Tree-like Structures
• An Extension of Muchnik's Theorem
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the structure of graphs in the Caucal hierarchy