Cellular automata between sofic tree shifts
From MaRDI portal
Publication:393113
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
sofic shiftcellular automatonsubshiftinjectivity problemfree monoidshift of finite typetree shiftregular rooted treesurjectivity problemunrestricted Rabin automaton
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
