Hierarchies and undecidability results for iterative arrays with sparse communication

DOI10.1007/S11047-019-09773-3MaRDI QIDQ6151193zbMATH OpenOpenAlexFDO

Authors 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 automatacommunication boundscomputational capacitydecidability questionsdescriptional complexityiterative arrays

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Recommendations

• Hierarchies and undecidability results for iterative arrays with sparse communication
• Iterative arrays with finite inter-cell communication
• Iterative arrays with finite inter-cell communication
• Computations and decidability of iterative arrays with restricted communication
• Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability

Cites work

• Cellular automata -- a computational point of view
• Cellular automata with limited inter-cell bandwidth
• Cellular automata with sparse communication
• Cellular automata: descriptional complexity and decidability
• Descriptional complexity -- an introductory survey
• Generation of Primes by a One-Dimensional Real-Time Iterative Array
• scientific article; zbMATH DE number 1512708 (Why is no real title available?)
• scientific article; zbMATH DE number 1886333 (Why is no real title available?)
• scientific article; zbMATH DE number 2113950 (Why is no real title available?)
• On one-way one-bit O (one)-message cellular automata
• On real-time cellular automata and trellis automata
• One-way cellular automata, bounded languages, and minimal communication
• 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 language recognition by one-dimensional cellular automata
• Signals in one-dimensional cellular automata
• Two-dimensional iterative arrays: Characterizations and applications

Cited in

(1)

• Iterative arrays with finite inter-cell communication

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

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