TY  - UNPD
A1  - Malcher, Andreas
T1  - On the descriptional complexity of iterative arrays
T2  - Frankfurter Informatik-Berichte ; Nr. 033
N2  - 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.
T3  - Frankfurter Informatik-Berichte - 03, 3 
KW  - Iteratives Array
KW  - Beschreibungskomplexität
Y1  - 2003
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7186
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-71682
SN  - 1616-9107
PB  - Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik
CY  - Frankfurt am Main
ER  -