# Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata

Modanese, Augusto

## Abstract:

After an apparent hiatus of roughly 30 years, we revisit a seemingly neglected subject in the theory of (one-dimensional) cellular automata: sublinear-time computation. The model considered is that of ACAs, which are language acceptors whose acceptance condition depends on the states of all cells in the automaton. We prove a time hierarchy theorem for sublinear-time ACA classes, analyze their intersection with the regular languages, and, finally, establish strict inclusions in the parallel computation classes SC and (uniform) AC. As an addendum, we introduce and investigate the concept of a decider ACA (DACA) as a candidate for a decider counterpart to (acceptor) ACAs. We show the class of languages decidable in constant time by DACAs equals the locally testable languages, and we also determine $\Omega(\sqrt{n})$ as the (tight) time complexity threshold for DACAs up to which no advantage compared to constant time is possible.

 Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI) Publikationstyp Forschungsbericht/Preprint Publikationsjahr 2021 Sprache Englisch Identifikator ISSN: 0129-0541, 1793-6373 KITopen-ID: 1000136168 Vorab online veröffentlicht am 09.07.2021 Nachgewiesen in arXiv Relationen in KITopen Verweist aufSublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata. Modanese, Augusto (2021) Zeitschriftenaufsatz (1000136167)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page