Cellular automata between sofic tree shifts

DOI10.1016/J.TCS.2013.07.007MaRDI QIDQ393113zbMATH OpenOpenAlexFDO

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

Publication date 16 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

sofic shiftsubshiftcellular automatoninjectivity problemfree monoidshift of finite typetree shiftregular rooted treesurjectivity problemunrestricted Rabin automaton

Mathematics Subject Classification ID

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

Abstract: We study the sofic tree shifts of $A^{Sigm{a}^{\ast }}$, where $Sigm{a}^{\ast }$ is a regular rooted tree of finite rank. In particular, we give their characterization in terms of unrestricted Rabin automata. We show that if $Xsubset{A}^{Sigm{a}^{\ast }}$ 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 $aucolonXoX$ 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.

Recommendations

• Computational aspects of cellular automata on countable sofic shifts
• Sofic Trace Subshift of a Cellular Automaton
• Cellular automata versus quasisturmian shifts
• On the sofic limit sets of cellular automata
• Cellular automata, decidability and phasespace
• scientific article; zbMATH DE number 3938573
• Cellular automata on regular rooted trees
• Cellular automata, duality and sofic groups
• Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems
• Cellular automata over algebraic structures

Cites work

• scientific article; zbMATH DE number 3403481 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A garden of Eden theorem for linear subshifts
• Amenable groups and cellular automata
• An Introduction to Symbolic Dynamics and Coding
• Cellular automata and groups
• Cellular automata and strongly irreducible shifts of finite type.
• Cellular automata on regular rooted trees
• Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Endomorphisms of symbolic algebraic varieties
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Normal Recurring Decimals
• On the density of periodic configurations in strongly irreducible subshifts
• PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS
• Reversibility and surjectivity problems of cellular automata
• Reversibility of 2D cellular automata is undecidable
• Semi-strongly irreducible shifts
• Sofic and almost of finite type tree-shifts
• Sofic groups and dynamical systems.
• Sofic tree-shifts
• Surjunctivity and reversibility of cellular automata over concrete categories
• Tesselations with local transformations
• The Injectivity of the Global Function of a Cellular Automaton in the Hyperbolic Plane is Undecidable
• The Myhill property for strongly irreducible subshifts over amenable groups
• The Nilpotency Problem of One-Dimensional Cellular Automata
• The elementary theory of finite fields
• The theory of ends, pushdown automata, and second-order logic
• Topological properties of cellular automata on trees
• Tree acceptors and some of their applications

Cited in

(16)

• Topological properties of cellular automata on trees
• On surjunctive monoids
• A language hierarchy and kitchens-type theorem for self-similar groups
• Glider automata on all transitive sofic shifts
• Finitely constrained groups of maximal Hausdorff dimension
• Computational aspects of cellular automata on countable sofic shifts
• Sofic tree-shifts
• Sofic and almost of finite type tree-shifts
• Reversibility of linear cellular automata on Cayley trees with periodic boundary condition
• Decidability of irreducible tree shifts of finite type
• On the lattice of subgroups of the lamplighter group.
• REDUCED POWER AUTOMATA AND SOFIC SYSTEMS
• Stem and topological entropy on Cayley trees
• Large deviation principle of multiplicative Ising models on Markov-Cayley trees
• Cellular automata on regular rooted trees
• Topological entropy for shifts of finite type over \(\mathbb{Z}\) and trees

This page was built for publication: Cellular automata between sofic tree shifts

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