Low complexity classes of multidimensional cellular automata

DOI10.1016/J.TCS.2006.07.061MaRDI QIDQ861257zbMATH OpenOpenAlexFDO

Authors Véronique Terrier

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

zbMATH Keywords

closure propertiesmultidimensional cellular automataone-way multihead alternating finite automatareal-time and linear time classes

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Recommendations

• scientific article; zbMATH DE number 4026832
• scientific article; zbMATH DE number 2113943
• Language classes defined by time-bounded relativised cellular automata
• Alternation on cellular automata
• Complexity of one-way cellular automata

Cites work

• A universal interconnection pattern for parallel computers
• Alternating multihead finite automata
• Alternation in simple devices
• Characterization of real time iterative array by alternating device.
• Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
• Generation of Primes by a One-Dimensional Real-Time Iterative Array
• On One-Way Cellular Arrays
• On real time one-way cellular array
• On real-time cellular automata and trellis automata
• Parallel Parsing on a One-Way Array of Finite-State Machines
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Real-time recognition of languages on an two-dimensional Archimedean thread
• Relating the power of cellular arrays to their closure properties
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• Two-dimensional iterative arrays: Characterizations and applications
• Variations of the firing squad problem and applications

Cited in

(5)

• A new dimension sensitive property for cellular automata
• Plane-walking automata
• scientific article; zbMATH DE number 1462667 (Why is no real title available?)
• A generalized neighborhood for cellular automata
• Inductive definitions in logic versus programs of real-time cellular automata

This page was built for publication: Low complexity classes of multidimensional cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q861257)