Real-time language recognition by one-dimensional cellular automata
From MaRDI portal
Publication:2563020
DOI10.1016/S0022-0000(72)80004-7zbMath0268.68044OpenAlexW2065620770WikidataQ60308396 ScholiaQ60308396MaRDI QIDQ2563020
Publication date: 1972
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(72)80004-7
Related Items
Closure properties of cellular automata ⋮ A symbiosis between cellular automata and genetic algorithms ⋮ T-recognition of T-languages, a new approach to describe and program the parallel pattern recognition capabilities of d-dimensional tessellation structures ⋮ One-way cellular automata on Cayley graphs ⋮ On time reduction and simulation in cellular spaces ⋮ Real-time recognition of languages on an two-dimensional Archimedean thread ⋮ Real-time, pseudo real-time, and linear-time ITA ⋮ A study on learning robustness using asynchronous 1D cellular automata rules ⋮ Real-time reversible iterative arrays ⋮ On optimal solutions to the firing squad synchronization problem ⋮ A survey of two-dimensional automata theory ⋮ Finite turns and the regular closure of linear context-free languages ⋮ Two-dimensional iterative arrays: Characterizations and applications ⋮ A characterization of constant-time cellular automata computation ⋮ Constant Acceleration Theorem for Extended von Neumann Neighbourhoods ⋮ Relating the power of cellular arrays to their closure properties ⋮ Language classes defined by time-bounded relativised cellular automata ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ On the equivalence of linear conjunctive grammars and trellis automata ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ On iterative and cellular tree arrays ⋮ Unnamed Item ⋮ Some results on time-varying and relativised cellular automata* ⋮ Efficient unidimensional universal cellular automaton ⋮ Alternation on cellular automata ⋮ A simple P-complete problem and its language-theoretic representations ⋮ Self-verifying Cellular Automata ⋮ Real-time recognition of two-dimensional tapes by cellular automata ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ Fast one-way cellular automata. ⋮ Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars. ⋮ On some open problems concerning the complexity of cellular arrays ⋮ Exemples de classes d'automates cellulaires ⋮ Hierarchical cellular automata for visual saliency ⋮ \(\mathrm{GF}(2)\)-operations on basic families of formal languages ⋮ Complexity of algorithms and computations ⋮ Synchronous to asynchronous transformation of polyautomata ⋮ Deterministic one-way simulation of two-way real-time cellular automata and its related problems ⋮ Parallel language recognition in constant time by cellular automata ⋮ The Boolean closure of linear context-free languages ⋮ Fault-tolerant schemes for some systolic systems ⋮ On hardest languages for one-dimensional cellular automata ⋮ One-dimensional pattern generation by cellular automata ⋮ Estimates of the operating time of stable iterative, language-modeling, and recognition systems ⋮ Nondeterministic, probabilistic and alternating computations on cellular array models ⋮ A linear speed-up theorem for cellular automata ⋮ Languages not recognizable in real time by one-dimensional cellular automata ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ Cellular automata with limited inter-cell bandwidth ⋮ A Study on the Automatic Generation of Asynchronous Cellular Automata Rules by Means of Genetic Algorithms ⋮ On 'forgetful' cellular automata ⋮ The notion of a probabilistic cellular acceptor ⋮ Surjectivity of nondeterministic parallel maps induced by nondeterministic cellular automata ⋮ Theory of cellular automata: a survey ⋮ On hardest languages for one-dimensional cellular automata ⋮ Iterative arrays with self-verifying communication cell ⋮ Iterative arrays with self-verifying communication cell ⋮ Constructible functions in cellular automata and their applications to hierarchy results ⋮ Synchronization and computing capabilities of linear asynchronous structures ⋮ Classes of formal grammars ⋮ (A-)synchronous (non)-deterministic cell spaces simulating each other ⋮ Evolving cellular automata to perform computations: Mechanisms and impediments ⋮ Computations on one-dimensional cellular automata ⋮ Real-Time Prime Generators Implemented on Small-State Cellular Automata ⋮ Pushdown cellular automata ⋮ Two-dimensional cellular automata recognizer ⋮ Complexity of One-Way Cellular Automata ⋮ Language Recognition by Reversible Partitioned Cellular Automata ⋮ Iterative tree automata ⋮ Regular biosequence pattern matching with cellular automata ⋮ Fast language acceptance by shrinking cellular automata ⋮ A universal cellular automaton in quasi-linear time and its S-m-n form ⋮ Non-deterministic cellular automata and languages ⋮ Computation theoretic aspects of cellular automata ⋮ Topological transformations as a tool in the design of systolic networks ⋮ Computation theory of cellular automata ⋮ Fast parallel language recognition by cellular automata
Cites Work
- An optimum solution to the firing squad synchronization problem
- On the Computational Complexity of Algorithms
- A generalized firing squad problem
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
- Generation of Primes by a One-Dimensional Real-Time Iterative Array
- Tessellation Automata
- Quasi-realtime languages
- Classes of languages and linear-bounded automata
- Cellular automata complexity trade-offs
- Synchronization of interacting automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
