Abstract of Paper

Iterative Arrays with Small Time Bounds
by Thomas Buchholz, Andreas Klein, Martin Kutrib

Abstract:

An iterative array is a line of interconnected interacting finite automata.
One distinguished automaton, the communication cell, is connected to the
outside world and fetches the input serially symbol by symbol.  Sometimes in
the literature this model is referred to as cellular automaton with
sequential input mode. We investigate deterministic iterative arrays (IA)
with small time bounds between real-time and linear-time.  It is shown that
there exists an infinite dense hierarchy of strictly included complexity
classes in that range. The result closes the last gap in the time hierarchy
of IAs.