Cellular automata complexity trade-offs

DOI10.1016/S0019-9958(71)90501-8zbMath0222.94057OpenAlexW2020135021MaRDI QIDQ5628032

Alvy Ray III Smith

Publication date: 1971

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(71)90501-8

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items (33)

T-recognition of T-languages, a new approach to describe and program the parallel pattern recognition capabilities of d-dimensional tessellation structures ⋮ Impact of time delay on the dynamics of SEIR epidemic model using cellular automata ⋮ On time reduction and simulation in cellular spaces ⋮ Microeconomic foundations of cyclical irregularities or chaos ⋮ Two-dimensional iterative arrays: Characterizations and applications ⋮ Relating the power of cellular arrays to their closure properties ⋮ Language classes defined by time-bounded relativised cellular automata ⋮ Optimal simulation of tree arrays by linear arrays ⋮ On iterative and cellular tree arrays ⋮ Some results on time-varying and relativised cellular automata^* ⋮ Reducing the local alphabet size in tiling systems by means of 2D comma-free codes ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ On some open problems concerning the complexity of cellular arrays ⋮ A study of chaos in non-uniform cellular automata ⋮ Unnamed Item ⋮ Nondeterministic, probabilistic and alternating computations on cellular array models ⋮ Approximations of cooperative equilibria in multi-person prisoners' dilemma played by cellular automata ⋮ Languages not recognizable in real time by one-dimensional cellular automata ⋮ Survey of research in the theory of homogeneous structures and their applications ⋮ Computer simulation of reverberating spreading depression in a network of cell automata ⋮ On reversibility in cellular automata ⋮ On 'forgetful' cellular automata ⋮ The notion of a probabilistic cellular acceptor ⋮ Iterative arrays with direct central control ⋮ An improved parallel algorithm for integer GCD ⋮ The firing squad synchronization problem for a class of polyautomata networks ⋮ (A-)synchronous (non)-deterministic cell spaces simulating each other ⋮ Decomposable maps in general tessellation structures ⋮ Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures ⋮ Real-time language recognition by one-dimensional cellular automata ⋮ On the relationship between propagating context-dependent Lindenmayer systems and cellular automata systems ⋮ Theoretical reconciliation of equilibrium and structural approaches ⋮ Asynchronous interpretation of parallel microprograms

This page was built for publication: Cellular automata complexity trade-offs