Cellular automata on regular rooted trees

DOI10.1007/978-3-642-31606-7_9MaRDI QIDQ2914698zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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
• scientific article; zbMATH DE number 3938573 (Why is no real title available?)

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)