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
| 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 |
| 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): |  Veröffentlichungsvertrag für Publikationen ohne Print on Demand |
