KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel turing machines with one-head control units and cellular automata

Worsch, Thomas

Abstract:

Parallel Turing machines (PTM) can be viewed as a generalization of
cellular automata (CA) where an additional measure called processor
complexity can be defined which indicates the ``amount of
parallelism'' used. In this paper PTM are investigated with respect to
their power as recognizers of formal languages. A combinatorial
approach as well as diagonalization are used to obtain hierarchies of
complexity classes for PTM and CA. In some cases it is possible to
keep the space complexity of PTM fixed. Thus for the first time it is
possible to find hierarchies of complexity classes (though not CA
classes) which are completely contained in the class of languages
recognizable by CA with space complexity n and in polynomial time. A
possible collapse of the time hierarchy for these CA would therefore
also imply some unexpected properties of PTM.


Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Informatik – Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.)
Publikationstyp Buch
Publikationsjahr 1997
Sprache Englisch
Identifikator urn:nbn:de:swb:90-AAA42970
KITopen-ID: 4297
Erscheinungsvermerk Karlsruhe 1997. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1997,3.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page