The Nilpotency Problem of One-Dimensional Cellular Automata
From MaRDI portal
Publication:4016914
DOI10.1137/0221036zbMath0761.68067OpenAlexW2092195232WikidataQ62045994 ScholiaQ62045994MaRDI QIDQ4016914
Publication date: 16 January 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/5044b64aacc4b7a5626427fab48372a2d9f8a853
Related Items (61)
Cellular automata and communication complexity ⋮ Sand automata as cellular automata ⋮ Rice's theorem for the limit sets of cellular automata ⋮ Unraveling simplicity in elementary cellular automata ⋮ Ergodicity of some classes of cellular automata subject to noise ⋮ A Characterization of Cellular Automata Generated by Idempotents on the Full Shift ⋮ TWO-DIMENSIONAL LANGUAGES AND CELLULAR AUTOMATA ⋮ (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata ⋮ Self-stabilisation of Cellular Automata on Tilings ⋮ On dynamical complexity of surjective ultimately right-expansive cellular automata ⋮ Cellular automata between sofic tree shifts ⋮ Local rule distributions, language complexity and non-uniform cellular automata ⋮ On computing the Lyapunov exponents of reversible cellular automata ⋮ An automaton group with undecidable order and Engel problems ⋮ On computing the entropy of cellular automata. ⋮ Two-by-Two Substitution Systems and the Undecidability of the Domino Problem ⋮ Cold dynamics in cellular automata: a tutorial ⋮ Countable sofic shifts with a periodic direction ⋮ Undecidable translational tilings with only two tiles, or one nonabelian tile ⋮ Graph subshifts ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Effective Projections on Group Shifts to Decide Properties of Group Cellular Automata ⋮ Arithmetical complexity of the language of generic limit sets of cellular automata ⋮ Limit set problem of multi-agent systems with finite states: an eigenvalue-based approach ⋮ On the conjugacy problem of cellular automata ⋮ On dynamical finiteness properties of algebraic group shifts ⋮ Automaton (Semi)groups: Wang Tilings and Schreier Tries ⋮ Cellular automata in fuzzy backgrounds ⋮ A uniquely ergodic cellular automaton ⋮ Subshifts with sparse traces ⋮ Around probabilistic cellular automata ⋮ Three research directions in non-uniform cellular automata ⋮ The Undecidability of the Domino Problem ⋮ Probabilistic Cellular Automata, Invariant Measures, and Perfect Sampling ⋮ \(\mu\)-limit sets of cellular automata from a computational complexity perspective ⋮ Nondeterministic cellular automata ⋮ THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE ⋮ An aperiodic set of 11 Wang tiles ⋮ Dynamical behavior of additive cellular automata over finite abelian groups ⋮ A search algorithm for subshift attractors of cellular automata ⋮ Bulking II: Classifications of cellular automata ⋮ Permutive one-way cellular automata and the finiteness problem for automaton groups ⋮ On the undecidability of the limit behavior of cellular automata ⋮ Theory of cellular automata: a survey ⋮ Nilpotency and Limit Sets of Cellular Automata ⋮ Hierarchy and Expansiveness in 2D Subshifts of Finite Type ⋮ Nilpotency and periodic points in non-uniform cellular automata ⋮ The 4-way deterministic tiling problem is undecidable ⋮ Slopes of multidimensional subshifts ⋮ Decidability in Group Shifts and Group Cellular Automata ⋮ Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties ⋮ On linear shifts of finite type and their endomorphisms ⋮ Inducing an order on cellular automata by a grouping operation ⋮ Nilpotent endomorphisms of expansive group actions ⋮ Characterizations of periods of multi-dimensional shifts ⋮ The word and order problems for self-similar and automata groups ⋮ Global fixed point attractors of circular cellular automata and periodic tilings of the plane: Undecidability results ⋮ Freezing, Bounded-Change and Convergent Cellular Automata ⋮ Decidability and undecidability in cellular automata ⋮ Computation theoretic aspects of cellular automata ⋮ On the impact of treewidth in the computational complexity of freezing dynamics
This page was built for publication: The Nilpotency Problem of One-Dimensional Cellular Automata
