On the descriptional complexity of iterative arrays

The descriptional complexity of iterative arrays (lAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that lAs when compared to deterministic finite
The descriptional complexity of iterative arrays (lAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that lAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between lAs working in linear time and lAs working in real time. Furthermore, the descriptional complexity of lAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for lAs are undecidable and not semidecidable.
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
URN:urn:nbn:de:hebis:30-71682
ISSN:1616-9107
Series (Serial Number):Frankfurter Informatik-Berichte (03, 3)
Publisher:Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik
Place of publication:Frankfurt am Main
Document Type:Working Paper
Language:English
Year of Completion:2003
Year of first Publication:2003
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2009/10/16
SWD-Keyword:Beschreibungskomplexität; Iteratives Array
Pagenumber:IV, 10 S.
HeBIS PPN:219727317
Institutes:Informatik
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $