Cellular automata on regular rooted trees

DOI10.1007/978-3-642-31606-7_9zbMATH Open1297.68175arXiv1205.6785OpenAlexW1601366707MaRDI QIDQ2914698FDOQ2914698

Authors: Michel Coornaert, Francesca Fiorenzi, Zoran Šunić, Tullio Ceccherini-Silberstein 

Publication date: 20 September 2012

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Abstract: We study cellular automata on regular rooted trees. This includes the characterization of sofic tree shifts in terms of unrestricted Rabin automata and the decidability of the surjectivity problem for cellular automata between sofic tree shifts.

Full work available at URL: https://arxiv.org/abs/1205.6785

Recommendations

• Cellular automata between sofic tree shifts
• Sofic tree-shifts
• Tree algebra of sofic tree languages
• Topological properties of cellular automata on trees
• Sofic and almost of finite type tree-shifts

zbMATH Keywords

cellular automatonfree monoidsurjectivity problemunrestricted Rabin automatonfinite tree automatonsofic tree shift

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Cited In (7)

• Cellular automata between sofic tree shifts
• Topological properties of cellular automata on trees
• Computational aspects of cellular automata on countable sofic shifts
• Sofic tree-shifts
• Von Neumann regularity, split epicness and elementary cellular automata
• On von Neumann regularity of cellular automata
• Title not available (Why is that?)

This page was built for publication: Cellular automata on regular rooted trees

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