# Cellular Automata/Boundary Conditions

On bounded lattices the information about preimages outside the boundaries of the observed string ${\displaystyle \alpha }$ can be described by two boundary preimage vectors (left ${\displaystyle b_{L}}$ and right ${\displaystyle b_{R}}$). The observed string ${\displaystyle \alpha }$ can be seen as part of an infinite string ${\displaystyle \beta _{L}\alpha \beta _{R}}$. Boundary vector ${\displaystyle b_{L}}$ describes preimages of the semi-infinite string ${\displaystyle \beta _{L}}$ and boundary vector ${\displaystyle b_{R}}$ describes preimages of the semi-infinite string ${\displaystyle \beta _{R}}$. Vector elements are the numbers of preimages that can be traced from the boundary to infinity for each of the overlaps at the boundaries. Element at position ${\displaystyle o_{L}}$ in the left boundary vector ${\displaystyle b_{L}}$ specifies the number of preimages ${\displaystyle p_{-\infty \leftrightarrow o_{L}}(\beta _{L})}$ that can be traced from left infinity to the overlap ${\displaystyle o_{L}}$ at the left boundary of the observed string. The definition of the right boundary vector ${\displaystyle b_{R}}$ is similar.

${\displaystyle b_{L}=[p_{-\infty \leftrightarrow o_{L}=0},p_{-\infty \leftrightarrow o_{L}=1},\dots ,p_{-\infty \leftrightarrow o_{L}},\dots ,p_{-\infty \leftrightarrow o_{L}=k^{m-1}-1}]^{T}}$
${\displaystyle b_{R}=[p_{0=o_{R}\leftrightarrow +\infty },p_{1=o_{R}\leftrightarrow +\infty },\dots ,p_{o_{R}\leftrightarrow +\infty },\dots ,p_{k^{m-1}-1=o_{R}\leftrightarrow +\infty }]^{T}}$

Since we usually don't care about the state of the CA outside the observed string, unrestricted boundary vectors can be used. \paragraph{Definition} For the \emph{unrestricted boundary vector} it is assumed that each of the boundary overlaps can be used to trace exactly one path to infinity. Therefore the unrestricted boundary vector contains all ones.

${\displaystyle b_{u}=[1,1,\dots ,1]^{T}}$

Note The below definitions rely on assumptions that are not proved yet, so the definitions my be wrong.

General boundary vectors ${\displaystyle b_{L}}$ and ${\displaystyle b_{R}}$ describe general infinite strings ${\displaystyle \beta _{L}}$ and ${\displaystyle \beta _{R}}$. It is assumed that this strings end with an unrestricted boundary vector ${\displaystyle b_{u}}$ in the infinity.

${\displaystyle b_{L}^{T}=\lim _{|\beta _{L}|\rightarrow \infty }b_{u}^{T}\,D(\beta _{L})\qquad b_{R}=\lim _{|\beta _{R}|\rightarrow \infty }D(\beta _{R})\,b_{u}}$

Since an infinite string can have an infinite number of preimages, this definition is rarely useful. Boolean values can be used instead of integers to state if the overlap can be used for tracing or not. The equations are identical, only the scalar multiplication operator used for matrix multiplication is replaced by an XOR logical operation. Another option is using probabilities.

Another common boundary is an infinite periodic string with a finite period. Some commonly used boundaries can be defined this way. The periodic boundary vectors ${\displaystyle b_{\bar {L}}}$ and ${\displaystyle b_{\bar {R}}}$ describe infinite periodic strings with finite periods ${\displaystyle {\overline {\beta _{L}}}}$ and ${\displaystyle {\overline {\beta _{R}}}}$. This strings end with the same boundary vector ${\displaystyle b_{\bar {L}}}$ and ${\displaystyle b_{\bar {R}}}$ in the infinity. The preimage matrix of a sting of ${\displaystyle n}$ period strings ${\displaystyle {\overline {\beta }}^{n}}$ is computed as ${\displaystyle D({\overline {\beta }}^{n})=D^{n}({\overline {\beta }})}$.

${\displaystyle b_{\bar {L}}^{T}=\lim _{n\rightarrow \infty }b_{\bar {L}}^{T}\,D^{n}({\overline {\beta _{L}}})\qquad b_{\bar {R}}=\lim _{n\rightarrow \infty }D^{n}({\overline {\beta _{R}}})\,b_{\bar {R}}}$

The problem with this definition is thet there may by many different vectors that fulfil the criteria. There is an example of periodic boundaries with a finite number of preimages at the end of the paper.