Augusto Modanese
email: modanese@kit.edu

Complexity-Theoretic Aspects of Expanding Cellular Automata

The expanding cellular automata (XCA) variant of cellular automata is investigated and characterized from a complexity-theoretical standpoint. The respective polynomial-time complexity class is shown to coincide with ≤ p tt (NP), that is, the class of decision problems polynomialtime truth-table reducible to problems in NP. Corollaries on select XCA variants are proven: XCAs with multiple accept and reject states are shown to be polynomial-time equivalent to the original XCA model. Meanwhile, XCAs with diverse acceptance behavior are classified in terms of ≤ p tt (NP) and the Turing machine polynomial-time class P.

Introduction

Traditionally, cellular automata (CAs) are defined as a rigid and immutable lattice of cells; their behavior is dictated exclusively by a local transition function operating on homogeneous local configurations. This can be generalized, for instance, by mutable neighborhoods [START_REF] Rosenfeld | Reconfigurable Cellular Computers[END_REF] or by endowing CAs with the ability to shrink, that is, delete their cells [START_REF] Rosenfeld | Fast language acceptance by shrinking cellular automata[END_REF]. When shrinking, the automaton's structure and dimension are preserved by "gluing" the severed parts and reconnecting their delimiting cells as neighbors. When employed as language recognizers, shrinking CAs (SCAs) can be more efficient than standard CAs [START_REF] Rosenfeld | Fast language acceptance by shrinking cellular automata[END_REF][START_REF] Kutrib | Shrinking One-Way Cellular Automata[END_REF].

Other variants of CAs with dynamically reconfigurable neighborhoods have emerged throughout the years. In the case of two-dimensional CAs, there is the structurally dynamical CA (SDCA) [START_REF] Ilachinski | Structurally Dynamic Cellular Automata[END_REF], in which the connections between neighbors are created and dropped depending on the local configuration. In the one-dimensional case, further variants in this sense are considered in the work of Dubacq [START_REF] Dubacq | Different Kinds of Neighborhood-Varying Cellular Automata[END_REF], where one finds, in particular, CAs whose neighborhoods vary over time. Dubacq also proposes the dynamically reconfigurable CA (DRCA), a CA whose cells are able to exchange their neighbors for neighbors of their neighbors. Dantchev [START_REF] Dantchev | Dynamic Neighbourhood Cellular Automata[END_REF] later points out a drawback in the definition of DRCAs and proposes an alternative dubbed the dynamic neighborhood CA (DNCA).

By relaxing the arrangement of cells as a lattice, CAs may be generalized to graphs. Graph automata [START_REF] Tomita | Graph automata: natural expression of self-reproduction[END_REF] are related to CAs in that each vertex in the graph can be identified as a cell; thus, graphs whose vertices have finite degrees provide a natural generalization of CAs. In [START_REF] Tomita | Graph automata: natural expression of self-reproduction[END_REF], the authors also define a rule based on topological refinements of graphs, which may be used as a model for biological cell division. An additional example of cell division in this sense is found in the "inflating grid" described in [START_REF] Arrighi | Causal graph dynamics[END_REF].

Modeling cell division and growth, in fact, was one of the driving motivations towards the investigation of the expanding CA (XCA) in [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF]. An XCA is, in a way, the opposite of an SCA; instead of cells vanishing, new cells can emerge between existing ones. This operation is topologically similar to the cell division of graph automata; as in the SCA model, however, it maintains the overall arrangement and connectivity of the automaton's cells as similar as possible to that of standard CAs (i.e., a bi-infinite, one-dimensional array of cells).

We mention a few aspects in which XCAs differ from the aforementioned variants. Contrary to SDCAs [START_REF] Ilachinski | Structurally Dynamic Cellular Automata[END_REF] or CAs with dynamic neighborhoods such as DRCAs [START_REF] Dubacq | Different Kinds of Neighborhood-Varying Cellular Automata[END_REF] and DNCAs [START_REF] Dantchev | Dynamic Neighbourhood Cellular Automata[END_REF], XCAs enable the creation of new cells, not simply new links between existing ones. In addition, the XCA model does not focus as much on the reconfiguration of cells; in it, the neighborhoods are homogeneous and predominantly immutable. Furthermore, in contrast to the far more general graph automata [START_REF] Tomita | Graph automata: natural expression of self-reproduction[END_REF], XCAs are still one-dimensional CAs; this ensures basic CA techniques (e.g., synchronization) function the same as they do in standard CAs.

Finally, shrinking and expanding are not mutually exclusive. Combining them yields the shrinking and expanding CA (SXCA). The polynomial-time class of SXCA language deciders was shown in [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF][START_REF] Modanese | Shrinking and Expanding Cellular Automata[END_REF] to coincide with PSPACE.

In [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF], the polynomial-time class XCAP of XCA language deciders is shown to contain both NP and coNP while being contained in PSPACE. A precise characterization of XCAP, however, remained outstanding. Such was the topic of the author's master's thesis [START_REF] Modanese | Complexity-Theoretical Aspects of Expanding Cellular Automata[END_REF], the results of which are summarized in this paper. The main result is XCAP being equal to the class of decision problems which are polynomial-time truth-table reducible to NP, denoted ≤ p tt (NP). The rest of this paper is organized as follows: Section 2 covers the fundamental definitions and results needed for the subsequent discussions. Following that, Section 3 recalls the main result of [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF] concerning XCAP and presents the aforementioned characterization of XCAP. Section 4 covers some immediate corollaries, in particular by considering an XCA variant with multiple accept and reject states as well as two other variants with diverse acceptance conditions. Finally, Section 5 concludes.

Basic Definitions

This section recalls basic concepts and results needed for the proofs and discussions in the later sections and is broken down in two parts. The first is concerned with basic topics regarding formal languages, Turing machines, and Boolean formulas. The second part covers the definition of expanding CAs.

Formal Languages and Turing Machines

It is assumed the reader is familiar with the concepts of ωω-words and their homomorphisms as well as deterministic and non-deterministic Turing machines (TMs and NTMs, respectively) and the fundamental classes P, NP, coNP, and PSPACE. In this paper, it is assumed all words have length at least one. The notion of a complete language is employed strictly in the sense of polynomial-time many-one (i.e., Karp) reductions by Turing machines.

Boolean Formulas Let V be a language of variables over an alphabet Σ which, without loss of generality, is disjoint from {T, F, ¬, ∧, ∨, (, )}. BOOL V denotes the language of Boolean formulas over the variables of V . An interpretation of V is a map I : V → {T, F }. Each interpretation I gives rise to an evaluation E I : BOOL V → {T, F } which, given a formula f ∈ BOOL V , substitutes each variable x ∈ V with the truth value I(x) and reduces the resulting formula using standard propositional logic. A formula f is satisfiable if there is an interpretation I such that E I (f ) = T ; f is a tautology if this holds for all interpretations.

In order to define the languages SAT of satisfiable formulas and TAUT of tautologies, a language V of variables must be agreed on. In this paper, variables are encoded as binary strings prefixed by a special symbol x, that is, V = {x} • {0, 1} + . The language SAT contains exactly the satisfiable formulas of BOOL V . Similarly, TAUT contains exactly the tautologies of BOOL V . The following is a well-known result concerning SAT and TAUT [3]: Theorem 1. SAT is NP-complete, and TAUT is coNP-complete.

Truth-Table Reductions

The theory of truth-table reductions was established in [START_REF] Ladner | A Comparison of Polynomial Time Reducibilities[END_REF][START_REF] Ladner | Relativization of Questions About Log Space Computability[END_REF]; later it was shown the class of decision problems polynomial-time truthtable (i.e., Boolean circuit) reducible to NP, denoted ≤ p tt (NP), is equivalent to that of those polynomial-time Boolean formula reducible to NP [START_REF] Wagner | Bounded Query Classes[END_REF]. We refer to [START_REF] Samuel | On Truth-Table Reducibility to SAT[END_REF] for a series of alternative characterizations of ≤ p tt (NP). As a cursory remark, we state the inclusions NP ∪ coNP ⊆ ≤ p tt (NP) and ≤ p tt (NP) ⊆ PSPACE hold. For the results of this paper, a formal treatment of the class ≤ p tt (NP) is not necessary; it suffices to note ≤ p tt (NP) has complete languages. In particular, we are interested in Boolean formulas with NP and coNP predicates. To this end, we employ SAT and TAUT to define membership predicates of the form f L , where f is a Boolean formula, L ∈ {SAT, TAUT}, and " L " is a purely syntactic construct which stands for the statement "f ∈ L".

Definition 1 (SAT ∧ -TAUT ∨ ). Let V = {x}•{0, 1} + and V L = BOOL V •{ L } for L ∈ {SAT, TAUT}.
The language BOOL ∧∨ SAT,TAUT ⊆ BOOL VSAT∪VTAUT is defined recursively as follows:

1. V SAT , V TAUT ⊆ BOOL ∧∨ SAT,TAUT 2. If v ∈ V SAT and f ∈ BOOL ∧∨ SAT,TAUT , then ∧(v, f ) ∈ BOOL ∧∨ SAT,TAUT 3. If v ∈ V TAUT and f ∈ BOOL ∧∨ SAT,TAUT , then ∨(v, f ) ∈ BOOL ∧∨ SAT,TAUT
The language SAT ∧ -TAUT ∨ ⊆ BOOL ∧∨ SAT,TAUT contains all formulas which are true under the interpretation mapping f L to the truth value of the statement "f ∈ L".

The following follows from the results of Buss and Hay [START_REF] Samuel | On Truth-Table Reducibility to SAT[END_REF]:

Theorem 2. SAT ∧ -TAUT ∨ is ≤ p tt (NP)-complete.

Cellular Automata

In this paper, we are strictly interested in one-dimensional cellular automata (CAs) with the standard neighborhood and employed as language deciders. CA deciders possess a quiescent state q; cells which are not in this state are said to be active and may not become quiescent. The input for a CA decider is provided in its initial configuration surrounded by quiescent cells. As deciders, CAs are Turing complete, and, more importantly, CAs can simulate TMs in real-time [START_REF] Smith | Simple Computation-Universal Cellular Spaces[END_REF]. Conversely, it is known a TM can simulate a CA with time complexity t in time at most t 2 . A corollary is that the CA polynomial-time class equals P.

Expanding Cellular Automata First considered in [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF], the expanding CA (XCA) is similar to the shrinking CA (SCA) in that it is dynamically reconfigurable; instead of cells being deleted, however, in an XCA new cells emerge between existing ones. This does not alter the underlying topology, which remains one-dimensional and biinfinite.

For modeling purposes, the new cells are seen as hidden between the original (i.e., visible) ones, with one hidden cell placed between any two neighboring visible cells. These latter cells serve as the hidden cell's left and right neighbors and are referred to as its parents. In each CA step, a hidden cell observes the states of its parents and either assumes a non-hidden state, thus becoming visible, or remains hidden. In the former case, the cell assumes the position between its parents and becomes an ordinary cell (i.e., visible), and the parents are reconnected so as to adopt the new cell as a neighbor. Visible cells may not become hidden.

Definition 2 (XCA). Let N = {-1, 0, 1} be the standard neighborhood. An expanding CA ( XCA) is a CA A with state set Q and local transition function

δ : Q N → Q and which possesses a distinguished hidden state ∈ Q. For any local configuration : N → Q, δ( ) = is allowed only if (0) = .
Let c : Z → Q be a global configuration and z ∈ Z, and let

h c : Z → Q N be such that h c (z)(-1) = c(z), h c (z)(0) = , and h c (z)(1) = c(z + 1). Define α : Q Z → Q Z as
follows, where ∆ is the standard CA global transition function:

α(c)(z) = ∆(c)( z 2 ), z even δ(h c ( z-1 2 )), otherwise
Finally, let Φ be the ωω-word homomorphism induced by the mapping Q → Q * which maps any state to itself except for , which is mapped to ε (i.e., the empty word). Then the global transition function of an XCA is

∆ X = ∆ X δ := Φ • α.
Figure 1 illustrates an XCA A and its operation for input 001010 as an example. The local transition function δ of A is as follows: δ(q -1 , q 0 , q 1 ) = q -1 ⊕ q 1 , q -1 , q 1 ∈ {0, 1} q 0 , otherwise (where ⊕ denotes the bitwise XOR operation, that is, addition modulo 2). In the initial configuration c, the hidden cells are all in the state . Using h c as the hidden cells' local configurations, α applies δ to each local configuration and promotes all hidden cells to ordinary (i.e., visible) ones. Finally, Φ eliminates hidden cells which conserved the state (as these are present only implicitly in the global configuration).

q 0 0 1 0 1 0 q -1 0 1 2 3 4 5 6 q 0 0 1 0 1 0 q -2 0 2 4 6 8 10 12 -1 1 3 5 7 9 11 q 0 1 0 1 0 0 q 0 1 1 1 1 -2 0 2 4 6 8 10 12 -1 1 3 5 7 9 11 1 1 1 0 1 0 q 0 1 1 0 0 q -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12
1 1 1 0 1 0 q 0 1 1 0 0 q -1 0 1 2 3 4 5 6 7 8 9 10 11 α(c) c ∆ X (c) Figure 1.
Illustration of a step of the XCA A. The number next to each cell indicates its index in the respective configuration. In this particular example, we use the convention that the ωω-word homomorphism Φ contracts deleted symbols towards index zero.

Adapted from [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF].

The supply of hidden cells is never depleted; if a hidden cell becomes an ordinary cell, new ones appear between it and its neighbors. Thus, the number of active cells in an XCA may increase exponentially [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF]: Lemma 1. Let A be an XCA. For an input of size n, A has at most (n + 3)2 t -3 active cells after t ∈ N 0 steps. This upper bound is sharp.

We have postponed defining the acceptance behavior of an XCA until now. Usually, a CA possesses a distinguished cell, often cell 0, which dictates the automaton's accept or reject response [START_REF] Kutrib | Cellular Automata and Language Theory[END_REF]. In the case of XCAs, however, under a reasonable complexity-theoretical assumption (i.e., P = ≤ p tt (NP)) such an acceptance behavior results in XCAs not making full use of the efficient cell growth indicated in Lemma 1 (see Section 4.3). This phenomenon does not occur if the acceptance behavior is defined based on unanimity, that is, in order for an XCA to accept (or reject), all its cells must assume the accept (or reject) state simultaneously. This acceptance condition is by no means novel [START_REF] Ibarra | Fast Parallel Language Recognition by Cellular Automata[END_REF][START_REF] Sommerhalder | Parallel Language Recognition in Constant Time by Cellular Automata[END_REF][START_REF] Rosenfeld | Picture languages[END_REF][START_REF] Kim | A Characterization of Constant-Time Cellular Automata Computation[END_REF]. As an aside, note all (reasonable) CA time complexity classes (including, in particular, linear-and polynomial-time) remain invariant when using this acceptance condition instead of the standard one.

Definition 3 (Acceptance behavior, time complexity). Each XCA has a (unique) accept state a and a (unique) reject state r. An XCA A halts if all active (and non-hidden) cells are either all in state a, in which case the XCA accepts, or they are all in state r, in which case it rejects; if neither is the case, the computation continues. L(A) denotes the set of words accepted by A.

The time complexity of an XCA is the number of elapsed steps until it halts. An XCA decider is an XCA which halts on every input. A language L is in XCAP if there is an XCA decider A with polynomial time complexity (in the length of its input) and such that L = L(A ).

In summary, the decision result of an XCA decider is the one indicated by the first configuration in which its active cells are either all in the accept or all in the reject state. This agrees with our aforementioned notion of a unanimous decision.

Characterizing the XCA Polynomial-Time Class

In [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF], the following first result regarding the class XCAP is proven:

Theorem 3. NP ∪ coNP ⊆ XCAP.
We give a brief outline of the proof and refer the interested reader to [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF] for the details. Since many-one reductions by TMs can be simulated by (X)CAs in real-time, it suffices to show XCAP contains NP-and coNP-complete problems. We construct XCAs for SAT and TAUT which run in polynomial time and apply Theorem 1. The two constructions are very similar; in fact, one obtains one from the other simply by swapping the accept and reject states. The following describes the XCA A for TAUT.

XCAs allow for efficient creation of new cells between existing ones. This may be used in order to efficiently create copies of the original formula and in each copy set a given variable to a possible truth value (i.e., "true" or "false"). A iterates over the input formula's variables and, at each iteration step, creates two copies of each formula: one in which the respective variable is set to "true" and one in which it is set to "false". The copies are synchronized with each other, and the process continues in parallel as separate computation branches. The synchronization ensures that, since all copies have equal length, all variables will be exhausted by each branch at the same time.

When this is the case, parallel evaluations of the resulting formulas are carried out, and their results combining using a subtlety of the accepting behavior of XCAs: Reject states are conserved while accept states yield to reject in the next step. If the result of an evaluation is "true", then all respective cells are synchronized and enter the accept state; otherwise, that is, if the result is "false", then all respective cells enter the reject state (after synchronization). As a result, if no reject states are present, then A immediately accepts; otherwise, in the next step, any existing accepting cells become rejecting cells, and A rejects.

Note the steps described above are all carried out in polynomial time since the whole process amounts to replacing variables with truth values and then evaluating the resulting formulas.

A First Characterization

This section covers the following (main) result of [START_REF] Modanese | Complexity-Theoretical Aspects of Expanding Cellular Automata[END_REF]: Proof. We construct an XCA A which decides SAT ∧ -TAUT ∨ (see Definition 1 and Theorem 2) in polynomial time. The actual inclusion follows from the fact that CAs can simulate polynomial-time many-one reductions by TMs in real-time.

Given a problem instance f , A evaluates f recursively. Without loss of generality, f = ∧(f 1 SAT , ∨(f 2 TAUT , f )), where f is some other problem instance; other instances of SAT ∧ -TAUT ∨ are obtained by replacing f 1 , f 2 , or f with a trivial formula (e.g., a trivial tautology).

To evaluate f 1 SAT , A emulates the behavior of the XCA for SAT (see Theorem 3); however, special care must be taken to ensure A does not halt prematurely. All computation branches retain a copy of f . Whenever a branch obtains a "true" result, the respective cells do not directly accept (as in the original construction); instead, they proceed with evaluating the formula's next connective. Conversely, if the result is false, the respective cells simply enter the reject state. The behavior for f 2 TAUT is analogous, with A emulating the XCA for TAUT instead (and with exchanged accept and reject states, accordingly). Additionally, the accept and reject states are such that cells transition between them back and forth1 , and we (arbitrarily) enforce accept states only exist in even-and reject states in odd-numbered steps 2 .

If f 1 ∈ SAT, all branches of A transition into the reject state, and A rejects. Otherwise, f 1 is satisfiable; thus, at least one branch obtains a "true" result, and A continues to evaluate f until the (aforementioned) base case is reached.

An analogous argument applies for f 2 . Note the synchronicity of the branches guarantee they operate exactly the same and terminate at the same time. The repeated transition between accept and reject states guarantee the only cells relevant for the final decision of A are those in the branches which are still "active" (in the sense they are still evaluating f ).

It is concluded that A accepts f if and only if it evaluates to true and rejects it otherwise. A runs in polynomial time (in |f |) since f has at most |f | predicates and since evaluating a predicate requires polynomial time in |f |.

For the converse, we express an XCA computation as a SAT ∧ -TAUT ∨ instance. The main effort here lies on defining the appropriate "variables": Definition 4 (STATE ∀ ). Let A be an XCA, and let V A be the set of triples (w, t, z), w being an input for A, t ∈ {0, 1} + a (standard) binary representation of τ ∈ N 0 , and z a state of A. STATE ∀ (A) ⊆ V A is the subset of triples such that, if A is given w as input, then after τ steps all active cells are in state z.

Lemma 2. If A has polynomial time complexity, STATE

∀ (A) ∈ coNP.
Proof. Fix an efficiently computable polynomial p : N → N 0 such that A always terminates after at most p(n) steps for an input of size n. Consider an NTM T which non-deterministically picks an active cell in step τ of A for input w, computes its state z in polynomial time, and accepts if and only if z = z. Additionally, suppose that, by doing so, T covers all active cells of A in step τ . Furthermore, to ensure T only simulates A for a polynomial number of steps (in |w|), T determines p(|w|) and rejects in case τ > p(|w|); this is not a restriction because of the choice of p. The claim follows immediately from the existence of such a T : If all computation branches of T accept, then in step τ all cells of A are in state z; otherwise, there is a cell in a state which is not z, and T rejects. The rest of the proof is concerned with the construction of T as well as showing that its branches cover all active cells of A in its final configuration for the input w.

To compute the state of an active cell in step τ , T calculates a series of subconfigurations c 0 , . . . , c τ of A, that is, contiguous excerpts of the global configuration of A. As the number of cells in an XCA may increase exponentially in the number of computation steps, bounding c i is essential to ensure T runs in polynomial time; in particular, T maintains |c i | = 1 + 2(τ -i), thus ensuring the lengths of the c i are linear in τ (which, in turn, is polynomial in |w|). This choice of length for the c i ensures each of the subconfigurations correspond to a cell of A surrounded by τ -i cells on either side. 3 The non-determinism of T is used precisely in picking the cells from c i which are to be included in the next subconfiguration c i+1 .

The initial subconfiguration c 0 is set to be q 2τ wq 2τ , thus containing the input word as well as (as shall be proven) a sufficiently large number of surrounding quiescent cells. To obtain c i+1 from c i , T applies the global transition function of A on c i to obtain a new temporary subconfiguration c i+1 . The next state of the two "boundary" cells (i.e, those belonging to indices 0 and |c i | -1) cannot be determined since the state of their neighbors is unknown; thus, they are excluded from c i+1 . The same applies to any hidden cell which remains so. c i+1 contains, as a result, |c i | -2 active cells from the previous configuration c i in addition to a maximum of |c i | -1 previously hidden cells. To maintain |c i | = 1+2(τ -i), T nondeterministically chooses a contiguous subset s of c i+1 containing 1 + 2(τ -i) cells and sets c i+1 to s; when doing so, T ignores subsets containing solely quiescent cells. That there are enough cells to choose from is, again, ensured by the fact that c i+1 contains at least |c i | -2 active cells from the previous configuration c i .

The process of selecting a next subconfiguration c i+1 from c i is depicted in figure 2 This concludes the construction of T . Note it runs in polynomial time since the invariant |c i | = 1 + 2(τ -i) guarantees the number of states T computes in each step is bounded by a multiple of τ , which, as previously discussed, is bounded by p(|w|). Only |w| has to be taken into account when estimating the time complexity of T since the encoding of z is constant with respect to |w| while that of t is logarithmic with respect to p(|w|); expressing the problem instance (w, t, z) requires, as a result, asymptotically |w| space.

. . . z 2 z 1 z m-1 z m c i+1 n -2 . . . z 2 z 1 z n-3 z n-2 ci+1
To show all active cells of A in step τ are covered by T , it suffices to prove the following by induction: Let i ∈ {0, . . . , τ }, and let z 1 , . . . , z m be the active cells of A in step i; then T covers all subconfigurations of q 2(τ -i) z 1 • • • z m q 2(τ -i) of size 1 + 2(τ -i). Note this corresponds to T covering all subconfigurations of A in step i which contain at least one active cell; thus, when T reaches step τ , it covers all subconfigurations of z 1 • • • z m of size 1, that is, all active cells.

The induction basis follows from c 0 = q 2τ wq 2τ . For the induction step, fix a step 0 < i ≤ τ and assume the claim holds for all steps prior to i. To each subconfiguration of q 2(τ -i) z 1 • • • z m q 2(τ -i) having size 1 + 2(τ -i) corresponds a cell w which is located in its center; such subconfiguration is denoted by s i (w). Now let s i (w) be given, in which case there are three cases to be considered: w was active in step i -1; w was a hidden cell which became active in the transition to step i; or w was a quiescent cell in step i -1 and, by |s i (w)| = 1 + 2(τ -i), is at most τ -i cells away from z 1 or z m .

In the first case, by the induction hypothesis, there is a value of c i-1 corresponding to s i-1 (w); since only the two boundary cells are present in c i-1 but not in c i , choosing c i from c i with w as its middle cell yields s i (w). In the second, for any of the two parents p 1 and p 2 of w, there are, by the induction hypothesis, values of c i-1 which equal s i-1 (p 1 ) and s i-1 (p 2 ); in either case, choosing c i from c i with w as its middle cell again yields s i (w).

Finally, if w was a quiescent cell, then, without loss of generality, consider the case in which w was located to the left of the active cells in step i -1. By the induction hypothesis, for each cell w up to τ -i + 1 cells away from the leftmost active cell z 1 there is a value of c i-1 corresponding to s i-1 (w ), and the first case applies; the only exception is if c i would then contain only quiescent cells, in which case w would be located strictly more than τ -i cells away from z 1 , thus contradicting our previous assumption. The claim follows.

The following proposition completes our argument by reduction:

Proposition 2. XCAP ⊆ ≤ p tt (NP).
Proof. Let L ∈ XCAP, and let A be an XCA for L whose time complexity is bounded by a polynomial p : N → N 0 . Additionally, let w be an input for A, V A be as in Definition 4, and let V = V A • { STATE ∀ (A) }, where STATE ∀ (A) is a syntactic symbol standing for membership in STATE ∀ (A) (cf. Definition 1). Define f 0 (w), . . . , f p(n) (w) ∈ BOOL V recursively as follows:

f i (w) := ∨( (w, i, a) STATE ∀ (A) , ∧( ¬( (w, i, r) STATE ∀ (A) ), f i+1 ) ), i = p(n) ∨( (w, p(n), a) STATE ∀ (A) , ¬( (w, p(n), r) STATE ∀ (A) ) ), i = p(n)
Lemma 2 together with the coNP-completeness of TAUT (see Theorem 1) ensures each subformula of the form (w, i, a) STATE ∀ (A) is polynomial-time many-one reducible to an equivalent4 SAT ∧ -TAUT ∨ formula g TAUT , g being a TAUT instance. Similarly, each subformula ¬((w, i, a) STATE ∀ (A) ) is reducible to an equivalent formula h SAT . Since each of the f i (w) may contain only polynomially (respective to |w|) many connectives, each is polynomial-time (many-one) reducible to an equivalent SAT ∧ -TAUT ∨ instance f i (w).

By the definition of XCA (i.e., Definitions 2 and 3) and our choice of p, f (w) := f 0 (w) is true if and only if A accepts w. Since f (w) is such that |f (w)| is polynomial in |w|, this provides a polynomial-time (many-one) reduction of L to a problem instance of SAT ∧ -TAUT ∨ ∈ ≤ p tt (NP). The claim follows.

For the converse inclusion, consider the following NP analogue of the STATE ∀ language (cf. Definition 4 and Lemma 2): Definition 8 (STATE ∃ ). Let A be an XCA, and let V be the set of triples (w, t, z) as in definition 4. STATE ∃ ⊆ V is the subset of triples such that, for the input w, after t steps at least one of the active cells of A is in state z. Proof. Consider the NTM T from Lemma 2 and notice that, if any of the active cells of A in step τ have state z, then T will have at least one accepting branch; otherwise, none of the active cells of A in step τ have state z; thus, all branches of T are rejecting.

Using Lemma 4 to proceed as in Proposition 2 yields the following, from which Theorem 6 follows: Proposition 4. EXCAP ⊆ ≤ p tt (NP).

One-Cell-Decision XCA

We turn to the discussion of XCAs whose acceptance condition is defined in terms of a distinguished cell which directs the automaton's decision, considered the standard acceptance condition for CAs [START_REF] Kutrib | Cellular Automata and Language Theory[END_REF]. This behavior is similar to the existential variant in the sense that a single cell suffices to trigger the automaton's termination; the difference lies in the position of this single cell being immutable. We consider only the case in which the decision cell is the leftmost active cell in the initial configuration (i.e., cell 0). By a one-cell-decision XCA (1XCA) we refer to an XCA which accepts if and only if 0 is in the accept state and rejects if and only if cell zero is in the reject state. Let 1XCAP denote the polynomial-time class of 1XCAs.

The position of the decision cell is fixed; with a polynomial-time restriction in place, it can only communicate with cells which are a polynomial (in the length of the input) number of steps apart. As a result, despite a 1XCA being able to efficiently increase its number of active cells exponentially (see Lemma 1), any cells impacting its decision behavior must be at most a polynomial number of cells away from the decision cell. Thus: Theorem 7. 1XCAP = P.

Proof. The inclusion 1XCAP ⊇ P is trivial. For the converse, recall the construction of the NTM T in Lemma 2. T can be modified such that it works deterministically and always chooses the next configuration c i+1 from c i by selecting cell zero as the middle cell. If cell zero is accepting, then T accepts immediately; if it is rejecting, then T also rejects immediately. This yields a simulation of a 1XCA by a (deterministic) TM which is only polynomially slower, thus implying 1XCAP ⊆ P.

This paper summarized the results of [START_REF] Modanese | Complexity-Theoretical Aspects of Expanding Cellular Automata[END_REF], which, in turn, expanded on the complexity-theoretic aspects of XCAs from [START_REF] Modanese | Shrinking and Expanding One-Dimensional Cellular Automata[END_REF]. The main result was the characterization XCAP = ≤ p tt (NP) in Section 3.1. In Section 4, XCAs with multiple accept and reject states were shown to be equivalent to the original model. Also in Section 4, two other variants based on varying varying acceptance conditions were considered: the existential (EXCA), in which a single, though arbitrary cell may direct the automaton's response; and the one-cell-decision XCA (1XCA), in which a fixed cell does so. In the first case, it was shown that the polynomial-time class EXCAP equals XCAP; in the latter, it was shown that the polynomial-time class 1XCAP of 1XCAs equals P.

This paper has covered some XCA variants with diverse acceptance conditions. A topic for future work might be considering further variations in this sense (e.g., XCAs whose acceptance condition is based on majority instead of unanimity). Another avenue of research lies in restricting the capabilities of XCAs and analyzing the effects thereof (e.g., restricting 1XCAs or SXCAs to a polynomial number of cells). A final open question is determining what polynomial speedups, if any, 1XCAs provide with respect to 1CAs.

Theorem 4 .

 4 XCAP = ≤ p tt (NP). The equality in Theorem 4 is proven by considering the two inclusions. Proposition 1. ≤ p tt (NP) ⊆ XCAP.

  . In the figure, |c i | has been replaced with n for legibility. T at first applies the global transition function of A to obtain an intermediate subconfiguration c i+1 with m = |c i+1 | cells. Because of hidden cells, c i+1 may consist of n -2 ≤ m ≤ 2n -3 cells. Non-determinism is used to select a contiguous subconfiguration of n -2 cells, thus giving rise to c i+1 .

Figure 2 .

 2 Figure 2. Illustration of how T obtains the next subconfiguration ci+1 from ci.

Lemma 4 .

 4 If A has polynomial time complexity, STATE ∃ (A) ∈ NP.

That is, δ( ) = a for (0) = r and vice-versa, where δ and are as in Definition

[START_REF] Samuel | On Truth-Table Reducibility to SAT[END_REF] This may be accomplished, for example, by using a bit counter in the cells' states, and having cells wait for a step before transitioning to an accept or reject state if needed.

That is to say, each ci corresponds to the so-called extended (τ -i)-neighborhood of a cell of A.

In the sense of evaluating to the same truth value under the respective interpretations (see Definition 1).

An allusion to the existential states of alternating Turing machines (ATMs)

Acknowledgments

The author would like to thank Thomas Worsch for his mentoring, encouragement, and support during the writing of this paper. The author would also like to thank Dennis Hofheinz for pointing out a crucial mistake in a preliminary version of this paper as well as the anonymous referees for their valuable remarks and suggestions.

This section covers some immediate corollaries of Theorem 4 regarding XCA variants. In particular, we address XCAs with multiple accept and reject states, followed by XCAs with acceptance conditions differing from that from Definition 3, in particular the two other classical acceptance conditions for CAs [START_REF] Rosenfeld | Picture languages[END_REF].

XCAs with Multiple Accept and Reject States

Recall the definition of an XCA specifies a single accept and a single reject state (see Section 2.2). Consider XCAs with multiple accept and reject states. As shall be proven, the respective polynomial-time class (MAR-XCAP) remains equal to XCAP. In the case of TMs, the equivalent result (i.e., TMs with a single accept and a single reject state are as efficient as standard TMs) is trivial, but such is not the case for XCAs. Recall the acceptance condition of an XCA requires orchestrating the states of multiple, possibly exponentially many cells. In addition, an XCA with multiple accept states may, for instance, attempt to accept whilst saving its current state (i.e., a cell in state z may assume an accept state a z while simultaneously saving state z). Such is not the case for standard XCAs (i.e., as specified in Definition 3), in which all accepting cells have necessarily the same state.

Definition 5 (MAR-XCA, MAR-XCAP). A multiple accept-reject XCA ( MAR-XCA) D is an XCA with state set Q and which admits subsets A, R ⊆ Q of accept and reject states, respectively. D accepts (rejects) if its active cells all have states in A (R), and it halts upon accepting or rejecting. In addition, D is required to either accept or reject its input after a finite number of steps. MAR-XCAP denotes the MAR-XCA analogue of XCAP.

The following generalizes STATE ∀ (see Definition 4 and Lemma 2) to the case of MAR-XCAs:

Let A be a MAR-XCA with state set Q, and let V A be the set of triples (w, t, Z), w being an input for A, t ∈ {0, 1} + a binary encoding of τ ∈ N 0 , and Z ⊆ Q. STATE MAR ∀ (A) ⊆ V A is the subset of triples such that, if A is given w as input, after t steps all active cells have states in Z. , the accept state a with the set A, and the reject state r with the set R. Lemma 3 guarantees the reductions to SAT ∧ -TAUT ∨ are all efficient. This implies MAR-XCAP ⊆ ≤ p tt (NP) = XCAP. Since MAR-XCAs are a generalization of XCAs, the converse inclusion is trivial.

Existential XCA

The remainder of this section is concerned with XCAs variants which use the two other acceptance conditions from [START_REF] Rosenfeld | Picture languages[END_REF][START_REF] Ibarra | Fast Parallel Language Recognition by Cellular Automata[END_REF][START_REF] Sommerhalder | Parallel Language Recognition in Constant Time by Cellular Automata[END_REF][START_REF] Kim | A Characterization of Constant-Time Cellular Automata Computation[END_REF]. The first is that of a single final state being present in the CA's configuration sufficing for termination. Definition 7 (EXCA, EXCAP). An existential 5 XCA (EXCA) is an XCA with the following acceptance condition: If at least one of its cells is in the accept (reject) state a (r), then the EXCA accepts (rejects). The coexistence of accept and reject states in the same global configuration is disallowed (and any machine contradicting this requirement is, by definition, not an EXCA). EXCAP denotes the EXCA analogue of XCAP.

Disallowing the coexistence of accept and reject states in the global configuration of an EXCA is necessary to ensure a consistent accepting behavior. An alternative would be to establish a priority relation between the two (e.g., an accept state overrules a reject one); nevertheless, this behavior can be emulated by our chosen variant with only constant delay. This is accomplished by introducing binary counters to delay state transitions and assure, for instance, that accept and reject states exist only in even-and odd-numbered steps, respectively.

Despite the diverse accepting behavior, the following holds for EXCAs: Theorem 6. EXCAP = XCAP = ≤ p tt (NP). Note this is an equivalence between two disparately complex acceptance behaviors: As by Definition 3, in an XCA all cells must agree on the final decision; on the other hand, in an EXCA, a single, arbitrary cell suffices. We ascribe this phenomenon to XCAP = ≤ p tt (NP) being equal to its complementary class. As for the proof of Theorem 6, first note that Proposition 1 may easily be restated in the context of EXCAs: Proposition 3. ≤ p tt (NP) ⊆ EXCAP. Proof. Consider the XCA A for SAT ∧ -TAUT ∨ from the proof of Proposition 1; by adapting it, we obtain an EXCA B which decides TAUT ∧ -SAT ∨ in polynomial time. TAUT ∧ -SAT ∨ is the problem analogous to SAT ∧ -TAUT ∨ and which is obtained by exchanging "TAUT" and "SAT" in Definition 1. As SAT ∧ -TAUT ∨ , TAUT ∧ -SAT ∨ is ≤ p tt (NP)-complete (see Theorem 2). To evaluate a predicate of the form f TAUT , B proceeds as A and emulates the behavior of the XCA deciding TAUT (see Theorem 3); however, unlike A, the computation branches of B which evaluate to false reject immediately while it is those that evaluate to true that continue evaluating the input formula. As a result, if f ∈ TAUT, all branches of B evaluate to true and continue evaluating the input in a synchronous manner; otherwise, there is a branch evaluating to false, and, since a single rejecting cell suffices for it to reject, B rejects immediately. The evaluation of f SAT is carried out analogously.

The modifications to A to obtain B do not impact its time complexity whatsoever; thus, B also has polynomial time complexity.