Cellular Automata/Decision Problems

The study of decision problems for 1D CA is based on the subset diagram of the de Bruijn diagram. The subset diagram is interpreted as an finite automaton and analysed accordingly. Most decision problems are defined using the larger matrix subset diagram, but they can be redefined using the smaller vector subset diagram.

The subset diagram

Nodes in the subset diagram are all possible preimage matrices or vectors that can be written using boolean elements.

Matrix subset diagram

The matrix subset diagram is a directed graph $\langle S,Q_{D},\delta _{D}\rangle$ later remodeled as a finite automaton.

$Q_{D}$ is the set of all states which are all $|Q_{D}|=2^{k^{2(m-1)}}$ distinct bolean preimage matrices.

$Q_{D}=\left\{{\begin{bmatrix}0&0&\dots 0\\0&0&\dots 0\\\vdots &\vdots &\ddots \vdots \end{bmatrix}},{\begin{bmatrix}1&0&\dots 0\\0&0&\dots 0\\\vdots &\vdots &\ddots \vdots \end{bmatrix}},\dots ,{\begin{bmatrix}1&1&\dots 1\\1&1&\dots 1\\\vdots &\vdots &\ddots \vdots \end{bmatrix}}\right\}$

The set of available cell states $S$ is used for link labes and as the automaton alphabet. The automaton state transition function $\delta$ defines links between states and their labes.

$\delta _{D}:Q_{D}\times S\rightarrow Q_{D}$

Two transition functions can be constructed, one for the forward direction $\delta _{D,f}$ and one for the backward direction $\delta _{D,b}$. The transitions on input symbols $c\in S$ are defined by single cell preimage matrices.

$q_{D_{x+1}}=\delta _{D,f}(q_{D_{x}},c_{x})\qquad D_{x+1}=D_{x}\cdot D(c_{x})\quad {\mbox{boolean multiplication}}$

$q_{D_{x-1}}=\delta _{D,b}(q_{D_{x}},c_{x})\qquad D_{x-1}^{T}=D(c_{x-1})\cdot D_{x}^{T}\quad {\mbox{boolean multiplication}}$

A finite automaton $\langle S,Q_{D},q_{0},\delta _{D},F_{D}\rangle$ is constructed from the graph $\langle S,Q_{D},\delta _{D}\rangle$ by specifying an initial state $q_{0}\in Q_{D}$ and the set of final states $F_{D}\subset Q_{D}$.

The empty set is the state $q=0$ where all preimage matrix elements are 0.

${\begin{bmatrix}0&0&\dots 0\\0&0&\dots 0\\\vdots &\vdots &\ddots \vdots \end{bmatrix}}$

Vector subset diagram

The vector subset diagram is a directed graph $\langle S,Q,\delta \rangle$ later remodeled as an finite automaton. $Q$ is the set of all states which are all $|Q|=2^{k^{m-1}}$ distinct bolean preimage vectors.

$Q_{b}=\{0,1,\dots ,b,\dots ,|Q|-1\}$

$q=\sum _{o=0}^{k^{m-1}-1}b(o)=2^{k^{m-1}-1}b(k^{m-1}-1)+\cdots +2^{o}b(o)+\cdots +2b(1)+b(0)$

The set of available cell states $S$ is used for link labes and as the automaton alphabet. The automaton state transition function $\delta$ defines links between states and their labes.

$\delta :Q\times S\rightarrow Q$

Two transition functions can be constructed, one for the forward direction $\delta _{f}$ and one for the backward direction $\delta _{b}$. The transitions on input symbols $c\in S$ are defined by single cell preimage matrices.

$q_{x+1}=\delta _{f}(q_{x},c_{x})\qquad b_{x+1}=b_{x}\cdot D(c_{x})\quad {\mbox{boolean multiplication}}$

$q_{x-1}=\delta _{b}(q_{x},c_{x})\qquad b_{x-1}^{T}=D(c_{x-1})\cdot b_{x}^{T}\quad {\mbox{boolean multiplication}}$

A finite automaton $\langle S,Q,q_{0},\delta ,Q_{F}\rangle$ is constructed from the graph $\langle S,Q,\delta \rangle$ by specifying an initial state $q_{0}\in Q$ and the set of final states $Q_{F}\subset Q$.

The empty set is the state $q=0$ where none of the overlaps in the preimage vector $b$ can be used to trace paths.

$b=[0,0,\dots ,0]$

The full set is the state $q=2^{k^{m-1}}$ where all of the overlaps in the preimage vector $b$ can be used to trace paths.

$b=[1,1,\dots ,1]$

Decision Problems

To observe a decision problem the subset diagram is transformed into an automaton. A word defined as a string of cells $\alpha$ is accepted if it connects the specified initial state to one of the final states.

De Bruijn subset diagram, are used to answer injectivity and surjectivity problems, regular expression for preimages...

Surjectivity of CA rules

The global transition function is surjective if each present configuration $C^{t}$ has at least one preimage $C^{t-1}$.

$\forall C^{t}\;\exists C^{t-1}\;:\;F(C^{t-1})=C^{t}$

Since preimages are paths in the preimage network, there must always exist at least a single path between the boundaries of any cell string $\alpha$.

Shortest non-accepted string

Another problem related to the subset diagram is the shortest string that is not accepted by the subset diagram. This can easily be rephrased as a decision problem: does the subset diagram have a string of length $l$ or shorter for a given integer $l$. By the definition of this problem, testing true for a given cellular automaton rule and given $l$, the same cellular automaton will test true for l+1. In the case that a cellular automaton is surjective, there will be no such string.

It was alluded to by Wolfram that what Sutner called the 1-permutative cellular automata most likely will test false for the highest $l$ within the set of cellular automata with the same number of characters and the same width. Kingsbery proved in his undergraduate thesis that 1-permutative CA will test true for all $l$ greater than or equal to $wk^{w-1}$, where $w$ is the CA's width and $k$ is the number of symbols. Assuming that this is true for all CA (and the work of Wolfram and Sutner seem to indicate that it should be), this ensures that any certificate for this decision problem can be verified in time polynomial to the size of the CA's rule table. It is not known whether such a certificate can be constructed in polynomial time.

Theorem: 1-permutative CA with a width $w$ over $k$ symbols have a shortest non-accepted string no longer than $wk^{w}-1$.

Proof: TODO

Definitions and Proofs

Boolean matrix and vector operations

All mathematical addition and multiplications are exchanged with their Boolean counterparts disjunction and conjunction.

Addition become disjunction (logical operator OR):

$x_{1}+x_{2}\to x_{1}\lor x_{2}$

Multiplication becomes conjunction (logical operator AND):

$x_{1}\cdot x_{2}\to x_{1}\land x_{2}$

This basic Boolean operations are than used to define matrix and vector operations.

Examples

References

1. Tobias Gärtner, Timo von Oertzen, and Jan Schwinghammer, Efficiently Computing the Density of Regular Languages, Proceedings of Latin American INformatics (LATIN'04), pages 262-270, Buenos Aires.
2. Etienne Grandjean, Complexity of the first-order theory of almost all finite structures, Information and Control, 57(2/3):180-204, May/June 1983

Tools

1. Grail+