TY  - UNPD
A1  - Malcher, Andreas
T1  - Descriptional complexity of cellular automata and decidability questions
T2  - Frankfurter Informatik-Berichte ; Nr. 01,04
N2  - We study the descriptional complexity of cellular automata (CA), a parallel model of computation. We show that between one of the simplest cellular models, the realtime-OCA. and "classical" models like deterministic finite automata (DFA) or pushdown automata (PDA), there will be savings concerning the size of description not bounded by any recursive function, a so-called nonrecursive trade-off. Furthermore, nonrecursive trade-offs are shown between some restricted classes of cellular automata. The set of valid computations of a Turing machine can be recognized by a realtime-OCA. This implies that many decidability questions are not even semi decidable for cellular automata. There is no pumping lemma and no minimization algorithm for cellular automata.
T3  - Frankfurter Informatik-Berichte - 01, 4 
Y1  - 2001
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7182
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-71662
SN  - 1616-9107
PB  - Frankfurt am Main : Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik
CY  - Frankfurt am Main
ER  -