Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata

$(1\Rightarrow 2)$ Let $Y$ be a SFT on alphabet ${\mathrm{\Sigma }}^{\prime }$ given by a finite set $ℱ$ of forbidden patterns and $\pi :{\mathrm{\Sigma }}^{\prime }\to \mathrm{\Sigma }$ be such that $\pi (Y)=X$; remember that we assume that patterns in $ℱ$ have support $\{\bullet ,\uparrow \}$ or $\{\bullet ,\mathrm{\to }\}$. We define $A=(V,E,{\mathrm{\Sigma }}^{\prime },D)$ by setting $V={\mathrm{\Sigma }}^{\prime }$ and $D=\pi$, and $E$ is defined as follows: for all $p\in {\mathrm{\Sigma }}^{\prime \{\bullet ,\uparrow \}}$, $(p_{\bullet },p_{\uparrow },\uparrow )\in E$ if and only if $p\notin ℱ$, and similarly for $\mathrm{\to }$. By construction, $y\in {\mathrm{\Sigma }}^{\prime {\mathbb{Z}}^2}$ is a recognising run of $A$ on $x$ if and only if $y\in Y$ and $\pi (y)=x$, so $X=R_{\mathrm{\infty }}(A)$.

$(2\Rightarrow 1)$. Let $A=(V,E,{\mathrm{\Sigma }}^{\prime },D)$ be an automaton and define the SFT $Y\subset V^{{\mathbb{Z}}^2}$ by the set of forbidden patterns:

Again by construction, $y$ is a recognising run of $A$ on $x$ if and only if $y\in Y$ and $D(y)=x$, so $X=D(Y)$ is sofic.

$(2\iff 3)$ The two statements are equivalent for any automaton $A$. If $x\in R_{\mathrm{\infty }}(A)$ has a recognising run, then the restriction of this run to any finite pattern in $x$ is recognising, so all patterns in $x$ belong to $R_f(A)$. Conversely, if all patterns in $x$ admit a recognising run, then $x$ does as well by a standard compactness argument. $◀$

Notice that the third condition involves complementation, in contrast with the one-dimensional case; recognisable languages are not closed by complement in dimension 2 [1].

Let $A=(V,E,\mathrm{\Sigma },D,I,Q)$ be an alternating PWA. Let ${\mathrm{\Sigma }}^{\prime }=\mathrm{\Sigma }\times 𝒫(V)$, where a symbol from ${\mathrm{\Sigma }}^{\prime }$ encodes the set of states starting from which there is an accepting run in the current position. Let ${\pi }_1$ and ${\pi }_2$ be the projections on the first and second component, respectively.

We define a SFT $Y\subset {\mathrm{\Sigma }}^{\prime {\mathbb{Z}}^2}$ by the following set $ℱ$ of forbidden patterns: for $p\in {\mathrm{\Sigma }}^{\prime \{\leftarrow ,\mathrm{\to },\uparrow ,\downarrow ,\bullet \}}$, denote $p_{\bullet }=(s,S)$ where $s\in \mathrm{\Sigma }$ and $S\in 𝒫(V)$. Then $p\in ℱ$ if and only if:

1. 1.

   $\exists v\in S,D(v)\ne s$, or

2. 2.

   $S\cap I=\mathrm{\varnothing }$, or

3. 3.

   there is $v\in S$ such that

   • $\mathrm{■}$

     $Q(v)=\exists$ and for all $(v,v^{\prime },d)\in E$, we have $p_d=(s^{\prime },S^{\prime })$ with $v^{\prime }\notin S^{\prime }$.

   • $\mathrm{■}$

     $Q(v)=\forall$ and there is $(v,v^{\prime },d)\in E$ such that $p_d=(s^{\prime },S^{\prime })$ with $v^{\prime }\notin S^{\prime }$.

We claim that $L_{\mathrm{\infty }}(A)={\pi }_1(Y)$.

Given a configuration $y\in Y$, we prove inductively the following statement: there is an accepting run starting from $(i,v)$ on ${\pi }_1(y)$ for all $i\in {\mathbb{Z}}^2$ and $v\in {\pi }_2(y_i)$. If $Q(v)=\exists$, then Condition 3 ensures we find an edge $(v,v^{\prime },d)$ with $v^{\prime }\in {\pi }_2(y_{i+d})$. Condition 1 and iterating this argument yields an accepting run starting from $(i+d,v^{\prime })$. A similar argument works for $\forall$. Condition $2$ ensures that there is an initial state in ${\pi }_2(y_i)$, so ${\pi }_1(y)$ is accepted by $A$.

Conversely, given a configuration $x\in L_{\mathrm{\infty }}(A)$, we define $y_i=(x_i,S_i)$ where $S_i\subset V$ is the set of states $v$ such that there is an accepting run on $x$ from $(i,v)$. Since $x$ admits an accepting run from any position for some initial state, it is easy to see that all three conditions above are satisfied and $y\in Y$. $◀$

The proof of the following result is due to Ville Salo (personal communication).

By the constructions of Aubrun-Sablik [2] or Durand-Romaschenko-Shen [5], the lift of any one-dimensional subshift given by a computable set of forbidden patterns is a sofic subshift.

Let $A$ be the automaton that accepts $X^{\uparrow }$ in the sense that $X^{\uparrow }=L_{\mathrm{\infty }}(A)$, and $A^{\prime }$ be the automaton obtained by replacing every direction $\uparrow$ or $\downarrow$ by $\bullet$ in $A$.

Since every configuration in $X^{\uparrow }$ is constant in the vertical direction, $A^{\prime }$ accepts every configuration in $X^{\uparrow }$ (as well as additional configurations that are not constant vertically). Since $A^{\prime }$ only travels horizontally, it can be seen as a two-way one-dimensional automaton that accepts exactly the one-dimensional configurations that lift to $X^{\uparrow }$; in other words, $A^{\prime }$ accepts $X$. It follows that $X$ is defined by a regular set of forbidden patterns, so it is sofic.$◀$

To prove Theorem 8, see that the lift $X^{\uparrow }$ of any non-sofic one-dimensional subshift $X$ given by a computable set of forbidden patterns is sofic and not accepted by any alternating PWA. It is well-known that such subshifts exist; see e.g. [12, Example 3.1.7].

Given a PWA $A$, define $A^{\prime }$ as follows. From the initial state, check the area $\{\bullet ,\uparrow ,\mathrm{\to }\}$ around the initial position. If a forbidden pattern is found, reject; this is done deterministically. Otherwise, come back to the initial position and execute a run of $A$. $A^{\prime }$ belongs to the same class as $A$ and accepts all configurations in $L_{\mathrm{\infty }}(A)$ where no forbidden pattern appears. $◀$

Let $A$ be the automaton represented in Figure 2. Every run starting from a position containing $0$ accepts. Therefore every configuration with no $1$ is accepted.

If $A$ starts on a $1$ at position $i$, it nondeterministically picks a quarter-plane to explore and rejects if this branch encounters another $1$. A run never visits a given position twice, so if $x$ contains a single $1$, all runs accept.

If $x$ contains two $1$ at positions $i$ and $j$, draw a path from $i$ to $j$ using at most two directions in $\{\mathrm{\to },\uparrow ,\leftarrow ,\downarrow \}$. This path yields a rejecting run starting from $i$. $◀$

The following proof is related to Proposition 1 in [14], which only holds for deterministic PWA (and a larger class of subshifts). Intuitively, ${\mathrm{\Sigma }}_1$-automata are ill-fitted to explore unbounded spaces, as a run may reject from a given starting point only if all branches reject, but every branch may only visit a small part of the space.

In the next proof, we use the notation $p\pm K=\{p\pm i:i\in K\}$ for $p\in {\mathbb{Z}}^2,K\subset {\mathbb{Z}}^2$.

Let $A$ be a ${\mathrm{\Sigma }}_1$ PWA with $C$ states; we show that $X_{ssu}\ne L_{\mathrm{\infty }}(A)$. For $\overrightarrow{v}\in {\mathbb{Z}}^2$ and $r\in \mathbb{N}$, we denote by $B^{+}(\overrightarrow{v},r)$ the set $\{j\in {\mathbb{Z}}^2:\exists k\in {ℝ}^{+},d(j,k\overrightarrow{v})\le r\}$ (for the Manhattan distance on ${ℝ}^2$), and $B(\overrightarrow{v},r)=B^{+}(\overrightarrow{v},r)\cup -B^{+}(\overrightarrow{v},r)$. In other words, this is the band of width $r$ around the (half-)line of direction $\overrightarrow{v}$ starting from $0$; if $\overrightarrow{v}=0$, $B(0,r)=B^{+}(0,r)$ is a ball of radius $r$. When $r$ is not indicated, we assume that $r=C$.

Let $A$ be a ${\mathrm{\Sigma }}_1$-automaton that accepts all configurations in $X_{ssu}$. Define $x\in X_{ssu}$ such that $x_i=0$ for all $i$; $y\in X_{ssu}$ such that $y_0=1$ and $y_i=0$ for all other positions $i$; and, for any $p\ne 0$, $z^p\notin X_{ssu}$ such that $z_0^p=z_p^p=1$ and $z_i^p=0$ for all other positions $i$. We find some $p$ such that $A$ accepts $z^p$, showing that $A$ does not accept $X_{ssu}$.

To find some accepted $z^p$, we use the following property: if there is an accepting branch in $x$ that visits neither $0$ nor $p$, the same branch is accepting in $z^p$. Similarly, if an accepting branch in $y$ does not visit $p$ or an accepting branch in ${\sigma }^p(y)$ does not visit $0$, then the same branch is accepting in $z^p$.

Let $S_1(r)\subset V\times B(0,r)$ be such that $(s,k)\in S_1$ if and only if there is an accepting run on $y$ from $(s,k)$. For each $(s,k)\in S_1$, pick an arbitrary accepting branch $b$. It is described by a sequence ${(s_n,p_n)}_{n\in \mathbb{N}}\in {(V\times {\mathbb{Z}}^2)}^{\mathbb{N}}$. If $b$ stays in $B(0)$, we find two steps such that $(s_i,p_i)=(s_j,p_j)$ and, by a pumping argument, we build another accepting branch $b_p$ which is eventually periodic and stays in $B(0)$. If $b$ leaves $B(0)$, we find two steps such that $s_i=s_j$ and $d(0,p_j)\ge d(0,p_i)$ and, by a pumping argument, we build another accepting branch $b_p$ which is eventually periodic up to translation by the pumping vector $v^{(s,k)}=p_j-p_i$ every $j-i$ steps; in other words, $b_p$ stays in some band $B(v^{(s,k)})$. Denote $P_1(r)=\{v^{(s,k)}:(s,k)\in S_1(r)\}$ the set of all such pumping vectors.

Let $S_0\subset V$ be the set of states reachable from $i_0$ through a path labelled by $0$. Since $x$ is accepted, there must be a cycle that stays in $S_0$. For any such simple cycle (without repeated states), the associated pumping vector is the sum of all directions. Denote $P_0$ the finite set of all such pumping vectors.

We distinguish two cases that we illustrate in Figure 3.

We build a $\exists$ automaton that accepts $X_{cl}$ assuming that patterns from Definition 19 do not appear; we can do this assumption by Lemma 15. The automaton is represented in Figure 4.

If the initial position is not the entrance of a labyrinth $\mathrm{\#}1$, accept (by looping). Otherwise, walk nondeterministically in all directions $\nearrow ,\mathrm{\to },\searrow$. Keep going as long as you see $0$, accept if you find a $1$, reject if you find a $\mathrm{\#}$. Therefore the automata accepts if and only if, starting from every entrance, one branch found a matching exit. $◀$

Intuitively, in order for a run to reject a labyrinth with no exit, some individual branch must reject, which requires visiting a region of unbounded size (depending on the width on the labyrinth). By making the width large enough, we disorient this run into rejecting a valid configuration because it cannot check all required cells.

Let $A$ be a ${\mathrm{\Pi }}_1$-automaton that rejects all configurations not in $X_{cl}$. We build a configuration $y\in X_{cl}$ that $A$ rejects, the process being illustrated in Figure 5.

First define a configuration $x^n\notin X_{cl}$ for some $n>|Q|$.

Since $A$ rejects $x^n$, there exists a position from which there is no accepting run of $A$; that is, some branch $b$ from some position $p$ rejects (in finite time). The configuration would be valid if we switched the symbols at positions $(0,0)$ or $(n,k)$ for any $-n\le k\le n$; therefore $b$ must visit all these positions, since it would otherwise reject a valid configuration.

Within $x^n$, we call “the left” the half-plane $i\le 0$, “the right” the half-plane $i\ge n$, and “the center” the band . For simplicity, we assume that $b$ starts in the left and ends in the right. We decompose $b$ as ${\mathrm{\ell }}_0{c}_0^{\mathrm{\ell }\to r}{r}_0{c}_0^{r\to \mathrm{\ell }}\mathrm{\dots }{\mathrm{\ell }}_T{c}_T^{\mathrm{\ell }\to r}{r}_T$, where for all $k=0,\mathrm{\dots },T$:

• $\mathrm{■}$

  every subsequence is nonempty;

• $\mathrm{■}$

  ${\mathrm{\ell }}_k$ starts in the left, stays in the left and center, and ends in the left (left stays);

• $\mathrm{■}$

  $r_k$ starts in the right, stays in the right and center, and ends in the right (right stays);

• $\mathrm{■}$

  $c_k^{\mathrm{\ell }\to r}$ and $c_k^{r\to \mathrm{\ell }}$ stay in the center (center crossings).

Consider the first crossing $c_0^{\mathrm{\ell }\to r}$. Crossing takes at least $n$ steps, so we find two positions $(i,j)$ and $(i+a_0,j+b_0)$ with $a_0>0$ that $c_0^{\mathrm{\ell }\to r}$ visited in that order in the same state; $(a_0,b_0)$ is the pumping vector. Similarly, we find such pumping vectors $(a_k,b_k)$ with $a_k>0$ for all $c_k^{\mathrm{\ell }\to r}$ and $({\alpha }_k,{\beta }_k)$ with for all $c_k^{r\to \mathrm{\ell }}$.

By pumping on these vectors on each crossing, we build a branch $b^{\prime }$ that will be valid on some other configuration $y\ne x^n$; for the time being, we only pay attention to the positions in the branch and not to the underlying configuration.

Let $C$ be the lowest common multiple of all $a_k$ and $-{\alpha }_k$ and let $m>0$ to be fixed later. We define $b^{\prime }={\mathrm{\ell }}_0^{\prime }{c}_0^{\prime \mathrm{\ell }\to r}{r}_0^{\prime }{c}_0^{\prime r\to \mathrm{\ell }}\mathrm{\dots }{\mathrm{\ell }}_T^{\prime }{c}_T^{\prime \mathrm{\ell }\to r}{r}_T^{\prime }$ step by step.

• $\mathrm{■}$

  ${\mathrm{\ell }}_0^{\prime }={\mathrm{\ell }}_0$ is unchanged;

• $\mathrm{■}$

  $c_0^{\prime \mathrm{\ell }\to r}$ is $c_0^{\mathrm{\ell }\to r}$ that we pump $\frac{mC}{a_0}$ times along the vector $(a_0,b_0)$.

• $\mathrm{■}$

  $r_0^{\prime }={\sigma }^{(mC,\frac{mC}{a_1}{b}_1)}(r_0)$; in other words, $r_0^{\prime }$ is shifted relative to $r_0$ so that the positions are consistent with the previous part.

• $\mathrm{■}$

  $c_0^{\prime r\to \mathrm{\ell }}$ is $c_0^{r\to \mathrm{\ell }}$ shifted by $(mC,\frac{mC}{a_1}{b}_1)$ and pumped $\frac{mC}{-{\alpha }_0}$ times along the vector $({\alpha }_0,{\beta }_0)$.

In a similar manner, we pump every crossing in the center and shift:

• $\mathrm{■}$

  ${\mathrm{\ell }}_k^{\prime }$ and $c_k^{\prime \mathrm{\ell }\to r}$ by $(0,o_k^{\mathrm{\ell }}(m))$, where $o_k^{\mathrm{\ell }}(m)={\mathrm{\Sigma }}_{i=0}^{k-1}\frac{mC}{a_i}{b}_i+{\mathrm{\Sigma }}_{i=0}^{k-1}\frac{mC}{-{\alpha }_i}{\beta }_i$;

• $\mathrm{■}$

  $r_k^{\prime }$ and $c_k^{\prime r\to \mathrm{\ell }}$ by $(mC,o_k^r(m))$ where $o_k^r(m)={\mathrm{\Sigma }}_{i=0}^k\frac{mC}{a_i}{b}_i+{\mathrm{\Sigma }}_{i=0}^{k-1}\frac{mC}{-{\alpha }_i}{\beta }_i$.

These values are chosen so that the positions are locally consistent with allowed transitions in $A$. Notice that $o_k^{\mathrm{\ell }}(m)-o_{k^{\prime }}^{\mathrm{\ell }}(m)$ is either always $0$ or tends to $\pm \mathrm{\infty }$ as $m\to \mathrm{\infty }$.

Denoting $\phi$ the footprint, we see that $\phi ({\mathrm{\ell }}_k^{\prime })=\phi ({\mathrm{\ell }}_k)+o_k^{\mathrm{\ell }}(m)$. Because every $\phi ({\mathrm{\ell }}_k)$ is finite, we can find $m$ large enough such that, for all $k$ and $k^{\prime }$, $\phi ({\mathrm{\ell }}_k^{\prime })\cap \phi ({\mathrm{\ell }}_{k^{\prime }}^{\prime })=\mathrm{\varnothing }$ or $\phi ({\mathrm{\ell }}_k^{\prime })\cap \phi ({\mathrm{\ell }}_{k^{\prime }}^{\prime })=\phi ({\mathrm{\ell }}_k)\cap \phi ({\mathrm{\ell }}_{k^{\prime }})$, and similarly for right stays. In other words, two stays either visit no cell in common or they cross in exactly the same manner as the original branch.

If needed, we increase $m$ so that $m>|\phi (b)|$.

Now we build a configuration $y$ so that $b^{\prime }$ is a branch of the run starting at the same position $p$. Start by putting $y=x^{n+mC}$, and do the following modifications:

1. 1.

   set $y_{(0,o_k^{\mathrm{\ell }}(m))}=1$ for all $k$;

2. 2.

   choose some $i$ such that and $(n+Cm,i)\notin {\bigcup }_k\phi (r_k^{\prime })$. Then set $y_{(n,i+o_k^{\mathrm{\ell }}(m))}=1$ for all $k$.

Condition 1 adds entrances at such positions that the left stay ${\mathrm{\ell }}_k^{\prime }$ “sees” an entrance exactly when the original left stay ${\mathrm{\ell }}_k$ saw an entrance at position $(0,0)$. This does not impact other left stays by the argument above.

Condition 2 adds exits at positions that are not visited by $b^{\prime }$, which is possible because we chose $m$ to be larger than the footprint of $b$, but satisfy the definition for a valid labyrinth. This ensures that $y\in X_{cl}$ and that $b^{\prime }$ rejects.

By construction, the branch $b^{\prime }$ is a branch for the run on $y$ starting at $p$. It follows that $y\in X_{cl}$ is rejected by $A$, a contradiction. $◀$