Computation theory of cellular automata
From MaRDI portal
Self-organizing behaviour in cellular automata is discussed as a computational process. Formal language theory is used to extend dynamical systems theory descriptions of cellular automata. The sets of configurations generated after a finite number of time steps of cellular automaton evolution are shown to form regular languages. Many examples are given. The sizes of the minimal grammars for these languages provide measures of the complexities of the sets. This complexity is usually found to be non-decreasing with time. the limit sets generated by some classes of cellular automata correspond to regular languages. For other automata they appear to correspond to more complicated languages. Many properties of these sets are then formally non-computable. It is suggested that such undecidability is common in these and other dynamical systems.
Recommendations
- Computation theoretic aspects of cellular automata
- scientific article; zbMATH DE number 17562
- Cellular automata -- a computational point of view
- Cellular automata and grossone computations
- An overview of computation in cellular automata
- Theory of practical cellular automaton
- On the computational complexity of finite cellular automata
- Computations on nondeterministic cellular automata
- Theory of cellular automata: a survey
- Computational classification of cellular automata
Cites work
- Algebraic properties of cellular automata
- Algorithmic Information Theory
- Axiom A Diffeomorphisms have Rational Zeta Functions
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Endomorphisms and automorphisms of the shift dynamical system
- Finite procedures for sofic systems
- Finite state languages
- scientific article; zbMATH DE number 3848281 (Why is no real title available?)
- scientific article; zbMATH DE number 3896305 (Why is no real title available?)
- scientific article; zbMATH DE number 3896306 (Why is no real title available?)
- scientific article; zbMATH DE number 3896307 (Why is no real title available?)
- scientific article; zbMATH DE number 3934947 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3692636 (Why is no real title available?)
- scientific article; zbMATH DE number 3717357 (Why is no real title available?)
- scientific article; zbMATH DE number 3738961 (Why is no real title available?)
- scientific article; zbMATH DE number 3745547 (Why is no real title available?)
- scientific article; zbMATH DE number 3588051 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3641577 (Why is no real title available?)
- scientific article; zbMATH DE number 3802813 (Why is no real title available?)
- scientific article; zbMATH DE number 3227613 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3310089 (Why is no real title available?)
- scientific article; zbMATH DE number 3311587 (Why is no real title available?)
- scientific article; zbMATH DE number 3366846 (Why is no real title available?)
- scientific article; zbMATH DE number 3095523 (Why is no real title available?)
- Linear Automaton Transformations
- Local maps inducing surjective global maps of one-dimensional tessellation automata
- Nonlinear oscillations, dynamical systems, and bifurcations of vector fields
- Normal Recurring Decimals
- On the entropy of context-free languages
- Persuasion with communication costs
- Prediction and Entropy of Printed English
- Real-time language recognition by one-dimensional cellular automata
- Simple Computation-Universal Cellular Spaces
- Statistical mechanics of cellular automata
- Subshifts of finite type and sofic systems
- The constructibility of a configuration in a cellular automaton
- The noncomputability of the channel capacity of context-sensitive languages
Cited in
(only showing first 100 items - show all)- Periodic orbits for additive cellular automata
- Random sequence generation by cellular automata
- Toward a quantitative theory of self-generated complexity
- Computing fractal dimensions for additive cellular automata
- Global properties of cellular automata
- A function for evaluating the computing time of a bubbling system
- Predecessor states for certain cellular automata evolutions
- Intriguing properties of global structure in some classes of finite cellular automata
- Cellular automata as a paradigm for ecological modeling
- On totalistic systolic networks
- Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems
- Symbolic dynamics and characterization of complexity
- The attractor-basin portrait of a cellular automaton
- On the limit set of some universal cellular automata
- Edge of chaos in rule-changing cellular automata
- Computations on nondeterministic cellular automata
- Complexity of two-dimensional patterns
- From quantum cellular automata to quantum lattice gases
- A thermodynamic formalism for one dimensional cellular automata
- Nonconstructible blocks in 1D cellular automata: minimal generators and natural systems
- Elements of a theory of computer simulation. I
- Transformations of one-dimensional cellular automaton rules by translation-invariant local surjective mappings
- Arithmetic representations of cellular automata
- Dynamical system where proving chaos is equivalent to proving Fermat's conjecture
- Complex systems, complexity measures, grammars and model-inferring
- Regular unimodal systems and factors of finite automata
- Numerical studies for a model describing complexity
- Predecessors of cellular automata states. II: Pre-images of finite sequences
- The measures of sequence complexity for EEG studies
- Phenomenlogy of nonlocal cellular automata
- The ``magic rule spaces of neural-like elementary cellular automata
- Cellular automata and intermediate degrees.
- Hierarchical content classification and script determination for automatic document image processing.
- A complexity analysis of the elementary cellular automaton of rule 122
- Graph-theoretical characterization of invertible cellular automata
- Autonomous indefiniteness versus external indefiniteness: Theory of weak topped -structure and its application to elementary local cellular automaton
- Theory of cellular automata: a survey
- Linear cellular automata and the garden-of-eden
- The calculi of emergence: Computation, dynamics and induction
- Multilevel evolution: Replicators and the evolution of diversity
- A numerical study of one-dimensional cellular automata
- Statistical analysis of a multiply-twisted helix
- Evolution complexity of the elementary cellular automaton of rule 22.
- A note on inherent replication properties of local cellular automata transition functions
- Cellular automata and statistical mechanical models
- Robust periodic solutions and evolution from seeds in one-dimensional edge cellular automata
- \(1/f\) fluctuation in the game of life
- On the absence of homogeneous scalar unitary cellular automata.
- On the classifiability of cellular automata
- Numerical methods for microstructural evolutions in laser additive manufacturing
- On the complexity of asynchronous freezing cellular automata
- Phase transitions in random mixtures of elementary cellular automata
- A spectral outlook on the elementary cellular automata with cyclic configurations and block-sequential asynchronous updates
- One-dimensional cellular automata with random rules: longest temporal period of a periodic solution
- Mean field dynamics of stochastic cellular automata for random and small-world graphs
- Shift-equivalence of \(k\)-ary, one-dimensional cellular automata rules
- Long-range correlations in chaotic cellular automata
- Learning processes based on incomplete identification and information generation
- Behavioral complexity indicators for process algebra: The NKS approach
- Complexity of limit language of the elementary cellular automaton of Rule 22
- An algebraic measure of complexity
- Digital mechanics. An information process based on reversible universal cellular automata
- Progress, gaps and obstacles in the classification of cellular automata
- Predictability, complexity, and learning
- 2D elementary cellular automata with four neighbors
- Asymptotic behavior and ratios of complexity in cellular automata
- Designing complex dynamics in cellular automata with memory
- Computational classification of cellular automata
- Evolutionary dynamics of the spatial prisoner's dilemma with single and multi-behaviors: a multi-agent application
- Measure evolution of cellular automata and of finitely anticipative transformations
- Distributed multi-authority attribute-based encryption using cellular automata
- scientific article; zbMATH DE number 4215382 (Why is no real title available?)
- Ranks of finite semigroups of one-dimensional cellular automata
- A NOTE ON FRACTALS OF ONE FORBIDDEN WORD AND THEIR BOX DIMENSIONS
- Finite Size Stability Analysis for Stochastic Cellular Automata
- Five Determinisation Algorithms
- A topological classification ofD-dimensional cellular automata
- Asymptotic Cellular Complexity
- Statistical mechanics of cellular automata
- scientific article; zbMATH DE number 3896307 (Why is no real title available?)
- Classes of linear automata
- On the computational power of totalistic cellular automata
- scientific article; zbMATH DE number 4092781 (Why is no real title available?)
- Impartial games emulating one-dimensional cellular automata and undecidability
- scientific article; zbMATH DE number 17562 (Why is no real title available?)
- scientific article; zbMATH DE number 166925 (Why is no real title available?)
- scientific article; zbMATH DE number 2013213 (Why is no real title available?)
- scientific article; zbMATH DE number 2068878 (Why is no real title available?)
- Unpredictability and undecidability in dynamical systems
- Hierarchical approach to complexity with applications to dynamical systems
- Traveling patterns in cellular automata
- Overview: PCA models and issues
- Inferring the Limit Behavior of Some Elementary Cellular Automata
- Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines
- scientific article; zbMATH DE number 2113941 (Why is no real title available?)
- On the sofic limit sets of cellular automata
- Internal symmetries of cellular automata
- Numerical Simulation of the Grains Growth on Titanium Alloy Electron Beam Welding Process
- A comparison of finite and cellular automata
- Logical gates via gliders collisions
This page was built for publication: Computation theory of cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1072705)
