key: cord-0043822-i6pohkl9
authors: Modanese, Augusto
title: Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
date: 2020-05-26
journal: Developments in Language Theory
DOI: 10.1007/978-3-030-48516-0_19
sha: ec00acbbbcb2af74ac301700d44426fab08f33f1
doc_id: 43822
cord_uid: i6pohkl9

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 [Formula: see text] and (uniform) [Formula: see text]. 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 [Formula: see text] as the (tight) time complexity threshold for DACAs up to which no advantage compared to constant time is possible.

While there have been several works on linear-and real-time language recognition by cellular automata over the years (see, e.g., [14, 24] for an overview), interest in the sublinear-time case has been scanty at best. We can only speculate this has been due to a certain obstinacy concerning what is now the established acceptance condition for cellular automata, namely that the first cell determines the automaton's response, despite alternatives being long known [18] . Under this condition, only a constant-size prefix can ever influence the automaton's decision, which effectively dooms sublinear time to be but a trivial case just as it is for (classical) Turing machines, for example. Nevertheless, at least in the realm of Turing machines, this shortcoming was readily circumvented by adding a random access mechanism to the model, thus sparking rich theories on parallel computation [5, 20] , probabilistically checkable proofs [23] , and property testing [8, 19] .

In the case of cellular automata, the adaptation needed is an alternate (and by all means novel) acceptance condition, covered in Sect. 2. Interestingly, in the Some proofs have been omitted due to page constraints. These may be found in the full version of the paper [17] . resulting model, called ACA, parallelism and local behavior seem to be more marked features, taking priority over cell communication and synchronization algorithms (which are the dominant themes in the linear-and real-time constructions). As mentioned above, the body of theory on sublinear-time ACAs is very small and, to the best of our knowledge, resumes itself to [10, 13, 21] . Ibarra et al. [10] show sublinear-time ACAs are capable of recognizing non-regular languages and also determine a threshold (namely Ω(log n)) up to which no advantage compared to constant time is possible. Meanwhile, Kim and McCloskey [13] and Sommerhalder and Westrhenen [21] analyze the constant-time case subject to different acceptance conditions and characterize it based on the locally testable languages, a subclass of the regular languages.

Indeed, as covered in Sect. 3, the defining property of the locally testable languages, that is, that words which locally appear to be the same are equivalent with respect to membership in the language at hand, effectively translates into an inherent property of acceptance by sublinear-time ACAs. In Sect. 4, we prove a time hierarchy theorem for sublinear-time ACAs as well as further relate the language classes they define to the regular languages and the parallel computation classes SC and (uniform) AC. In the same section, we also obtain an improvement on a result of [10] . Finally, in Sect. 5 we consider a plausible model of ACAs as language deciders, that is, machines which must not only accept words in the target language but also explicitly reject those which do not. Section 6 concludes.

We assume the reader is familiar with the theory of formal languages and cellular automata as well as with computational complexity theory (see, e.g., standard references [1, 6] ). This section reviews basic concepts and introduces ACAs.

Z denotes the set of integers, N + that of (strictly) positive integers, and

For a word w ∈ Σ * over an alphabet Σ, w(i) is the i-th symbol of w (starting with the 0-th symbol), and |w| x is the number of occurrences of x ∈ Σ in w. For k ∈ N 0 , p k (w), s k (w), and I k (w) are the prefix, suffix and set of infixes of length k of w, respectively, where p k (w) = s k (w) = w and I k (w) = {w} for k ≥ |w|. Σ ≤k is the set of words w ∈ Σ * for which |w| ≤ k. Unless otherwise noted, n is the input length.

The class REG of regular languages is defined in terms of (deterministic) automata with finite memory and which read their input in a single direction (i.e., from left to right), one symbol at a time; once all symbols have been read, the machine outputs a single bit representing its decision. In contrast, a scanner is a memoryless machine which reads a span of k ∈ N + symbols at a time of an input provided with start and end markers (so it can handle prefixes and suffixes separately); the scanner validates every such substring it reads using the same predicate, and it accepts if and only if all these validations are successful. The languages accepted by these machines are the strictly locally testable languages. 1 Definition 1 (strictly locally testable). Let Σ be an alphabet. A language L ⊆ Σ * is strictly locally testable if there is some k ∈ N + and sets π, σ ⊆ Σ ≤k and μ ⊆ Σ k such that, for every word w ∈ Σ * , w ∈ L if and only if p k (w) ∈ π, I k (w) ⊆ μ, and s k (w) ∈ σ. SLT is the class of strictly locally testable languages.

A more general notion of locality is provided by the locally testable languages. Intuitively, L is locally testable if a word w being in L or not is entirely dependent on a property of the substrings of w of some constant length k ∈ N + (that depends only on L, not on w). Thus, if any two words have the same set of substrings of length k, then they are equivalent with respect to being in L:

LT denotes the class of locally testable languages.

LT is the Boolean closure of SLT, that is, its closure under union, intersection, and complement [16] . In particular, SLT LT (i.e., the inclusion is proper [15] ).

In this paper, we are strictly interested in one-dimensional cellular automata with the standard neighborhood. For r ∈ N 0 , let N r (z) = {z ∈ Z | |z − z | ≤ r} denote the extended neighborhood of radius r of the cell z ∈ Z.

A cellular automaton ( CA) C is a triple (Q, δ, Σ) where Q is a finite, non-empty set of states, δ : Q 3 → Q is the local transition function, and Σ ⊆ Q is the input alphabet. An element of Q 3 (resp., Q Z ) is called a local (resp., global) configuration of C. δ induces the global transition function Δ :

Our interest in CAs is as machines which receive an input and process it until a final state is reached. The input is provided from left to right, with one cell for each input symbol. The surrounding cells are inactive and remain so for the entirety of the computation (i.e., the CA is bounded). It is customary for CAs to have a distinguished cell, usually cell zero, which communicates the machine's output. As mentioned in the introduction, this convention is inadequate for computation in sublinear time; instead, we require the finality condition to depend on the entire (global) configuration (modulo inactive cells): 

There is a distinguished state q ∈ Q \ Σ, called the inactive state, which, for every z 1 , z 2 , z 3 ∈ Q, satisfies δ(z 1 , z 2 , z 3 ) = q if and only if z 2 = q. A cell not in state q is said to be active. For an input w ∈ Σ * , the initial configuration

and c contains only states in F ∪{q}. In this context, the sequence c 0 , . . . , Δ τ (c 0 ) = c is the trace of w, and τ is the time complexity of C (with respect to F and w).

Because we effectively consider only bounded CAs, the computation of w involves exactly |w| active cells. The surrounding inactive cells are needed only as markers for the start and end of w. As a side effect, the initial configuration c 0 = c 0 (ε) for the empty word ε is stationary (i.e., Δ(c 0 ) = c 0 ) regardless of the choice of δ. Since this is the case only for ε, we disregard it for the rest of the paper, that is, we assume it is not contained in any of the languages considered.

Finally, we relate final configurations and computation results. We adopt an acceptance condition as in [18, 21] and obtain a so-called ACA; here, the "A" of "ACA" refers to the property that all (active) cells are relevant for acceptance.

An ACA is a CA C with a non-empty subset A ⊆ Q\{q} of accept states. For w ∈ Σ + , if C reaches an A-final configuration, we say C accepts w. L(C) denotes the set of words accepted by C. For t : N + → N 0 , we write ACA(t) for the class of languages accepted by an ACA with time complexity bounded by t, that is, for which the time complexity of accepting w is ≤ t(|w|).

is immediate for functions t 1 , t 2 : N + → N 0 with t 1 (n) ≤ t 2 (n) for every n ∈ N + . Because Definition 5 allows multiple accept states, it is possible for each (non-accepting) state z to have a corresponding accept state z A . In the rest of this paper, when we say a cell becomes (or marks itself as) accepting (without explicitly mentioning its state), we intend to say it changes from such a state z to z A . Figure 1 illustrates the computation of an ACA with input alphabet Σ = {0, 1} and which accepts {01} + with time complexity equal to one (step). The local transition function is such that δ(0, 1, 0) = δ(1, 0, 1) = δ(q, 0, 1) = δ(0, 1, q) = a, a being the (only) accept state, and δ(z 1 , z 2 , z 3 ) = z 2 for z 2 = a and arbitrary z 1 and z 3 .

This section recalls results on sublinear-time ACA computation (i.e., ACA(t) where t ∈ o(n)) from [10, 13, 21] and provides some additional remarks. We start with the constant-time case (i.e., ACA(O(1))). Here, the connection between scanners and ACAs is apparent: If an ACA accepts an input w in time τ = τ (w), then w can be verified by a scanner with an input span of 2τ + 1 symbols and using the predicate induced by the local transition function of the ACA (i.e., the predicate is true if and only if the symbols read correspond to N τ (z) for some cell z in the initial configuration and z is accepting after τ steps).

Constant-time ACA computation has been studied in [13, 21] . Although in [13] we find a characterization based on a hierarchy over SLT, the acceptance condition there differs slightly from that in Definition 5; in particular, the automata there run for a number of steps which is fixed for each automaton, and the outcome is evaluated (only) in the final step. In contrast, in [21] we find the following, where SLT ∨ denotes the closure of SLT under union:

Thus, ACA(O(1)) is closed under union. In fact, more generally:

Moving beyond constant time, in [10] we find the following:

In [10] we find an example for a non-regular language in ACA(O(log n)) which is essentially a variation of the language

To illustrate the ideas involved, we present an example related to BIN (though it results in a different time complexity) and which is also useful in later discussions in Sect. 5. Let w k (i) = 0 i 10 k−i−1 and consider the language

of all identity matrices in line-for-line representations, where the lines are separated by # symbols. 2 We now describe an ACA for IDMAT; the construction closely follows the aforementioned one for BIN found in [10] (and the difference in complexity is only due to the different number and size of blocks in the words of IDMAT and BIN). Denote each group of cells initially containing a (maximally long) {0, 1} + substring of w ∈ IDMAT by a block. Each block of size b propagates its contents to the neighboring blocks (in separate registers); using a textbook CA technique, this requires exactly 2b steps. Once the strings align, a block initially containing w k (i) verifies it has received w k (i − 1) and w k (i + 1) from its left and right neighbor blocks (if either exists), respectively. The cells of a block and its delimiters become accepting if and only if the comparisons are successful and there is a single # between the block and its neighbors. This process takes linear time in b; since any w ∈ IDMAT has O( |w|) many blocks, each with b ∈ O( |w|) cells, it follows that IDMAT ∈ ACA(O( √ n)). To show the above construction is time-optimal, we use the following observation, which is also central in proving several other results in this paper: Lemma 9. Let C be an ACA, and let w be an input which C accepts in (exactly) τ = τ (w) steps. Then, for every input w such that p 2τ (w) = p 2τ (w ),

The lemma is intended to be used with τ < |w| 2 since otherwise w = w . It can be used, for instance, to show that (1)) (e.g., simply set 0 as the ACA's accepting state), ACA(t) is not closed under complement for any t ∈ o(n). Also, SOMEONE is a regular language and BIN ∈ ACA(O(log n)) is not, so we have:

If the inclusion of infixes in Lemma 9 is strengthened to an equality, one may apply it in both directions and obtain the following stronger statement: Lemma 11. Let C be an ACA with time complexity bounded by t : N + → N 0 (i.e., C accepts any input of length n in at most t(n) steps). Then, for any two inputs w and w with p 2μ (w) = p 2μ (w ), I 2μ+1 (w) = I 2μ+1 (w ), and s 2μ (w) = s 2μ (w ) where μ = max{t(|w|), t(|w |)}, we have that w ∈ L(C) if and only if w ∈ L(C).

Finally, we can show our ACA for IDMAT is time-optimal:

In this section, we present various results regarding ACA(t) where t ∈ o(n). First, we obtain a time hierarchy theorem, that is, under plausible conditions, ACA(t ) ACA(t) for t ∈ o(t). Next, we show ACA(t) ∩ REG is (strictly) contained in LT and also present an improvement to Theorem 8. Finally, we study inclusion relations between ACA(t) and the SC and (uniform) AC hierarchies. Save for the material covered so far, all three subsections stand out independently from one another.

For functions f, t : N + → N 0 , we say f is time-constructible by CAs in t(n) time if there is a CA C which, on input 1 n , reaches a configuration containing the value f (n) (binary-encoded) in at most t(n) steps. 3 Note that, since CAs can simulate (one-tape) Turing machines in real-time, any function constructible by Turing machines (in the corresponding sense) is also constructible by CAs.

, and let f and g be time-constructible (by CAs) in f (n) time. Furthermore, let t : N + → N 0 be such that 3f (k) ≤ t(f (k)g(k)) ≤ cf (k) for some constant c ≥ 3 and all but finitely many k ∈ N + . Then, for every t ∈ o(t), ACA(t ) ACA(t).

Given a > 1, this can be used, for instance, with any time-constructible f ∈ Θ(n a ) (resp., f ∈ Θ(2 n/a ), in which case a = 1 is also possible) and t ∈ Θ((log n) a ) (resp., t ∈ Θ(n 1/a )). The proof idea is to construct a language L similar to BIN (see Sect. 3) in which every w ∈ L has length exponential in the size of its blocks while the distance between any two blocks is Θ(t(|w|)). Due to Lemma 9, the latter implies L is not recognizable in o(t(|w|)) time.

and τ = t (|w k |) and applying Lemma 9 for sufficiently large k yields L ∈ ACA(t ).

By assumption it suffices to show w = w k ∈ L is accepted by an ACA C in at most 3f (k) ≤ t(|w|) steps for sufficiently large k ∈ N + . The cells of C perform two procedures P 1 and P 2 simultaneously: P 1 is as in the ACA for BIN (see Sect. 3) and ensures that the blocks of w have the same length, that the respective binary encodings are valid, and that the last value is correct (i.e., equal to g(k) − 1). In P 2 , each block computes f (k) as a function of its block length k. Subsequently, the value f (k) is decreased using a real-time counter (see, e.g., [12] for a construction). Every time the counter is decremented, a signal starts from the block's leftmost cell and is propagated to the right. This allows every group of cells of the form bs with b ∈ {0, 1} + and s ∈ {#} + to assert there are precisely f (k) symbols in total (i.e., |bs| = f (k)). A cell is accepting if and only if it is accepting both in P 1 and P 2 . The proof is complete by noticing either procedure takes a maximum of 3f (k) steps (again, for sufficiently large k).

In light of Proposition 10, we now consider the intersection ACA(t) ∩ REG for t ∈ o(n) (in the same spirit as a conjecture by Straubing [22] ). For this section, we assume the reader is familiar with the theory of syntactic semigroups (see, e.g., [7] for an in-depth treatment).

Given a language L, let SS(L) denote the syntactic semigroup of L. It is well-known that SS(L) is finite if and only if L is regular. A semigroup S is a semilattice if x 2 = x and xy = yx for every x, y ∈ S. Additionally, S is locally semilattice if eSe is a semilattice for every idempotent e ∈ S, that is, e 2 = e. We use the following characterization of locally testable languages:

In conjunction with Lemma 9, this yields the following, where the strict inclusion is due to SOMEONE ∈ ACA(t) (since SOMEONE ∈ LT; see Sect. 3):

Proof. Let L ∈ ACA(t) be a language over the alphabet Σ and, in addition, let L ∈ REG, that is, S = SS(L) is finite. By Theorem 14, it suffices to show S is locally semilattice. To that end, let e ∈ S be idempotent, and let x, y ∈ S.

To show (exe)(eye) = (eye)(exe), let a, b ∈ Σ * and consider the words u = a(exe)(eye)b and v = a(eye)(exe)b. For m ∈ N + , let u m = a(e m xe m )(e m ye m )b, and let r ∈ N + be such that r > max{|x|, |y|, |a|, |b|} and also t(|u 2r+1 |) < 1 16|e| |u 2r+1 | < r. Since e is idempotent, u = u 2r+1 and u belong to the same class in S, that is, u ∈ L if and only if u ∈ L; the same is true for v = a(e 2r+1 ye 2r+1 )(e 2r+1 xe 2r+1 )b and v. Furthermore, p 2r (u ) = p 2r (v ), I 2r+1 (u ) = I 2r+1 (v ), and s 2r (u ) = s 2r (v ) hold. Since L ∈ ACA(t), Lemma 11 applies.

The proof of (exe)(exe) = exe is analogous. Simply consider the words a(e m xe m )b and a(e m xe m )(e m xe m )b for sufficiently large m ∈ N + and use, again, Lemma 11 and the fact that e is idempotent.

Using Theorems 8 and 15, we have ACA(t)

LT for t ∈ o(log n). We can improve this bound to ACA(O(1)) = SLT ∨ , which is a proper subset of LT: Proof. We prove every ACA C with time complexity at most t ∈ o(log n) actually has O(1) time complexity. Let Q be the state set of C and assume |Q| ≥ 2, and let n 0 ∈ N + be such that t(n) < log n 9 log |Q| for n ≥ n 0 . Letting k(n) = 2t(n) + 1 and assuming t(n) ≥ 1, we then have |Q| 3k(n) ≤ |Q| 9t(n) < n ( ). We shall use this to prove that, for any word w ∈ L of length |w| ≥ n 0 , there is a word w ∈ L of length |w | ≤ n 0 as well as r < n 0 such that p r (w) = p r (w ), I r+1 (w) = I r+1 (w ), and s r (w) = s r (w ). By Lemma 9, C must have t(|w |) time complexity on w and, since the set of all such w is finite, it follows that C has O(1) time complexity. Now let w be as above and let C accept w in (exactly) τ = τ (w) ≤ t(|w|) steps. We prove the claim by induction on |w|. The base case |w| = n 0 is trivial, so let n > n 0 and assume the claim holds for every word in L of length strictly less than n. Consider the De Bruijn graph G over the words in |Q| κ where κ = 2τ +1. Then, from the infixes of w of length κ (in order of appearance in w) one obtains a path P in G by starting at the leftmost infix and visiting every subsequent one, up to the rightmost one. Let G be the induced subgraph of G containing exactly the nodes visited by P , and notice P visits every node in G at least once. It is not hard to show that, for every such P and G , there is a path P in G with the same starting and ending points as P and that visits every node of G at least once while having length at most m 2 ≤ |Q| 2κ , where m is the number of nodes in G . 4 To this P corresponds a word w of length |w | ≤ κ + |Q| 2κ < |Q| 3κ for which, by construction of P and G , p κ−1 (w ) = p κ−1 (w), I κ (w ) = I κ (w), and s κ−1 (w ) = s κ−1 (w ). Since κ ≤ k(|w|), using ( ) we have |w | < |w|, and then either |w | ≤ n 0 and κ < n 0 (since otherwise w = w , which contradicts |w | < |w|), or we may apply the induction hypothesis; in either case, the claim follows.

In this section, we relate ACA(t) to other classes which characterize parallel computation, namely the SC and (uniform) AC hierarchies. In this context, SC k is the class of problems decidable by Turing machines in O((log n) k ) space and polynomial time, whereas AC k is that decidable by Boolean circuits with polynomial size, O((log n) k ) depth, and gates with unbounded fan-in. SC (resp., AC) is the union of all SC k (resp., AC k ) for k ∈ N 0 . Here, we consider only uniform versions of AC; when relevant, we state the respective uniformity condition. Although SC 1 = L ⊆ AC 1 is known, it is unclear whether any other containment holds between SC and AC.

One should not expect to include SC or AC in ACA(t) for any t ∈ o(n). Conceptually speaking, whereas the models of SC and AC are capable of random access to their input, ACAs are inherently local (as evinced by Lemmas 9 and 11). Explicit counterexamples may be found among the unary languages: For any fixed m ∈ N + and w 1 , w 2 ∈ {1} + with |w 1 |, |w 2 | ≥ m, trivially p m−1 (w 1 ) = p m−1 (w 2 ), I m (w 1 ) = I m (w 2 ), and s m−1 (w 1 ) = s m−1 (w 2 ) hold. Hence, by Lemma 9, if an ACA C accepts w ∈ {1} + in t ∈ o(n) time and |w| is large (e.g., |w| > 4t(|w|)), then C accepts any w ∈ {1} + with |w | ≥ |w|. Thus, extending a result from [21] : Proposition 17. If t ∈ o(n) and L ∈ ACA(t) is a unary language (i.e., L ⊆ Σ + and |Σ| = 1), then L is either finite or co-finite.

In light of the above, the rest of this section is concerned with the converse type of inclusion (i.e., of ACA(t) in the SC or AC hierarchies). For f, s, t : N + → N 0 with f (n) ≤ s(n), we say f is constructible (by a Turing machine) in s(n) space and t(n) time if there is a Turing machine T which, on input 1 n , outputs Thus, for polylogarithmic t (where the strict inclusion is due to Proposition 17):

Moving on to the AC classes, we employ some notions from descriptive complexity theory (see, e.g., [11] for an introduction). Let FO L [t] be the class of languages describable by first-order formulas with numeric relations in L (i.e., logarithmic space) and quantifier block iterations bounded by t : N + → N 0 . Theorem 20. Let t : N + → N 0 with t(n) ≥ log n be constructible in logarithmic space (and arbitrary time). For any ACA C whose time complexity is bounded by t,

Since FO L [O((log n) k )] equals L-uniform AC k [11] , by Proposition 17 we have:

Because SC 1 ⊆ AC 0 (regardless of non-uniformity) [9] , this is an improvement on Corollary 19 at least for k = 1. Nevertheless, note the usual uniformity condition for AC 0 is not Lbut the more restrictive DLOGTIME-uniformity [25] , and there is good evidence that these two versions of AC 0 are distinct [4] . Using methods from [2] , Corollary 21 may be rephrased for AC 0 in terms of TIME(polylog(n))or even TIME((log n) 2 )-uniformity, but the DLOGTIMEuniformity case remains unclear.

So far, we have considered ACAs strictly as language acceptors. As such, their time complexity for inputs not in the target language (i.e., those which are not accepted) is entirely disregarded. In this section, we investigate ACAs as deciders, that is, as machines which must also (explicitly) reject invalid inputs. We analyze the case in which these decider ACAs must reject under the same condition as acceptance (i.e., all cells are simultaneously in a final rejecting state):

A decider ACA ( DACA) is an ACA C which, in addition to its set A of accept states, has a non-empty subset R ⊆ Q \ {q} of reject states that is disjoint from A (i.e., A ∩ R = ∅). Every input w ∈ Σ + of C must lead to an A-or an R-final configuration (or both). C accepts w if it leads In contrast to Definition 5, here we must be careful so that the accept and reject results do not overlap (i.e., a word cannot be both accepted and rejected). We opt for interpreting the first (chronologically speaking) of the final configurations as the machine's response. Since the outcome of the computation is then irrelevant regardless of any subsequent configurations (whether they are final or not), this is equivalent to requiring, for instance, that the DACA must halt once a final configuration is reached.

One peculiar consequence of Definition 22 is the relation between languages which can be recognized by acceptor ACAs and DACAs (i.e., the classes ACA(t) and DACA(t)). As it turns out, the situation is quite different from what is usually expected of restricting an acceptor model to a decider one, that is, that deciders yield a (possibly strictly) more restricted class of machines. In fact, one can show DACA(t) ⊆ ACA(t) holds for t ∈ o(n) since SOMEONE ∈ ACA(O(1)) (see discussion after Lemma 9); nevertheless, SOMEONE ∈ DACA(O(1)). For example, the local transition function δ of the DACA can be chosen as δ(z 1 , 0, z 2 ) = r and δ(z 1 , z, z 2 ) = a for z ∈ {1, a, r}, where z 1 and z 2 are arbitrary states, and a and r are the (only) accept and reject states, respectively; see Fig. 2 . Choosing the same δ for an (acceptor) ACA does not yield an ACA for SOMEONE since then all words of the form 0 + are accepted in the second step (as they are not rejected in the first one). We stress this rather counterintuitive phenomenon occurs only in the case of sublinear time (as ACA(t) = CA(t) = DACA(t) for t ∈ Ω(n)).

Similar to (acceptor) ACAs (Lemma 9), sublinear-time DACAs operate locally: Lemma 23. Let C be a DACA and let w ∈ {0, 1} + be a word which C decides in exactly τ = τ (w) steps. Then, for every word w ∈ {0, 1} + with p 2τ (w) = p 2τ (w ), I 2τ +1 (w ) = I 2τ +1 (w), and s 2τ (w) = s 2τ (w ), C decides w in ≤ τ steps, and w ∈ L(C) holds if and only if w ∈ L(C).

One might be tempted to relax the requirements above to I 2τ +1 (w ) ⊆ I 2τ +1 (w) (as in Lemma 9) . We stress, however, the equality I 2τ +1 (w) = I 2τ +1 (w ) is crucial; otherwise, it might be the case that C takes strictly less than τ steps to decide w and, hence, w ∈ L(C) may not be equivalent to w ∈ L(C).

We note that, in addition to Lemmas 9 and 11, the results from Sect. 4 are extendable to decider ACAs; a more systematic treatment is left as a topic for future work. The remainder of this section is concerned with characterizing DACA(O(1)) computation (as a parallel to Theorem 6) as well as establishing the time threshold for DACAs to decide languages other than those in DACA(O(1)) (as Theorem 16 and the result BIN ∈ ACA(O(log n)) do for acceptor ACAs).

First notice that, for any DACA C, swapping the accept and reject states yields a DACA with the same time complexity and which decides the complement of L(C). Hence, in contrast to ACAs (see discussion following Lemma 9): Using this, we can prove the following, which characterizes constant-time DACA computation as a parallel to Theorem 6:

Hence, we obtain the rather surprising inclusion ACA(O(1)) DACA(O(1)), that is, for constant time, DACAs constitute a strictly more powerful model than their acceptor counterparts.

Theorem 16 establishes a logarithmic time threshold for (acceptor) ACAs to recognize languages not in ACA(O(1)). We now turn to obtaining a similar result for DACAs. As it turns out, in this case the bound is considerably larger: One immediate implication is that DACA(t) and ACA(t) are incomparable for t ∈ o( √ n) ∩ ω(1) (since, e.g., BIN ∈ ACA(log n); see Sect. 3). The proof idea is that any DACA whose time complexity is not constant admits an infinite sequence of words with increasing time complexity; however, the time complexity of each such word can be traced back to a critical set of cells which prevent the automaton from either accepting or rejecting. By contracting the words while keeping the extended neighborhoods of these cells intact, we obtain a new infinite sequence of words which the DACA necessarily takes Ω( √ n) time to decide:

Proof. Let C be a DACA with time complexity bounded by t and assume t ∈ O(1); we show t ∈ Ω( √ n). Since t ∈ O(1), for every i ∈ N 0 there is a w i such that C takes strictly more than i steps to decide w i . In particular, when C receives w i as input, there are cells x i j and y i j for j ∈ {0, . . . , i} such that x i j (resp., y i j ) is not accepting (resp., rejecting) in step j. Let J i be the set of all z ∈ {0, . . . , |w i | − 1} for which min{|z − x i j |, |z − y i j |} ≤ j, that is, z ∈ N j (x i j ) ∪ N j (y i j ) for some j. Consider the restriction w i of w i to the symbols having index in J i , that is,

. . , j m−1 } and j 0 < · · · < j m−1 , and notice w i has the same property as w i (i.e., C takes strictly more than i steps to decide w i ). Since |w i | = |J i | ≤ 2(i + 1) 2 , C has Ω( √ n) time complexity on the (infinite) set {w i | i ∈ N 0 }.

Using IDMAT (see Sect. 3), we show the bound in Theorem 26 is optimal:

Proposition 27. IDMAT ∈ DACA(O( √ n)).

We have IDMAT ∈ ACA(O( √ n)) (see Sect. 3); the non-trivial part is ensuring the DACA also rejects every w ∈ IDMAT in O( |w|) time. In particular, in such strings the # delimiters may be an arbitrary number of cells apart or even absent altogether; hence, naively comparing every pair of blocks is not an option. Rather, we check the existence of a particular set of substrings of increasing length and which must present if the input is in IDMAT. Every O(1) steps the existence of a different substring is verified; the result is that the input length must be at least quadratic in the length of the last substring tested (and the input is timely rejected if it does not contain any one of the required substrings).

Following the definition of ACAs in Sect. 2, Sect. 3 reviewed existing results on ACA(t) for sublinear t (i.e., t ∈ o(n)); we also observed that sublinear-time ACAs operate in an inherently local manner (Lemmas 9 and 11). In Sect. 4, we proved a time hierarchy theorem (Theorem 13), narrowed down the languages in ACA(t)∩REG (Theorem 15), improved Theorem 8 to ACA(o(log n)) = ACA(O(1)) (Theorem 16), and, finally, obtained (strict) inclusions in the parallel computation classes SC and AC (Corollaries 19 and 21, respectively). The existence of a hierarchy theorem for ACAs is of interest because obtaining an equivalent result for NC and AC is an open problem in computational complexity theory. Also of note is that the proof of Theorem 13 does not rely on diagonalization (the prevalent technique for most computational models) but, rather, on a quintessential property of sublinear-time ACA computation (i.e., locality as in the sense of Lemma 9).

In Sect. 5, we considered a plausible definition of ACAs as language deciders as opposed to simply acceptors, obtaining DACAs. The respective constant-time class is LT (Theorem 25), which surprisingly is a (strict) superset of ACA(O(1)) = SLT ∨ . Meanwhile, Ω( √ n) is the time complexity threshold for deciding languages other than those in LT (Theorem 26 and Proposition 27).

As for future work, the primary concern is extending the results of Sect. 4 to DACAs. DACA(O(1)) = LT is closed under union and intersection and we saw that DACA(t) is closed under complement for any t ∈ o(n); a further question would be whether DACA(t) is also closed under union and intersection. Finally 

Computational Complexity -A Modern Approach

Extensions of an idea of McNaughton

Characterizations of locally testable events

Nondeterministic NC 1 computation

A taxonomy of problems with fast parallel algorithms

Cellular Automata. A Parallel Model. Mathematics and Its Application

Automata, Languages, and Machines. Pure and Applied Mathematics

The art of uninformed decisions

Parity, circuits, and the polynomial-time hierarchy

Fast parallel language recognition by cellular automata

Descriptive Complexity. Texts in Computer Science

Constructible functions in cellular automata and their applications to hierarchy results

A characterization of constant-time cellular automata computation

Cellular automata and language theory

Algebraic decision procedures for local testability

Counter-Free Automata

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

Picture Languages: Formal Models for Picture Recognition

Ronitt Rubinfeld and Asaf Shapira: Sublinear time algorithms

On uniform circuit complexity

Parallel language recognition in constant time by cellular automata

Finite Automata, Formal Logic, and Circuit Complexity

Probabilistically checkable proofs

Language recognition by cellular automata

Introduction to Circuit Complexity -A Uniform Approach

Acknowledgments. I would like to thank Thomas Worsch for the fruitful discussions and feedback during the development of this work. I would also like to thank the DLT 2020 reviewers for their valuable comments and suggestions and, in particular, one of the reviewers for pointing out a proof idea for Theorem 16, which was listed as an open problem in a preliminary version of the paper.