Frankfurter InformatikBerichte
1 search hit
 07, 1

Sublinearly space bounded iterative arrays
(2007)

Andreas Malcher
Carlo Mereghetti
Beatrice Palano
 Iterative arrays (IAs) are a, parallel computational model with a sequential processing of the input. They are onedimensional arrays of interacting identical deterministic finite automata. In this note, realtimelAs with sublinear space bounds are used to accept formal languages. The existence of a proper hierarchy of space complexity classes between logarithmic anel linear space bounds is proved. Furthermore, an optimal spacc lower bound for nonregular language recognition is shown. Key words: Iterative arrays, cellular automata, space bounded computations, decidability questions, formal languages, theory of computation