Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
From MaRDI portal
Publication:5560021
DOI10.1109/T-C.1969.222663zbMath0172.20804OpenAlexW2105155995MaRDI QIDQ5560021
Publication date: 1969
Published in: IEEE Transactions on Computers (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/t-c.1969.222663
Related Items
Closure properties of cellular automata ⋮ T-recognition of T-languages, a new approach to describe and program the parallel pattern recognition capabilities of d-dimensional tessellation structures ⋮ Real time recognition with cellular automata : a meaningful example ⋮ On time reduction and simulation in cellular spaces ⋮ Two-dimensional cellular automata and their neighborhoods ⋮ Real-time recognition of languages on an two-dimensional Archimedean thread ⋮ Real-time, pseudo real-time, and linear-time ITA ⋮ Grids and universal computations on one-dimensional cellular automata ⋮ Real-time reversible iterative arrays ⋮ Language not recognizable in real time by one-way cellular automata ⋮ On nondeterminism in parallel computation ⋮ On the capabilities of systolic systems ⋮ Two-dimensional iterative arrays: Characterizations and applications ⋮ Low complexity classes of multidimensional cellular automata ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ Optimal simulation of tree arrays by linear arrays ⋮ Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs ⋮ On iterative and cellular tree arrays ⋮ Unnamed Item ⋮ Linear speed-up for cellular automata synchronizers and applications ⋮ Alternation on cellular automata ⋮ Searching for Gapped Palindromes ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ Characterization of real time iterative array by alternating device. ⋮ Recognition of topological equivalence of patterns by array automata ⋮ Cellular Automata: Descriptional Complexity and Decidability ⋮ On some open problems concerning the complexity of cellular arrays ⋮ Shrinking one-way cellular automata ⋮ Sequential and cellular graph automata ⋮ Simulations between cellular automata on Cayley graphs ⋮ Iterative tree arrays with logarithmic depth† ⋮ Unnamed Item ⋮ On real time one-way cellular array ⋮ A linear speed-up theorem for cellular automata ⋮ Languages not recognizable in real time by one-dimensional cellular automata ⋮ Using fixed-point semantics to prove retiming lemmas ⋮ Unnamed Item ⋮ Real-time recognition of substring repetition and reversal ⋮ PROCESSES AND THEIR INTERACTIONS ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ Survey of research in the theory of homogeneous structures and their applications ⋮ Cellular automata with limited inter-cell bandwidth ⋮ 1-way stack automaton with jumps ⋮ Achieving Universal Computations on One-Dimensional Cellular Automata ⋮ The behavioral properties of homogeneous structures ⋮ Iterative arrays with direct central control ⋮ An improved parallel algorithm for integer GCD ⋮ Iterative arrays with finite inter-cell communication ⋮ Iterative arrays with self-verifying communication cell ⋮ Iterative arrays with finite inter-cell communication ⋮ 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 ⋮ Palindrome recognition in real time by a multitape Turing machine ⋮ (A-)synchronous (non)-deterministic cell spaces simulating each other ⋮ Intersections de langages algébriques bornes ⋮ A Hierarchy of Fast Reversible Turing Machines ⋮ Computations on one-dimensional cellular automata ⋮ Statistical mechanics of cellular automata ⋮ Some applications of propositional logic to cellular automata ⋮ Pushdown cellular automata ⋮ Some regular state sets in the system of one-dimensional iterative automata ⋮ Searching for gapped palindromes ⋮ Real-time language recognition by one-dimensional cellular automata ⋮ Two-dimensional cellular automata recognizer ⋮ Theory of formal grammars ⋮ Iterative tree automata ⋮ Deterministic Turing machines in the range between real-time and linear-time. ⋮ A multiprocess network logic with temporal and spatial modalities ⋮ Regular biosequence pattern matching with cellular automata ⋮ The derivation of on-line algorithms, with an application to finding palindromes ⋮ Non-deterministic cellular automata and languages ⋮ Computation theoretic aspects of cellular automata ⋮ Parallel recognition of rational languages in plane cellular automata ⋮ Topological transformations as a tool in the design of systolic networks
