Hierarchies and undecidability results for iterative arrays with sparse communication

DOI10.1007/S11047-019-09773-3zbMath1530.68177OpenAlexW4250337606MaRDI QIDQ6151193

Andreas Malcher

Publication date: 9 February 2024

Published in: Natural Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11047-019-09773-3

zbMATH Keywords

cellular automatadescriptional complexitycomputational capacityiterative arraysdecidability questionscommunication bounds

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Cites Work

• Cellular automata with limited inter-cell bandwidth
• On real-time cellular automata and trellis automata
• Two-dimensional iterative arrays: Characterizations and applications
• Signals in one-dimensional cellular automata
• Cellular automata with sparse communication
• Real-time language recognition by one-dimensional cellular automata
• On One-way One-bit O (One)-message Cellular Automata
• Parallel Parsing on a One-Way Array of Finite-State Machines
• Cellular Automata: Descriptional Complexity and Decidability
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Generation of Primes by a One-Dimensional Real-Time Iterative Array
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hierarchies and undecidability results for iterative arrays with sparse communication