Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems

DOI10.1090/S0273-0979-1981-14904-1zbMath0484.03019OpenAlexW2012343259MaRDI QIDQ3942944

Paul E. Schupp, David E. Muller

Publication date: 1981

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0273-0979-1981-14904-1

zbMATH Keywords

isomorphism typescontext-free graphsglobal transition functionend-isomorphismlabelled n-ary treemonadic second- order theory

Mathematics Subject Classification ID

Related Items (9)

Problem of finite axiomatizability for strongly minimal theories of graphs and groups with a nonzero number of ends ⋮ Ends of semigroups ⋮ Cellular automata between sofic tree shifts ⋮ Formulae and Asymptotics for Coefficients of Algebraic Functions ⋮ Simulations and the lamplighter group ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ On mathematical contributions of Paul E. Schupp ⋮ Closure properties in the class of multiple context-free groups ⋮ Locally finite properties of data structures and their computation

Cites Work

• Unnamed Item
• The equality problem for vector addition systems is undecidable
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems