Cellular automata between sofic tree shifts

DOI10.1016/j.tcs.2013.07.007zbMath1301.68185arXiv1212.5951OpenAlexW2170008811MaRDI QIDQ393113

Francesca Fiorenzi, Zoran Šunić, Michel Coornaert, Tullio G. 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 shiftcellular automatonsubshiftinjectivity 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)

Related Items (9)

Topological entropy for shifts of finite type over \(\mathbb{Z}\) and trees ⋮ On the lattice of subgroups of the lamplighter group ⋮ Large deviation principle of multiplicative Ising models on Markov-Cayley trees ⋮ Reversibility of linear cellular automata on Cayley trees with periodic boundary condition ⋮ FINITELY CONSTRAINED GROUPS OF MAXIMAL HAUSDORFF DIMENSION ⋮ Decidability of irreducible tree shifts of finite type ⋮ Stem and topological entropy on Cayley trees ⋮ A language hierarchy and kitchens-type theorem for self-similar groups ⋮ On surjunctive monoids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sofic tree-shifts
• The Myhill property for strongly irreducible subshifts over amenable groups
• Reversibility of 2D cellular automata is undecidable
• The theory of ends, pushdown automata, and second-order logic
• Amenable groups and cellular automata
• Endomorphisms of symbolic algebraic varieties
• Reversibility and surjectivity problems of cellular automata
• Cellular automata and strongly irreducible shifts of finite type.
• Semi-strongly irreducible shifts
• The elementary theory of finite fields
• Tree acceptors and some of their applications
• Tesselations with local transformations
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• A Garden of Eden theorem for linear subshifts
• On the density of periodic configurations in strongly irreducible subshifts
• Cellular Automata on Regular Rooted Trees
• The Injectivity of the Global Function of a Cellular Automaton in the Hyperbolic Plane is Undecidable
• Sofic and Almost of Finite Type Tree-Shifts
• Cellular Automata and Groups
• PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS
• Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems
• The Nilpotency Problem of One-Dimensional Cellular Automata
• An Introduction to Symbolic Dynamics and Coding
• Surjunctivity and Reversibility of Cellular Automata over Concrete Categories
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Normal Recurring Decimals

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