Latest documents http://publikationen.ub.uni-frankfurt.de/index/index/ Fri, 16 Oct 2009 13:01:36 +0200 Fri, 16 Oct 2009 13:01:36 +0200 http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7189 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 Andreas Malcher; Carlo Mereghetti; Beatrice Palano workingpaper http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7189 Fri, 16 Oct 2009 13:01:36 +0200