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 wit
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
show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Malcher, Carlo Mereghetti, Beatrice Palano
URN:urn:nbn:de:hebis:30-71726
ISSN:1616-9107
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
Language:English
Year of Completion:2007
Year of first Publication:2007
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2009/10/16
Tag:cellular automata ; decidability questions ; formal languages ; iterative arrays ; space bounded computations ; theory of computation
Pagenumber:12, IV S.
HeBIS PPN:21973691X
Institutes:Informatik
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $