Affiliations: Fachbereich für Mathematik und Informatik,
Universität Kassel, Heinrich Plett Straße 40, D-34132 Kassel, Germany.
E-mail: [email protected] | Institut für Informatik,
Universität Giessen, Arndtstr. 2, D-35392 Giessen, Germany.
E-mail: [email protected]
Abstract: Devices of interconnected parallel acting sequential automata are
investigated from a language theoretic point of view. Starting with the
well-known result that each unary language accepted by a deterministic one-way
cellular automaton (OCA) in real time has to be a regular language, we will
answer the three natural questions 'How much time do we have to provide?'
'How much power do we have to plug in the single cells (i.e., how complex
has a single cell to be)?' and 'How can we modify the mode of operation (i.e., how much
nondeterminism do we have to add)?' in order to accept non-regular
unary languages. We show the surprising result that for classes of generalized
interacting automata parallelism does not yield to more computational capacity
than obtained by a single sequential cell. Moreover, it is proved that there
exists a unary complexity class in between the real-time and linear-time OCA
languages, and that there is a gap between the unary real-time OCA languages
and that class. Regarding nondeterminism as limited resource it is shown that a
slight increase of the degree of nondeterminism as well as adding two-way
communication reduces the time complexity from linear time to real time.
Furthermore, by adding a wee bit nondeterminism an infinite hierarchy of unary
language families dependent on the degree of nondeterminism is derived.
