When is a cellular automaton "bidirectional"?

Question

From this paper.

"A (bi-directional, deterministic) cellular automaton is a triplet $A = (S;N;\delta)$, where $S$ is an non-empty state set, $N$ is the neighborhood system, and $\delta$ is the local transition function (rule). This function defines the rule of calculating the cell’s state at $t +1$ time step, given the states of the neighborhood cells at previous time step $t$"

I haven't found other "bidirectional" CA via Google, so I wonder what does the term say about this automaton's properties. Does it mean that the state $t+1$ can be used to find out the state t?

Answer 1

The term is definitely an oddity. In the specific case $S=\mathbb Z$, it might refer to the fact that the neighborhood is two-sided, typically $N=\{-1,0,1\}$ instead of $N=\{0,1,2\}$. My advice is to forget this altogether.

Answer 2

I think that the notion is commonly called a reversible cellular automaton. We say that a cellular automaton $f:A^{\mathbb{Z}^{d}}\rightarrow A^{\mathbb{Z}^{d}}$ (i.e. a function defined by a local transition rule) is called reversible if there is a cellular automaton $g:A^{\mathbb{Z}^{d}}\rightarrow A^{\mathbb{Z}^{d}}$ where $f\circ g$ and $g\circ f$ are both the identity mapping. We have the following characterization of reversible cellular automata.

$\mathbf{Theorem}$ Let $f:A^{\mathbb{Z}^{d}}\rightarrow A^{\mathbb{Z}^{d}}$ be a cellular automaton. Then following are equivalent.

1. $f$ is reversible.

2. $f$ is bijective.

3. $f$ is injective.

In other words, every injective cellular automaton is bijective and its inverse is also a cellular automaton. See this paper for more details on reversible cellular automata.

I don't think the authors were referring to bi-dimensional cellular automata since the author defines cellular automata for all dimensions, and I don't think the authors were referring to cellular automata mapping $\mathbb{N}^{d}$ to $\mathbb{N}^{d}$ since we are dealing with multiple dimensions. It seems like the authors were putting words in parentheses rather carelessly that time.