TY  - UNPD
A1  - Malcher, Andreas
A1  - Mereghetti, Carlo
A1  - Palano, Beatrice
T1  - Sublinearly space bounded iterative arrays
T2  - Frankfurter Informatik-Berichte ; Nr. 07,1
N2  - Iterative arrays (IAs) are a, parallel computational model with a sequential processing of the input. They are one-dimensional arrays of interacting identical deterministic finite automata. In this note, realtime-lAs 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 non-regular language recognition is shown. Key words: Iterative arrays, cellular automata, space bounded computations, decidability questions, formal languages, theory of computation
T3  - Frankfurter Informatik-Berichte - 07, 1 
KW  - iterative arrays
KW  - cellular automata
KW  - space bounded computations
KW  - decidability questions
KW  - formal languages
KW  - theory of computation
Y1  - 2007
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7189
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-71726
SN  - 1616-9107
PB  - Johann Wolfgang Goethe-Univ., Fachbereich Informatik und Mathematik, Inst. für Informatik
CY  - Frankfurt am Main
ER  -