\( \newcommand{\TR}{\operatorname{TR}} \renewcommand{\epsilon}{\varepsilon} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ACA}{\mathcal{A}} \newcommand{\ACQ}{\mathcal{Q}} \)

A Linear Acceleration for all Neighborhoods on 2D Cellular Automata

Séminaire ALGO
Anaël Grandjean and Victor Poupet

Definitions

Cellular Automata

2-dimensional cellular automata (2DCA) \(\ACA = (\ACQ, V, \delta)\) :


global function \(\Delta: \ACQ^{\ZZ^2}\rightarrow \ACQ^{\ZZ^2}\)

Language Recognition

Languages of rectangular pictures in\[\Sigma^{**} = \bigcup_{n, m} \Sigma^{(n, m)}\]

We consider 2DCA such that


Time complexity is as expected\[f: \NN^2 \rightarrow \NN\]

Neighborhoods

Def. (Iterations)
\begin{align*} V^0 &= \{0\}\\ V^{n+1} &= V + V^n\\ &= \{x, y \ |\ x \in V, y\in V^n\} \end{align*}

\(V^n\) is the set of cells that the origin can see in \(n\) time steps.

Def. (Scalar Product)
\begin{align*} kV = \{k.x \ |\ x \in V\} \end{align*}
Def.
A neighborhood \(V\) is complete if \[\bigcup_{n\in\NN}V^n = \ZZ^2\]

Convex Hull

Def.

The convex hull of a neighborhood \(V\) is the smallest convex polygon (in \(\RR^2\)) containing \(V\).


The vertices of the convex hull are elements of \(V\)

Prop.

If a neighborhood is complete, its convex hull contains an open ball around the origin.


Prop.
\(\forall x\in\QQ^2\), if \(x\) is on the border of the convex hull of \(V\) then \[x = \lambda u + (1-\lambda)v\] with \(u, v\in V\) and \(\lambda\in [0, 1]\cap \QQ\)

Real Time

Definition

The real time function corresponding to a given neighborhood \(V\) is defined as\begin{align*} \TR_V: \NN^2 &\rightarrow \NN\\ (n, m) &\mapsto \min\{t \ |\ n\times m\subseteq V^t\} \end{align*}


Linear Acceleration
on the
Moore Neighborhood

On the Moore Neighborhood

Theorem

For any \(\epsilon > 0\), any language recognized in time \((\TR + f)\) by a 2DCA working on the Mooreneighborhood can be recognized in time \[\TR + \lceil\epsilon f\rceil\]


Proof :

Compression

A cell of the new automaton can contain up to \(k^2\) states of the original CA.

Simulation

Proof by induction

Self Synchronization


Problem : cells do not complete compression at the same time

Solution : compute new states as soon as relevant information is available.

Claim

All cells are at least as fast as if they all started at the same time as the last.

Linear Acceleration

Main Theorem

Theorem
For any complete neighborhood \(V\) and any \(\epsilon > 0\), any language recognized in time \((\TR + f)\) by a 2DCA working on \(V\) can be recognized in time \[(1+\epsilon)\TR + \epsilon f\]

Proof :

Simulation

Problem : After compression, a cell sees \(kV + c\) for the information it holds, not \(V^k + c\)

Solution : Gather more information !


  • \(m = (k-1)|V| - k + 1\)
  • \(V^{m+k} \subseteq V^m + kV\)
  • Cells gather the initial states in \(V^m + c\) for each \(c\) that was compressed to it
  • Bounded time loss

At each step, cells can compute \(k\) steps of the original automaton for each of the information they hold.

Compression

Difficulty : Optimal path towards the origin depends on the ratio \(\frac m n\)


Idea :

Moore-Like Neighborhoods

Defintion: see picture.

Claim

A Moore-like neighborhood can perform a compression of the input by a factor \((k+1)\) in time\[\frac{k}{k+1}\TR\]


Proof : Same as for the Moore neighborhood

Fixed Ratio

For input words with a specific ratio \(\rho\), the complete neighborhood \(V\) can behave as a Moore-likeneighborhood \(V'\)

Approximate Ratio


For any input picture, there is \(V'\in M_\epsilon\) that can compress it by \(k+1\) in time\[(1+\epsilon')\frac{k}{k+1}\TR_{V}\]

Summary


Total time : \((1+\epsilon)\TR + \epsilon f\)