KIT | KIT-Bibliothek | Impressum | Datenschutz

Simulations between alternating CA, alternating TM and circuit families

Reischle, Frank; Worsch, Thomas

Variants of cellular automata consisting of alternating instead of
deterministic finite automata are investigated, so-called uniform
alternating CA (ACA) and two types of nonuniform ACA. The former two
have been considered by Matamala (1997). It is shown that the
nonuniform ACA are time equivalent. The main contributions are fast
simulations of ACA by uniform circuit families and vice versa. It is
shown that nonuniform ACA are time equivalent to circuit families with
unbounded fan-in, and that uniform ACA are time equivalent to circuit
families with constant fan-in. Hence uniform ACA and alternating TM
are time equivalent, too, solving a problem left open by Matamala. The
results also give some evidence that a linear time simulation of
nonuniform ACA by ATM is ``unlikely'' to exist.

Volltext §
DOI: 10.5445/IR/19798
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 Forschungsbericht/Preprint
Publikationsjahr 1998
Sprache Englisch
Identifikator ISSN: 1432-7864
KITopen-ID: 19798
Verlag Universität Karlsruhe (TH)
Umfang 18 S.
Serie Interner Bericht. Universität Karlsruhe, Fakultät für Informatik ; 1998,9
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page