Low complexity classes of multidimensional cellular automata
From MaRDI portal
Publication:861257
DOI10.1016/j.tcs.2006.07.061zbMath1140.68045MaRDI QIDQ861257
Publication date: 9 January 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2006.07.061
closure properties; multidimensional cellular automata; one-way multihead alternating finite automata; real-time and linear time classes
68Q80: Cellular automata (computational aspects)
Related Items
Cites Work
- On real time one-way cellular array
- On real-time cellular automata and trellis automata
- Two-dimensional iterative arrays: Characterizations and applications
- Relating the power of cellular arrays to their closure properties
- Variations of the firing squad problem and applications
- Alternating multihead finite automata
- Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
- Characterization of real time iterative array by alternating device.
- Real-time recognition of languages on an two-dimensional Archimedean thread
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- Parallel Parsing on a One-Way Array of Finite-State Machines
- On One-Way Cellular Arrays
- A universal interconnection pattern for parallel computers
- Alternation in simple devices
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
- Generation of Primes by a One-Dimensional Real-Time Iterative Array
