SUBLINEARLY SPACE BOUNDED ITERATIVE ARRAYS

DOI10.1142/S0129054110007581zbMath1207.68215OpenAlexW2079626566MaRDI QIDQ3056282

Carlo Mereghetti, Andreas Malcher, 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 automataformal languagesiterative arraysnon-recursive trade-offsdecidability questionsspace bounded computations

Mathematics Subject Classification ID

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

Related Items (2)

IN MEMORIAM CHANDRA KINTALA ⋮ Cellular Automata: Descriptional Complexity and Decidability

Cites Work

• Unnamed Item
• Signals in one-dimensional cellular automata
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• On the Succinctness of Different Representations of Languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Counter machines and counter languages
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
• The Electronic Numerical Integrator and Computer (ENIAC)

This page was built for publication: SUBLINEARLY SPACE BOUNDED ITERATIVE ARRAYS