Shelah-Stupp's and Muchnik's iterations revisited

DOI10.1007/978-3-030-79416-3_24OpenAlexW3175377552MaRDI QIDQ2117107

Paweł Parys

Publication date: 21 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-79416-3_24

zbMATH Keywords

hierarchyinfinite relational structuresMSO decidabilityMuchnik's iterationShelah-stupp's iteration

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The theory of ends, pushdown automata, and second-order logic
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• The monadic theory of order
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• Monadic second-order logic on tree-like structures
• On infinite transition graphs having a decidable monadic theory
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Decision Problems of Finite Automata Design and Related Arithmetics
• Shelah-Stupp’s Iteration and Muchnik’s Iteration
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: Shelah-Stupp's and Muchnik's iterations revisited