Cellular automata between sofic tree shifts

详细信息    查看全文

• 作者：Tullio Ceccherini-Silberstein ; Michel Coornaert ; Francesca Fiorenzi ; Zoran ?uni?
• 关键词：Free monoid ; Regular rooted tree ; Tree shift ; Subshift ; Shift of finite type ; Sofic shift ; Unrestricted Rabin automaton ; Cellular automaton ; Surjectivity problem ; Injectivity problem
• 刊名：Theoretical Computer Science
• 出版年：2013
• 出版时间：30 September, 2013
• 年：2013
• 卷：506
• 期：Complete
• 页码：79-101
• 全文大小：640 K

文摘

We study the sofic tree shifts of , where is a regular rooted tree of finite rank. In particular, we give their characterization in terms of unrestricted Rabin automata. We show that if is a sofic tree shift, then the configurations in X whose orbit under the shift action is finite are dense in X, and, as a consequence of this, we deduce that every injective cellular automata is surjective. Moreover, a characterization of sofic tree shifts in terms of general Rabin automata is given.

We present an algorithm for establishing whether two unrestricted Rabin automata accept the same sofic tree shift or not. This allows us to prove the decidability of the surjectivity problem for cellular automata between sofic tree shifts. We also prove the decidability of the injectivity problem for cellular automata defined on a tree shift of finite type.