The Monadic Theory of Tree-like Structures

DOI10.1007/3-540-36387-4_16MaRDI QIDQ4412839zbMATH OpenOpenAlexFDO

Authors Dietmar Berwanger, Achim Blumensath

Publication date 16 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-36387-4_16

zbMATH Keywords

tree automata

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• An Extension of Muchnik's Theorem
• Monadic second-order logic on tree-like structures
• Prefix-Recognizable Graphs and Monadic Logic
• Monadic second order logic on tree-like structures
• Trees over infinite structures and path logics with synchronization

Cited in

(20)

• Automata on infinite trees
• Iterated pushdown automata and sequences of rational numbers
• The full binary tree cannot be interpreted in a chain
• Simple monadic theories and partition width
• A Hierarchy of Automaticω-Words having a Decidable MSO Theory
• Model Transformations in Decidability Proofs for Monadic Theories
• On monadic theories of monadic predicates
• New algorithm for weak monadic second-order logic on inductive structures
• Decidability of Scott's model as an ordered ℚ-vectorspace
• Monadic second order logic on tree-like structures
• Finite automata over infinite alphabets: two models with transitions for local change
• Shelah-Stupp's iteration and Muchnik's iteration
• An Extension of Muchnik's Theorem
• Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic
• Trees over infinite structures and path logics with synchronization
• A Combinatorial Theorem for Trees
• Mathematical Foundations of Computer Science 2003
• Monodic Tree Kleene Algebra
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• On the structure of graphs in the Caucal hierarchy

This page was built for publication: The Monadic Theory of Tree-like Structures

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