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

Metadaten
Verfasserangaben:	Andreas Malcher, Carlo Mereghetti, Beatrice Palano
URN:	urn:nbn:de:hebis:30-71726
ISSN:	1616-9107
Titel des übergeordneten Werkes (Deutsch):	Frankfurter Informatik-Berichte ; Nr. 07,1
Schriftenreihe (Bandnummer):	Frankfurter Informatik-Berichte (07, 1)
Verlag:	Johann Wolfgang Goethe-Univ., Fachbereich Informatik und Mathematik, Inst. für Informatik
Verlagsort:	Frankfurt am Main
Dokumentart:	Arbeitspapier
Sprache:	Englisch
Jahr der Fertigstellung:	2007
Jahr der Erstveröffentlichung:	2007
Veröffentlichende Institution:	Universitätsbibliothek Johann Christian Senckenberg
Datum der Freischaltung:	16.10.2009
Freies Schlagwort / Tag:	cellular automata; decidability questions; formal languages; iterative arrays; space bounded computations; theory of computation
Seitenzahl:	12, IV S.
HeBIS-PPN:	21973691X
Institute:	Informatik und Mathematik / Informatik
DDC-Klassifikation:	0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Lizenz (Deutsch):	Deutsches Urheberrecht

Open Access