Sublinearly space bounded iterative arrays

  • 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

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Andreas Malcher, Carlo Mereghetti, Beatrice Palano
Parent Title (German):Frankfurter Informatik-Berichte ; Nr. 07,1
Series (Serial Number):Frankfurter Informatik-Berichte (07, 1)
Publisher:Johann Wolfgang Goethe-Univ., Fachbereich Informatik und Mathematik, Inst. für Informatik
Place of publication:Frankfurt am Main
Document Type:Working Paper
Year of Completion:2007
Year of first Publication:2007
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2009/10/16
Tag:cellular automata; decidability questions; formal languages; iterative arrays; space bounded computations; theory of computation
Page Number:12, IV S.
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoDeutsches Urheberrecht