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 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Andreas Malcher
Parent Title (German):Frankfurter Informatik-Berichte ; Nr. 033
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
Year of Completion:2003
Year of first Publication:2003
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2009/10/16
GND Keyword:Iteratives Array; Beschreibungskomplexität
Page Number:IV, 10 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