Sublinearly space bounded iterative arrays

DOI10.1142/S0129054110007581MaRDI QIDQ3056282zbMATH OpenOpenAlexFDO

Authors Andreas Malcher, Carlo Mereghetti, Beatrice Palano

Publication date 11 November 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054110007581

zbMATH Keywords

cellular automatadecidability questionsformal languagesiterative arraysnon-recursive trade-offsspace bounded computations

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Recommendations

• scientific article; zbMATH DE number 1759411
• Computations and decidability of iterative arrays with restricted communication
• Publication:4934326
• Iterative arrays with set storage
• Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability

Cites work

• Counter machines and counter languages
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• On the Succinctness of Different Representations of Languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Signals in one-dimensional cellular automata
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• The Electronic Numerical Integrator and Computer (ENIAC)
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS

Cited in

(4)

• In memoriam Chandra Kintala
• Iterative tree arrays with logarithmic depth^†
• scientific article; zbMATH DE number 1759411 (Why is no real title available?)
• Cellular automata: descriptional complexity and decidability

This page was built for publication: Sublinearly space bounded iterative arrays

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