# MIDTERM Is a Deterministic Technique to Exit Recursive Mazes

Charles Bouillaguet, Orel Cosseron

<figure><img src="image_1.png" /></figure>

## To cite this version:

Charles Bouillaguet, Orel Cosseron. MIDTERM Is a Deterministic Technique to Exit Recursive Mazes. 2026. hal-05517329

HAL Id: hal-05517329

https://hal.science/hal-05517329v1

Preprint submitted on 18 Feb 2026

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# MIDTERM Is a Deterministic Technique to Exit Recursive Mazes

Charles Bouillaguet

<figure><img src="image_3.png" /></figure>

LIP6 laboratory, Sorbonne Université, Paris, France

Orel Cosseron

<figure><img src="image_4.png" /></figure>

Independent researcher

## Abstract

A recursive maze is a maze that contains copies of itself (that themselves contain copies of themselves, etc.). To exit the maze or reach the goal, each recursive block that has been entered must be exited. These once-popular puzzles are difficult to solve by hand, and this begs for an algorithmic solution.

It has been observed many times in the past that a recursive maze can be represented by a deterministic pushdown automaton. Finding a path, possibly the shortest, that leads to an exit therefore reduces to finding a word in a context-free language described by such an automaton. The problem is well-known to be decidable, and there is a classical algorithm for this task. We present a new algorithm, MIDTERM, with improved complexity compared to existing solutions.

MIDTERM improves on a previous attempt called LONGTERM (Obviously Not a Good Technique to Exit Recursive Mazes).

**2012 ACM Subject Classification** Theory of computation → Grammars and context-free languages; Theory of computation → Graph algorithms analysis

**Keywords and phrases** Quantum computing, blockchains, IA, pushdown automaton, reachability, graph rewriting, addition chains, recursive maze, $(\lambda x.xx)(\lambda x.xx)$

## 1 Introduction

A recursive maze is a maze that contains copies of itself. As the adage goes, a picture is worth a thousand words, and the concept is therefore best illustrated by Figures 1 and 2. Recursive mazes have been invented by Mark J. P. Wolf and the first one was published in 1996 under the name "fractal maze" (Extropy #17, p. 67, available in the internet archive). Similar puzzles later appeared both in print and online. Recursive mazes are notoriously difficult to solve by hand, without taking notes and/or using an *ad hoc* computer program to track one's position in the maze. Several such program exist, notably to play in a web browser, such as

https://amurielagi.github.io/fractal-maze/

or

\begin{shameless-advertisement}

https://orelcosseron.github.io/fractal-maze/

\end{shameless-advertisement}

At first glance, a recursive maze looks like the floor plan of an integrated circuit, that itself contains "boxes" representing inner integrated circuits. There are *wires* connecting the "outer" IO pins (on the edge of the circuit) to the "inner" IO pins of the boxes contained inside. The
<figure><img src="image_5.png" /><figcaption>Figure 1 Two early recursive mazes designed by Mark J. P. Wolf. First published in *Extropy #17*, Fall 1996, page 67 (left) and in the "Bogglers" column of the June 2004 issue of *Discover Magazine*, page 86 (right). See also the book [19] by the same author.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 2 Two other recursive mazes designed by Mike Earnest (published on July 2016 as a StackExchange puzzle, left) and Tristan "Siggy" Miller (published on October 2010 on the Skeptic's Play blog, right).</figcaption></figure>
boxes are often distinguished with capital letters. There are also special locations, such as $⊕$ and $∩$ in Fig. 1, or the starting point ("you are here") in Fig. 2. The aim of the puzzle consists in following the wires from point A to point B: from $∩$ to $⊕$ in Fig. 1, from the starting point to the outside or to the finish line in Fig. 2. The trick is that, when following a wire, we may hit one of the inner boxes. In this case, we "enter" the box, which is a copy of the whole maze. Each entered box must be exited, by reaching one of its outer IO pin.

This is where the real fun begins. For one, exiting may not be possible at all. Consider for instance the innocent-looking maze:

<figure><img src="image_7.png" /></figure>

From the starting point, one has to enter A (from the left). But from there, the only option is to follow the wire that leads to B, and enter on the left. From there, we are stuck in an infinite loop of entering B, and there is no way that we can exit the maze. In fact, the maze expands to:

<figure><img src="image_8.png" /></figure>

It follows that simple graph-search techniques are not sufficient to decide if there is a way to exit the maze, because the graph that consists of all possible paths is infinite (even though it has a regular structure). Sometimes it is easy to determine that the maze is unsolvable, for instance if the available paths always enter a recursive box (without any option to exit). This is clearly the case on the left maze of Fig. 3, but what about the one on the right? Because of the wire between pins 4 and 7, there is potentially a way to exit a recursive box. More precisely, any box entered on pin 4 or 7 can be exited by the opposite pin (and that's
<figure><img src="image_9.png" /><figcaption>■ **Figure 3** Two unsolvable recursive mazes by Tristan “Siggy” Miller (published on October 2023 on the Freethought blogs). On the right, the goal is to reach the “F” from any outer IO pin. These mazes are unsolvable with the normal rules, but what if one allows transfinite moves?</figcaption></figure>

it). So the only way to reach the goal would be to exit C by pin 4 or 7... but this requires C to be entered by pin 7 or 4, in which condition the goal was already reachable. Therefore, the target cannot be reached.

When the maze is known to be solvable (i.e., there is a finite path from the start to a target), then a breadth-first-search will find it. It will even find the shortest possible one. However, the number of explored nodes might be exponential in the size of the maze.

And there is worse: the length of a shortest path can itself be exponential in the size of any reasonable description of the maze. Consider for instance the maze shown in Fig. 4. A moment's thought will reveal that there is a path from the north-east to the south that goes through 0. Then, there is a path from the north to the south that enters 1, goes through 0, exits 1 and go through 0 again. Then there is a path from the north-west that enters 2, goes through 1, exits 2 and goes through 1 again, etc. Generalizing this construction to an *n*-gon yields a family of recursive mazes where the only way to exit makes an exponential number of steps in the size of the maze.

We first take one aspect of the problem off the table: out of the two possible goals (getting out of the maze, or reaching $⊕$ starting from $⊗$), only getting out is interesting. More precisely, every maze where the goal is to reach a specific wire can be converted into another maze where the goal is to exit. Fig. 5 shows how. Interestingly, we do not know how to make the conversion the other way around. The obvious attempt (shown in Fig. 6) fails, because it creates extra connections between wires that may lead to spurious solutions. For instance, it allows to escape the unescapable “innocent-looking” maze shown above.

In this article, we consider old and new algorithms to decide, in polynomial time, if the maze can be exited or not. All these algorithms produces (in polynomial time) a description of a solution path, even if it is of exponential length. We compare their complexities, expressed in terms of various characteristics of the maze: the number of wires $W$, the number of recursive boxes $B$ and the number $E$ of possible ways to enter a recursive box (8 in the maze on the left of Fig. 7).
<figure><img src="image_10.png" /><figcaption>Figure 4 The “power-of-two” maze.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 5 Converting a maze from “reaching an internal goal” to “getting out”. The new red maze contains all the content of the original maze plus an extra recursive box that connects “start” to $\emptyset$.</figcaption></figure>

After presenting some context, we review in section 6 the classical technique that decides emptiness of the context-free language associated to a deterministic pushdown automaton built from the description of the maze. It runs in time $O(W^2EB)$. In section 7, we review improved algorithms to decide reachability of arbitrary states in pushdown automata, that yield a faster decision procedure with complexity $O(W^3)$. Finally, in section 8 we discuss a new algorithmic technique to compute equivalence classes of wires inside a recursive maze. In section 9 we discuss the efficient implementation of this procedure, and show a version that terminates in time $O(WB + E\alpha(W))$, where $\alpha$ is the inverse-Ackermann function, improving the state of the art. We discuss how to bring this down to $O(E \log E)$, but this seems to either require: a) cheating, or b) randomization. Lastly, in section 10, we discuss how to actually construct an exit path (this was the whole point of the paper, isn't it?).

“Solving” recursive mazes in linear time, e.g. $O(W + E + B)$ is left as an intriguing open problem.
<figure><img src="image_12.png" /><figcaption>Figure 6 Trying to convert a “getting out” maze into a “reach internal target” maze in the obvious way does not work (it creates extra connections between wires).</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 7 A simple maze of our own design (left) and its “dual” representation (right). Wires with a double-box are “accepting” (connected to an outer IO pin).</figcaption></figure>

## 2 Topological representation of recursive mazes

A recursive maze has several parameters: the number *B* of recursive boxes (from 2 to 8 in the given examples), the number of output pins, the number *W* of wires. As a convention, inner boxes are identified by capital letters (A, B, C, ...), outer IO pins are referenced by numbers and wires are referenced by Greek letters. An inner IO pin (on a recursive box) is referenced by the identifier of the box and that of the pin. For example, on Fig. 3 (left), “1” is connected to “A.6” and “C.3”. An *endpoint* is either an outer pin, or an inner pin. A wire connects a set of endpoints. For instance, the wires of the simple maze shown on the left of Fig. 7 are:

$$ \{\text{start}, A.4\}, \{4, B.1\}, \{1, 2, C.3, D.1\}, \{3, 5, A.2, C.5\}, \{D.2, B.2\} $$

This completely represents the maze, and can easily be encoded as a text file. The size of this text file is a good measure of the size of the maze. Note that a recursive maze is therefore a hypergraph whose vertices are the endpoints. It even seems legitimate to consider this as “the” abstract description of the maze. Note that in principle each endpoint must appear in at most one wire, and each outer IO pin must appear in exactly one wire for the maze to be well-formed. This implies that $E \le BP$ and $W \le P$.
An alternate, “dual” description is also useful (Fig. 7, right): it is a directed graph whose nodes are the wires of the maze, and where there is a directed edge $\alpha \xrightarrow{X.i} \beta$ if it is possible to go from wire $\alpha$ to wire $\beta$ by entering the recursive box labelled $X$ using its pin labelled $i$. As before, $E$ denotes the number of edges of this graph. The dual representation graph can be assembled in essentially linear time from the previous “hypergraph” representation:

- First, associate each outer pin to the wire that contains it.

- Initialize an empty directed graph $G$ on the wires.

- Then, for each wire $\phi$, do:

- For each inner pin $X.i$ in $\phi$, add an edge labelled by $X.i$ from $\phi$ to the wire containing the outer pin $i$ (if it does not already exist).

It follows from the well-formedness conditions that all edge labels are distinct in the dual representation graph. The original “hypergraph” representation can be reassembled from the dual representation graph, under the assumption that the initial location (**start**) is always incident to the wire $\alpha$. An edge $\alpha \xrightarrow{X.i} \beta$ means that the outer IO pin $i$ belongs to wire $\beta$, and that $X.i$ belongs to wire $\alpha$. By convention, the starting point (**start**) belongs to wire $\alpha$.

Nothing prevent several outer IO pins to belong to the same wire. In the simple maze of Fig. 7, pins (1, 2) and (3, 5) are connected. But is this really necessary? When two outer IO pins belong to the same wire, couldn't we remove one of them (and redirect connections to the other one)? To answer this question, take the dual representation graph and erase all pin information:

<figure><img src="image_14.png" /></figure>

Then formulate the constraints:

- Different wires are not “inadvertently” connected to the same outer IO pin. This means that $\{i\}, \{j, n, o\}, \{p, m, k\}$ must be pairwise disjoint.

- Endpoints appear in a single wire. This means that inside the following sets, values are all different: $\{i, \ell\}, \{j, o\}, \{p, k\}$ and $\{n, m\}$.

The problem of assigning integer values in $\{1, \dots, N\}$, to the variables, for the smallest possible $N$, can be seen as a variant of the COLORABILITY problem, but it is an easy one. A simple algorithm will satisfy the constraints using the minimum possible number of values: first compute a “local” assignment of values to the unknowns for each disjoint subset in isolation; then form a global assignment by “shifting” values already used in previous subsets. For instance, in the example above, satisfying the inequality constraints inside each disjoint subset leads to:

$$ 
\begin{align*}
i &\rightsquigarrow 1 \\
j, n, o &\rightsquigarrow (1, 1, 2) \\
p, m, k &\rightsquigarrow (1, 1, 2)
\end{align*} 
$$
Then assembling all disjoint subsets leads to:

$$ (i), (j, n, o), (p, m, k) \rightsquigarrow (1), (2, 2, 3), (4, 4, 5) $$

Therefore, the simple maze discussed above cannot be simplified further: at least 5 outer IO pins are necessary (and sufficient). Let the disjoint subsets be $A_1, \dots, A_k$, and the all-different ones be $B_1, \dots, B_\ell$ (note that the $B_j$'s are also disjoint, because they correspond to different boxes). Then inside a disjoint subset $A_i$, the variables in $A_i \cap B_j$ must be all different, for each $j$. Therefore, $\min_j |A_i \cap B_j|$ values are necessary (and sufficient) for $A_i$.

Let us next look at the small maze on the right of Fig. 1. We number its pins from 0 to f clockwise (0,1,2,3 at the north, 4, 5, 6, 7 on the east side, 8,9,a,b at the south and c,d,e,f at on the west side). Pin 1 is clearly a decoy: nothing is connected to either A.1, B.1 or C.1. Next, pins 0, e and f belong to the same wire, but one of them is redundant. There are connections to A.0, B.0, C.0, C.e, A.f and B.f, therefore “merging” e and f is possible without creating extra connections. We assume that these extra pins are present for aesthetic reasons.

## 3 Recursive mazes as pushdown automata

Navigating recursive mazes in one's head is difficult because it is necessary to keep track of all the boxes that have been entered (and by what pin).

Suppose a sequence of instructions is given by the player to some kind of game engine. These instructions can be of three kinds: “from the current location, enter box X using its pin i” (encoded as $X.i$) or “from the current location, leave the current box X through the outer pin i” (encoded as $\overline{X.i}$) and finally “I have solved the problem” (done). For instance, this is a sequence of instructions for the simple maze of Fig. 7 (that presumably exits):

$$ A.4; B.1; \overline{B.2}; D.3; C.5; \overline{C.3}; \overline{D.1}; A.2; \text{done} $$

We note that $\overline{X.i}$ could be more compactly encoded as just “i” (we do not need to know that we are inside box X to just take the exit). However, this more verbose encoding enables us to define the mirror operation on instructions (also denoted with an overline): $\overline{X.i}$ is the mirror of $X.i$, and vice-versa so that $\overline{\overline{X.i}} = X.i$. Applying a (legal) instruction then its mirror is a no-op (the mirror cancels the effect of the first instruction). Lists of instructions can also be mirrored, by mirroring each instruction individually and reversing their order: $A.4; B.1; \overline{B.2} = B.2; \overline{B.1}; A.4$. Applying a sequence of legal instruction then its mirror is a no-op.

There is a way to efficiently check if a sequence of instruction is valid, i.e. if the desired moves are actually feasible. The validity of a move depend on the last box that was entered (for instance $A.2$ is valid inside A but not inside B, C and D). So it is required to track the current box, as boxes are entered and exited. The analogy with the call stack of a recursive function is quite obvious. This also strongly suggests some kind of stack-augmented automaton. This brilliant observation has certainly been made many times, by many people independently (including us), but a notorious and early statement is due to Peter Shor (of quantum polynomial factoring fame) in 2012, as a comment to a question on StackExchange). He writes:

*Can't you represent any fractal maze as a pushdown automaton, where the stack corresponds to the sequence of submazes that you're in? Then the solubility question would turn into the emptiness problem for context-free languages, which is decidable.*
Making this intuition precise is easier with the dual representation graph of recursive mazes. We assume that there is an initial wire (denoted as $\alpha$) where the player starts. The position of the player consists of a current wire and a stack of entered boxes. We write such a position as “wire | stack” or “wire stack”. The stack is initialized with the identifier of the “main” box that contains everything, which is denoted as $\perp$. Moving between wires pushes box identifiers on the stack (when a box is entered), or pops them (when a box is left). Entering box $X$ is always possible (if there is a wire leading to it of course), but exiting box $X$ only makes sense if we are currently inside it. The possible transitions from a given state are thus entirely determined by the top of the stack. If there is an edge $\phi \xrightarrow{X.i} \psi$ in the dual representation of the maze, then the player may move between positions $\phi|S$ and $\psi|X; S$ (both ways) by issuing $X.i$ or $\overline{X.i}$.

We can therefore describe a deterministic pushdown automaton (DPDA) for the maze, that accepts by empty stack. Suppose the set of outer pins is $\mathcal{P}$ (think $1, \dots, n$), the set of recursive boxes is $\mathcal{B}$ (think $\perp, A, B, C, \dots$) and the set of wires is $\mathcal{W}$ (think $\alpha, \beta, \dots$).

- The set of states of the DPDA is $Q := \mathcal{W} \cup \{\text{goal}\}$.

- The input alphabet is $\Sigma := \mathcal{B} \times \mathcal{P} \cup \overline{\mathcal{B}} \times \overline{\mathcal{P}}$.

- The stack alphabet is $\Lambda := \mathcal{B}$.

- The start state is a designated wire $\alpha \in \mathcal{W}$ (part of the specification of the maze).

- The initial stack symbol is $\perp$ (the global box).

- The transition function $f: Q \times \Sigma \times \Lambda \rightarrow Q \times \Lambda^*$ is defined as follows. For every edge $\phi \xrightarrow{X.i} \psi$ in the dual representation graph and for any box $Y \in \mathcal{B}$, $f(\phi, X.i, Y) = (\psi, XY)$ and $f(\psi, \overline{X.i}, X) = (\phi, \emptyset)$. If the goal is to exit the maze, additionally set $f(\omega, \text{done}, \perp) = (\text{goal}, \emptyset)$ for all wires $\omega$ adjacent to an outer IO pin. If the goal is to reach a specific wire $\omega$, set $f(\oplus, \text{done}, \perp) = (\text{goal}, \emptyset)$.

This pushdown automaton accepts all sequences of instructions that solve the maze. For instance, the following is a legal sequence of transitions in the simple maze of Fig. 7 (that exits the maze):

$$ \frac{\alpha}{\perp} \rightarrow \frac{A.4}{A \perp} \rightarrow \frac{\beta}{B \perp} \rightarrow \frac{\gamma}{BA \perp} \rightarrow \frac{\overline{B.2}}{A \perp} \rightarrow \frac{\zeta}{A \perp} \rightarrow \frac{\overline{D.3}}{DA \perp} \rightarrow \frac{\delta}{DA \perp} \rightarrow \frac{C.5}{CDA \perp} \rightarrow \frac{\overline{C.3}}{DA \perp} \rightarrow \frac{\gamma}{\overline{D.1}} \rightarrow \frac{\gamma}{A \perp} \rightarrow \frac{\overline{A.2}}{A \perp} \rightarrow \frac{\delta}{\perp} \xrightarrow{\text{done}} \text{goal} $$

As a consequence, the sequences of instructions that exit the maze form a (deterministic) context-free language. We note that there are off-the-shelf software libraries to test reachability of configurations in pushdown automata such as Moped [14] or PDAAAL [10] (just to mention a few) that can therefore be used to solve recursive mazes.

# 4 Construction of mazes with an exit path of a prescribed length

The dual representation of recursive mazes can be useful as a design tool. For instance, we highlight the conception of mazes where the exit path has a prescribed length. This length must be odd (because each entered box must be exited, and there is done at the end). For instance, suppose we would like to build a maze with a path of length 1337 (a random leet
10 MIDTERM Is a Deterministic Technique to Exit Recursive Mazes

value). We start from a *twisted addition chain* for 1335:

$$
\begin{align*}
5 &= 1 + (1+1) + (1+1) \\
19 &= 1 + (5+1) + (5+1) + (5+1) \\
101 &= 1 + (19+1) + (19+1) + (19+1) + (19+1) + (19+1) \\
307 &= 1 + (101+1) + (101+1) + (101+1) \\
1335 &= 1 + (101+1) + (307+1) + (307+1) + (307+1) + (307+1)
\end{align*}
$$

And we build the following graph (pins were assigned using the algorithm outlined above):

<figure><img src="image_15.png" /></figure>

The resulting maze has 15 pins, 6 recursive boxes and 20 wires. An exit path is provided by:

$$
\begin{align*}
\mathcal{P}_5 &:= \overline{B.1}; A.3; A.2; \overline{A.1}; \overline{A.1} \\
\mathcal{P}_{19} &:= \overline{C.1}; B.5; B.4; B.2; (\mathcal{P}_5)^3 \\
\mathcal{P}_{101} &:= \overline{D.1}; C.9; C.8; C.7; C.6; C.2; (\mathcal{P}_{19})^5 \\
\mathcal{P}_{307} &:= \overline{E.1}; D.11; D.10; D.2; (\mathcal{P}_{101})^3 \\
\mathcal{P}_{1335} &:= \overline{F.1}; D.15; E.14; E.13; E.12; E.2; (\mathcal{P}_{307})^4; (\mathcal{P}_{101}) \\
\mathcal{P}_{1337} &:= F.2; (\mathcal{P}_{1335}); \text{done}
\end{align*}
$$

The point is that the sequence of instruction $\mathcal{P}_5$ takes the player from wire $\tau$ to wire $\tau$ but exits box B. $\mathcal{P}_{19}$ does the same with box C, $\mathcal{P}_{101}$ with box D, etc. It is left to the reader to check that $\mathcal{P}_x$ has length $x$. We also hope that, at this point, the role of the “twisted addition chains” has become clear. A Twisted addition chain is a sequence of equalities of the kind $a_{i+1} = [\text{sum of } k \text{ previous } a_i\text{'s}] + (k+1)$, starting with $a_0 = 1$. The number of recursive boxes is one plus the number of steps of the twisted addition chain. The number of wires is two plus the total number of occurrences of all constants in right-hand sides of the twisted addition chain, and pins = wires + 1 - boxes.
Any Dyck language can be accepted by a recursive maze, as illustrated below for 3-Dyck:

<figure><img src="image_16.png" /></figure>

So, $h(\mathcal{L})$ is a subset of a Dyck language, but not any subset: it is contained in a *regular* language derived from the maze. Imagine that the dual representation graph is a finite automaton, in which the states corresponding to wires connected to an outer IO pin are accepting. Then for each edge add a “mirror” edge with the mirror instruction and keep only the box label, erasing the pin label on instructions. For instance, with the simple recursive maze of Fig. 7:

<figure><img src="image_17.png" /></figure>

This non-deterministic finite automaton “statically” describes possible moves in the recursive maze, ignoring the stack and the history of the computation. In this example, it expresses that from wire $\beta$ it is possible to enter box B to reach wire $\gamma$, and that you cannot enter box C from wire $\zeta$.

Denote by $R$ the regular language it accepts. Any valid sequence of instruction that exits the maze belong to $R$ (but the converse is not true). In the end, we find that $h(\mathcal{L}) \subseteq D \cap R$, where $D$ is the Dyck language with $B$ delimiters and $R$ is the regular language defined above. A moment's thought will reveal that this inclusion is in fact an equality, and yield:

**Theorem 1 (informal).** Let $\mathcal{L}$ be the language of all sequences of instructions that exit a recursive maze. Then $h(\mathcal{L})$ is precisely the intersection of the B-Dyck language with $R$, the regular language derived from the “undirected” version of the dual representation graph of the maze.

By the Chomsky-Schützenberger representation theorem [4], any context-free language can be obtained by applying a homomorphism to the intersection of a Dyck language and a regular language. This opens up the possibility that applying a homomorphism to $\mathcal{L}$ may yield a large class of context-free languages.

However, there is a severe restriction. The regular language in the intersection must be such that the graph describing the associated finite automaton is “undirected” (see [13] for more results on this kind of automata—they are said to be “dual and connected” in [17]). This
highlight a nasty “feature” of recursive mazes: all moves are reversible. Mistakes can be undone without having to hit CTRL+Z, just by entering an appropriate instruction (exit the box that has just been entered, or re-enter the box that has just been left).

In a valid sequence of instructions, it is possible to insert anywhere an arbitrarily long sequence of arbitrary (legal) moves, and then “undo” them to return to the same position while leaving the stack unchanged. This shows that even very simple *regular* languages (recognized by a deterministic finite automaton) such as $a^*b^*$ cannot be obtained by applying a homomorphism to $\mathcal{L}$. Indeed, suppose it could: the homomorphism sends some instructions to $a$ and some others to $b$. Start from a valid sequence of instruction that emits a word in the language (say *aaaabb*). Then “undo” it and replay it. This yields another valid sequence of instructions that emits “*aaaabb* [some stuff] *aaaabb*”, and this does not belong to $a^*b^*$.

*Irreversible progress* is banned from maze-associated languages.

We see a striking analogy with abstract quantum computational models: applying a unitary transformation to the state of a quantum system is reversible, *just like moves in a recursive maze*. This sheds new light to the intervention of Peter Shor in the field of recursive mazes (we are not so naive as to believe that it is a mere coincidence). Therefore, we plan to push forward the idea that recursive mazes are ideally suited as a computational model for future quantum computers (although we are going to leave that aspect aside for future work).

Characterizing the class of context-free languages that can be obtained by applying a homomorphism to the language associated to a regular maze remains an open problem.

# 6 Off-the-shelf algorithms to exit recursive mazes

Given a recursive maze, the “dual representation” graph can be built in linear time, and from there we have derived the context-free language of valid sequences of instructions. It is easy to write a context-free grammar (CFG) for this language. Emptiness of the language can be decided in time linear in the size of the grammar (it seems this was the solution implicitly suggested by Peter Shor). We now describe the classic algorithm that does this.

The non-terminal symbols are $L$ (the language itself) and $[\alpha X\beta]$ for $\alpha, \beta \in W$ and $X \in \mathcal{B}$. Intuitively, $[\alpha X\beta]$ is the set of sequence of instructions that move from wire $\alpha$ to wire $\beta$ while exiting the box $X$. The derivation rules are as follows. For the whole language, we need to exit the maze, so we need to reach the outside of the starting box (popping $\perp$), from the starting wire $\alpha$.

■ $L ::= [\alpha \perp \omega]$ (for all wire $\omega \in W$)

Then for each edge $\phi \xrightarrow{X.i} \psi$ in the dual representation of the maze:

■ $[\psi X \phi] ::= \overline{X.i}$

■ $[\phi Y \omega] ::= X.i [\psi X \chi] [\chi Y \omega]$ (for all wires $\omega, \chi$ and all boxes $Y \in \{\perp\} \cup \mathcal{B}$)

So, there are $BW^2$ non-terminals, and $1 + BW^2$ derivation rules per edge in the dual representation of the maze. The usual algorithm to decide emptiness operates by iteratively marking variables that produce a string of terminal symbols and/or marked variables. It can be implemented to run in constant time per derivation rule. This decides if a recursive maze can be exited in time $O(W^2EB)$.
<figure><img src="image_18.png" /><figcaption>■ **Figure 8** botched attempt at 3-Dyck Maze showing that the number of edges in the dual representation graph can be quadratic in the number of wires.</figcaption></figure>

However, the dual representation of the maze can have $E = \Omega(W^2)$ edges. This is for instance the case of the maze shown in Fig. 8: there are $k+1$ wires, and except the special one that it connected to $\oplus$ and $\ominus$, they are all reachable from one another. So the dual representation graph has $k(k+1)$ edges.

It follows that the generic technique may require $\Omega(BW^4)$ operations. However, the context-free grammar, once constructed, reveals much information about the language. In particular, it is fairly easy to find the shortest path that exits the maze (associate to each non-terminal the shortest word that can be obtained from it, and take the minimum over each possible derivation rule).

## 7 Getting out of recursive mazes faster with inter-dimensional wormholes

There is a more efficient technique that can be better suited to laaaaarge recursive mazes. It is heavily inspired by algorithms designed almost simultaneously by Bouajjani, Esparza and Maler [2] on the one hand and Finkel, Willems and Wolper [7] on the other hand. These algorithms were created to decide reachability properties in pushdown systems, in the context of model checking problems that could admit such a representation.

The main idea behind this algorithm is simple. If there are two edges $\alpha \xrightarrow{X.i} \beta \xleftarrow{X.j} \gamma$ in the dual representation graph, then it is possible to move from $\alpha$ to $\gamma$ as follows: starting from wire $\alpha$, enter the recursive box $X$ using its $i$-th pin (this lands on wire $\beta$ inside $X$), then leave $X$ using its $j$-th pin (this lands on wire $\gamma$ outside of $X$). Of course, the return trip is also possible.

More generally, if there is a sequence of instructions $S$ that allows the player to travel from wire $\beta$ to wire $\gamma$ while exiting box $X$ (popping $X$ from the stack), then $X.i; S$ is a sequence of instructions that allows the player to travel from $\alpha$ to $\gamma$ while leaving the stack unchanged. This is the main idea underlying the construction of the context-free grammar given above.

We therefore define a binary relation $\equiv$ between wires, where $\alpha \equiv \gamma$ if and only if there is a box $X$ and two pins $i, j$ such that the two edges $\alpha \xrightarrow{X.i} \beta \xleftarrow{X.j} \gamma$ exist in the dual representation graph. In this case we say that there is a *local wormhole* between $\alpha$ and $\gamma$. Note that $\equiv$ is symmetric, but not necessarily reflexive nor transitive. We then consider the
following sequence of pairs of wires:

$$
\begin{align*}
\Gamma_0 &= \{(\alpha, \beta) \mid \alpha \equiv \beta\} \cup \{(\omega, \omega) \mid \omega \in \mathcal{W}\} \\
\Gamma_{i+1} &= \Gamma_i \cup \{(\alpha, \gamma) \mid \exists \beta. (\alpha, \beta) \in \Gamma_i, (\beta, \gamma) \in \Gamma_i\} \\
&\phantom{=} \cup \{(\alpha, \delta) \mid \exists \beta. \exists \gamma. (\alpha, \beta) \in \Gamma_i, \beta \equiv \gamma, (\gamma, \delta) \in \Gamma_i\}
\end{align*}
$$

The sequence Γᵢ is increasing (with respect to set inclusion) and upper-bounded by W × W,
therefore it converges (in a finite number of steps) to a limit denoted as Γ∞. We write α ≡ᵢ β
(resp. α ≡* β) as syntactic sugar for (α, β) ∈ Γᵢ (resp. Γ∞).

► **Lemma 2.** * is the smallest equivalence relation such that $\alpha \xrightarrow{X.i} \beta \stackrel{*}{\equiv} \gamma \xleftarrow{X.j} \delta \implies \alpha \stackrel{*}{\equiv} \delta$.*

**Proof.** By intimidation: if this is not obvious to the reader, then they better stop reading *RIGHT NOW!* (otherwise, the argument is that the $\Gamma_i$ are constructed to this purpose; $\stackrel{*}{\equiv}$ is the least fixed-point of the increasing function on pairs of wires that guarantees the wanted properties). ◀

The idea is that there is a sequence of instruction that takes the player from $\alpha$ to $\delta$ while leaving the stack unchanged whenever $\alpha \stackrel{*}{\equiv} \delta$. We then say that there is a *transitive wormhole* between $\alpha$ and $\delta$.

Most games that require the player to explore a large map have some built-in mechanism to “fast-travel” between some previously visited locations. Recursive mazes lack this mechanism, and that is really unfortunate. For this reason, we suggest to extend the game with the ability to fast-travel through wormholes (and we bet that this could relieve players of a considerable amount of frustration). We extend the usual semantic of the dual representation graph with these wormholes, using dashed edges:

<figure><img src="image_19.png" /></figure>

Note that the wormhole between $\gamma$ and $\zeta$ is transitive ($\gamma \not\equiv \zeta$ but $\gamma \stackrel{*}{\equiv} \zeta$). From this, we observe that $\alpha \xrightarrow{A.4} \beta \stackrel{*}{\equiv} \gamma \xleftarrow{A.2} \delta$, so that $\alpha \stackrel{*}{\equiv} \delta$ and the maze can be exited from the starting wire.

The algorithm described in [2, 7] essentially consists in explicitly computing $\stackrel{*}{\equiv}$ by iterating the recursive construction starting from $\equiv$ until a least fixed point has been reached. This algorithm has complexity cubic in the number of states of the automaton. In our context, this leads to an algorithm with complexity $O(W^3)$, which is already better than constructing the associated context-free grammar.

This algorithm adds all the possible wormhole edges to the dual representation graph (at most $W^2$ of them). Each edge can be labelled with a unique identifier. Local wormhole edges can additionally be labelled with a sequence of *two* instructions. Transitive wormhole edges can be labelled with a tuple of (instruction, wormhole identifier, instruction). All wormhole
edges can be labelled with a length. Therefore, not only it is possible to find a the shortest path from the starting point to an exit (using only wormhole edges), but it is possible to emit a description of this path in polynomial time, even though the path may have exponential length, by printing the labels of the crossed wormhole edges.

In passing, [2, 7] show that the set of stacks that the player can have when sitting on a given wire is a regular language (accepted by a deterministic finite automaton).

## 8 Getting out of recursive mazes even faster by collapsing wormholes

The main contribution of this paper is that, in the case of recursive mazes, it is possible to do better than [2, 7]. Our starting point is that the reversible nature of all movements makes it possible to exploit equivalence classes of wires. If $\alpha \equiv \beta$, then we are going to consider that $\alpha$ and $\beta$ are “the same wire”, and as far as reachability is concerned no information is lost by doing so.

This is different from the general problem tackled by [2, 7] of deciding reachability of a given state in an arbitrary pushdown automaton. The main difference is that in a general PDA there may be a sequence of transitions from a state $q$ to another state $q'$ that leaves the stack unchanged, while there might not be a sequence of transitions from $q'$ to $q$ that leaves the stack unchanged. In recursive mazes, we now that the latter exists.

This makes it possible for us, instead of explicitly building a clique between equivalent wires as in [2, 7], to build a (much smaller) *spanning tree*: this preserves reachability properties. The same technique is used in the context of sparse matrix factorization [8] to construct the elimination tree of the matrix $A^t A$, given a sparse matrix $A$ and without explicitly forming $A^t A$ that might be much denser. Each row of $A$ with $k$ non-zero entries creates a clique of size $k$ in the graph whose adjacency matrix is $A^t A$. This clique is replaced by a path that preserves reachability.

Our proposed solution is also inspired by the “edge-contracting” probabilistic algorithm of Karger for min-cut [11]. The core idea of our proposal is simple: when a local wormhole $\alpha \xrightarrow{X.i} \beta \xrightarrow{X.j} \gamma$ is identified, we add an edge $\alpha \text{<--->} \gamma$ to the dual representation graph, and we immediately contract it. This collapses the two nodes that are the extremities of the wormhole into one and deletes the newly added edge. The reader may wonder what was the point of adding an edge just before deleting it. So, OK, let’s not add it, and instead directly “merge” the two equivalent wires. This operation creates a *supernode* labelled with a set of wires ({$\alpha, \gamma$} if starting from $\alpha$ and $\gamma$), as opposed to a normal node labelled with a single wire. All edges originating from (resp. pointing towards) the original nodes now originate in (resp. point to) the new supernode. The two edges forming the local wormhole now have the same extremities and the same box attribute, so we remove one of them. See Fig. 9 for an illustration. The underlying idea is that all wires inside of a supernode are known to be in relation by $\equiv$. Our algorithm consists in iterating this graph rewriting process as long as possible<fnref n="1" />.

We now establish the main property of the process: wormholes can be contracted in any order, and at the end we get exactly the equivalence classes of $\equiv$.

<footnote n="1">¹ After a draft of this paper was written, we discovered that the same operation has been called “folding” in [15, 16, 17], in quite a different context—profinite topologies on a free group</footnote>
<figure><img src="image_20.png" /><figcaption>■ **Figure 9** Illustration of the graph contraction process. Edge labels in lower-case letters are arbitrary.</figcaption></figure>

The intuition behind this is that contracting a wormhole may create new wormholes but not destroy preexisting ones (other than the one being contracted, of course). This is because a wormhole requires two similarly-labelled edges pointing to the same node; contracting a wormhole can only bring together the endpoints of edges previously pointing to different nodes, not take them apart.

We formally establish the results using tools borrowed from the field of artificial intelligence automated reasoning (and more precisely, rewriting techniques for equational theories, see [5] for more details). Let $\rightsquigarrow$ be the binary relation on directed graphs that corresponds to the wormhole contraction process described above. It operates on graphs where edges are labelled by a (box, pin) pair, and where nodes are labelled with a set of wires. We have $G \rightsquigarrow G'$ if $G'$ can be obtained from $G$ by contracting a wormhole. In this case, $G'$ has one less vertex and one less edge than $G$. It follows that any *derivation* $G_0 \rightsquigarrow G_1 \rightsquigarrow \dots$ is finite. Let $\rightsquigarrow^*$ denote the reflexive-transitive closure of $\rightsquigarrow$. A graph $G$ is *reducible* if there is a $G'$ such that $G \rightsquigarrow G'$, and *irreducible* otherwise. When $G \rightsquigarrow G'$ and $G'$ is irreducible, then $G'$ is a *normal form of G*. In our case, normal forms are *unique*: if $G_0$ and $G_1$ are normal forms of $G$, then $G_0 = G_1$. The main ingredient to establish this is the following:

**Lemma 3.** *The $\rightsquigarrow$ relation is confluent: if $G \rightsquigarrow^* G_0$ and $G \rightsquigarrow^* G_1$, then there is a $G'$ such that $G_0 \rightsquigarrow^* G'$ and $G_1 \rightsquigarrow^* G'$.*

**Proof.** This follows from *strong confluence* and termination of $\rightsquigarrow$ by Newman's lemma (essentially, an induction on the number of steps of the derivations).

Therefore the problem is to prove strong confluence: if $G \rightsquigarrow G_0$ and $G \rightsquigarrow G_1$, then either $G_0 = G_1$ or there is a $G'$ such that $G_0 \rightsquigarrow G'$ and $G_1 \rightsquigarrow G'$. Suppose $G_0 \neq G_1$, so that there are two “contractible” wormholes in $G$: $\alpha \xrightarrow{X} \beta \xleftarrow{X} \gamma$ (leading to $G_0$) and $\phi \xrightarrow{Y} \chi \xleftarrow{Y} \psi$ (leading to $G_1$), with $\{\alpha, \gamma\} \neq \{\phi, \psi\}$.

If $\{\alpha, \gamma\} \cap \{\phi, \psi\} = \emptyset$, then after contracting $\alpha \xrightarrow{X} \beta \xleftarrow{\sim} \gamma$ (yielding $G_0$), there still exist two vertices labelled $\phi$ and $\psi$ in $G_0$, along with the two outgoing edges labelled $Y$ pointing to the same node $\chi'$ (even though $\chi'$ may not be labelled $\chi$ as in $G$ as a result of the contraction; in any case it is labelled with a superset of $\chi$). Contracting $\phi \xrightarrow{Y} \chi' \xleftarrow{Y} \psi$ is still possible in $G_0$ and yields $G'$, where $\alpha, \gamma, \phi$ and $\psi$ have been replaced by $\alpha \cup \gamma$ and $\psi \cup \phi$. The exact
same reasoning can be carried out starting from $G_1$ (contracting the other wormhole), with
the same conclusion.

if {$\alpha, \gamma$} $\cap$ {$\phi, \psi$} $\neq \emptyset$, then without loss of generality we may assume that $\phi = \gamma$. There are
thus two wormholes $\alpha \xrightarrow{X} \beta \xleftarrow{X} \gamma \xrightarrow{Y} \chi \xleftarrow{Y} \psi$. In that case, after contracting $\alpha \xrightarrow{X} \beta \xleftarrow{\gamma}$, we
see that the second wormhole has been modified: $\gamma \xrightarrow{Y} \chi \xleftarrow{Y} \psi$ in $G$ has been replaced by
$(\alpha \cup \gamma) \xrightarrow{Y} \chi' \xleftarrow{Y} \psi$ in $G_0$. But then, contracting the modified wormhole leads to $G'$, where
$\alpha, \gamma$ and $\psi$ have been replaced by a single vertex $\alpha \cup \gamma \cup \psi$. Again, the same reasoning can
be made starting from the other wormhole, yielding the same graph.

◀

**▶ Corollary 4.** Normal forms for $\rightsquigarrow$ are unique (and are obtained after a finite number of steps).

So, the non-determinism that appears when several wormholes coexist is not important.
Wormholes can be contracted in any order, and we always obtain the same result—a good
one.

**▶ Theorem 5.** Let $G$ be the dual representation graph of a recursive maze, and $G_{nf}$ a normal form of $G$ for $\rightsquigarrow$. Then the nodes of $G_{nf}$ are labelled by the equivalence classes of $\cong$.

This theorem follows from the two following lemmas, using the same notations as the theorem.

**▶ Lemma 6.** *Wires in a supernode of $G_{nf}$ are related by $\cong$.*

**Proof.** Consider a derivation $G = G_0 \rightsquigarrow G_1 \rightsquigarrow \dots \rightsquigarrow G_k = G_{nf}$ leading to the normal form.
The result is established by induction on $i$. When $i=0$, nodes of $G$ are labelled by singletons,
so the property trivially holds.

Next, suppose the property holds in $G_i$. The next graph $G_{i+1}$ is obtained by contracting a
wormhole $\Sigma \xrightarrow{X} \Theta \xleftarrow{X} \Pi$, thus “merging” $\Sigma$ and $\Pi$. The two edges forming the wormhole
existed in the original graph $G$: in $G$ there are $\alpha \xrightarrow{X} \beta$ and $\gamma \xrightarrow{X} \delta$, where $\alpha \in \Sigma$, $\beta, \gamma \in \Theta$
and $\delta \in \Pi$. By induction hypothesis, $\beta \cong^* \gamma$ (they both belong to the supernode $\Theta$). This
means that $\alpha \cong^* \delta$ (by definition of $\cong^*$). Now the fact that any pair $(\sigma, \pi) \in \Sigma \times \Pi$ are related
by $\cong^*$ follows from the transitivity of $\cong^*$ and from the induction hypothesis applied to $\Sigma$ and
$\Pi$.

◀

**▶ Lemma 7.** For any $i \ge 0$, if $\alpha \equiv_i \beta$, then $\alpha$ and $\beta$ belong to the same supernode in $G_{nf}$.

**Proof.** We prove the result by induction on $i$. When $i=0$, we need to show that wires
that are connected by a local wormhole in $G$ have been contracted in $G_{nf}$. Starting from $G$,
we first contract an arbitrary wormhole $\alpha \xrightarrow{X} \beta \xleftarrow{X} \gamma$, leading to $G_1$ ($G \rightsquigarrow G_1$). Then by
the confluence of $\rightsquigarrow$, we know that $G_1 \rightsquigarrow G'$. In other term, $\alpha$ and $\gamma$ belong to the same
supernode in $G_{nf}$. This is true for any wormhole initially present in $G$.

Next, suppose the result holds for $i \ge 0$, and take two wires $\alpha \equiv_{i+1} \beta$. Looking at the
definition of $\Gamma_{i+1}$, there are 3 cases to consider:

- $\alpha \equiv_i \beta$. In this case, the result directly holds by induction hypothesis.

- There is a wire $\gamma$ such that $\alpha \equiv_i \gamma$ and $\gamma \equiv_i \beta$. By induction hypothesis, $\alpha, \beta$ and $\gamma$ all belong to the same supernode.
- There are two wires $\gamma$ and $\delta$ and a box X such that $\alpha \xrightarrow{X} \gamma$, $\gamma \equiv_i \delta$ and $\delta \xleftarrow{X} \beta$. By induction hypothesis, $\gamma$ and $\delta$ belong to the same supernode (say $\Theta$) in $G_{nf}$. Suppose, for the sake of a contradiction that, in $G_{nf}$, $\alpha$ belongs to a supernode $\Sigma$ and that $\beta$ belongs to a different supernode $\Pi$. Then the two edges $\alpha \xrightarrow{X} \gamma$ and $\beta \xrightarrow{X} \delta$ of G have not been removed in $G_{nf}$, but were modified to become $\Sigma \xrightarrow{X} \Theta \xleftarrow{X} \Pi$. Therefore, there is a contractible wormhole in $G_{nf}$, which contradicts the irreducibly of $G_{nf}$.

<figure><img src="image_21.png" /></figure>

We now discuss the implications of theorem 5. Starting from the dual representation graph of a maze, run the contraction process until a normal form has been obtained. To check if it is possible to exit the maze, it is sufficient to examine the wires in the equivalence class of the starting point, and test if one of them is connected to an outer IO pin. When it is the case, an exit path can be built explicitly (but how to do so depends on implementation details discussed below).

## 9 Efficient deterministic implementations

We now discuss the efficient implementation of the graph rewriting process discussed above. We assume that everything is represented as word-sized integers: wires are numbered from 0 to $W-1$, boxes are numbered from 0 to $B-1$, etc. The input is the dual representation graph, provided as adjacency lists, i.e. as an array $G$ such that $G[\omega]$ is the (linked) list of edges coming out of node $\omega$. The edge $\alpha \xrightarrow{X,i} \beta$ is represented by the triplet $(X, i, \beta)$, where the endpoint is explicit and the starting point is implicit. We therefore define the “type” `edge ::= box × pin × wire` (these are actually 3 integers, but this spells out their purpose more explicitly). The graph is therefore provided as an `edge list array`, where the edges coming out of wire $\omega$ are given in $G[\omega]$.

Tuples, also known as records or `struct`, can be (de)constructed in constant time. We make abundant use of `blockchains` linked lists, and we employ the following notations:

- `[]` denotes the empty list (a `NULL` pointer).

- $L \leftarrow head :: tail$ denotes the operation that constructs a new linked $L$ list whose first element is `head`, followed by the linked list `tail` (this means that a new cell must be acquired, `head` must be copied into it, and a pointer to `tail` must also be stored).

- `head :: tail ← L` denotes the “deconstruction” operation: it fetches the data item `head` contained in the first entry of the list, and grabs a pointer `tail` to the remaining items.

(De)constructing a list runs in constant time, and so does accessing any location in an array. The observant reader may have noticed that our notations are inspired from functional languages from the ML family.

We keep a list (`pending`) of wormholes awaiting contraction, and process them one at a time, adding newly discovered wormholes to the list. We must however navigate around two problems:

1. The same pair of wires can be merged by two (or more) wormholes (as shown in Fig. 10, left). In our implementation, the pending list may contain several wormholes merging the same pair of nodes.
<figure><img src="image_22.png" /><figcaption>■ **Figure 10** Two wires can be merged by several wormholes (left). There can be a quadratic number of wormholes (right).</figcaption></figure>

2. The number of wormholes can be quadratic in the size of the maze, even if it has only $E = O(W)$ edges (see Fig. 10, right). However, not all of them can be collapsed: some will vanish into thin air when *others* are collapsed.

When processing the next wormhole, we check if the two wires have already been merged and only proceed when it is not the case (this solves the first problem).

When a wormhole $\alpha \xrightarrow{X.i} \beta \xleftarrow{X.j} \gamma$ is discovered and added to the list, we immediately remove one of the two edges from the graph—they would become identical later when the wormhole actually gets contracted and one of them would be removed anyway, so why delay the inevitable? With this modification, only *E* wormholes can be added to the list. We implement this as follows: we look at each edge of the initial graph in sequence: either it creates a wormhole with another “hot” edge (we register the wormhole and original the edge is sucked into the void), or it does not (we mark the edge as hot).

Inside each supernode, one node is chosen as “supernode leader”. The supernode is hosted by the leader node in the original graph. Nodes that have been merged into larger supernode are not actually removed from the graph ; they remain there but become *followers* (as opposed to their leader).

When two (super)nodes are merged, to form the resulting supernode, one of them is “absorbed” into the other one. Hot edges pointing to the absorbee either create a wormhole and are dropped, or become hot edges pointing to the absorber. The actual issue is to detect the new wormholes that are created by the displacement of edges.

A major difference with the process suggested by Fig. 9 is that we only move the targets of edges, not their origins. This does not affect the process, at least not until an actual exit path has to be constructed. This issue is discussed in section 10.

**9.1 Dense mazes**

We first describe a simple implementation tailored for the case of *dense* mazes, where $E \approx WB$. We use a **hot** array of dimension $W \times B$ such that **hot**[$\beta$, $X$] is either **none** or **some**($\alpha$, $i$), in which case there is a “hot” edge $\alpha \xrightarrow{X.i} \beta$ in the graph.

When the algorithm starts, each node in the graph corresponds to a wire of the maze. Then nodes will be merged into supernodes. Maintaining the content of supernodes is a once-in-a-lifetime chance for us to use the celebrated “inverse-Ackermann” disjoint-set data structure (also known as UNION-FIND). This uses the two arrays parent and rank.
The pseudo-code of our solution is shown as Algorithm 1. We believe that it is simple enough to be implemented in assembler by a motivated undergraduate student. Its step-by-step execution on the simple maze of Fig. 7 is shown in Fig. 11. When it terminates, equivalence classes of $\equiv^*$ have been determined. This easily allows to test if the maze can be exited.

It is clear that ADDEdge runs in constant time, and that MERGE runs in $O(B)$ operations. The setup phase of COLLAPSEMAZE requires $O(WB + E)$ operations. The number of iterations of the while loop is at most $E$ (each new wormhole added to pending destroys an edge). MERGE can only be invoked $W-1$ times. So the total time spent in MERGE is $O(BW)$ and the total time spent in calls to FIND is $O(E\alpha(W))$, where $\alpha$ is the inverse-Ackermann function (thanks to the celebrated amortized analysis of [18]). Note that $\alpha(W)$ is upper-bounded by 4 when its $W$ is less than the number of atoms in the universe. So, the final complexity of COLLAPSEMAZEDENSE is $O(BW + E\alpha(W))$.

$E \approx W^2$ and $W \approx B$, then this gives a nearly-quadratic algorithm, improving upon the known cubic one.

## 9.2 Sparse mazes

When $E$ is much less than $BW$, several aspects of the algorithm could be made more efficient. For instance, MERGE requires $B$ operations to inspect $B$ potential edges, even if just a few are present. We can use a lightweight variant of the “sparse array” technique abundantly used in very early sparse matrix codes and rediscovered 20 years later [3] in a different context. To efficiently iterate on the hot incoming edges to a node, we also use an auxiliary array hotbox where hotbox[$\omega$] contains a list of $X$'s such that hot[$\omega$, X] $\neq$ none.

Also, when merging two nodes, we could absorb the “smaller” one (with less edges to process) into the “larger” one. Doing all the work on the smaller of the two nodes minimizes the total amount of work (this idea is common; for instance it is at work in Hopcroft’s DFA minimization algorithm [9]). Unfortunately, this breaks down the guarantees offered by the disjoint set data structure. We therefore make do with a more naive solution: we eagerly update all nodes when two sets are joined.

All nodes have a pointer (leader) to the leader node in their supernode (possibly themselves). Supernode leaders have a list (followers) of nodes in their supernode. The size of a (super)node is the number of nodes it contains plus the number of incoming edges. The algorithm maintains the sizes at all time (in an array size), as new wormholes are discovered and (super)nodes are merged. When two (super)nodes are merged, to form the resulting supernode, the smaller one (by size) is “absorbed” into the larger one. More precisely:

- The leader pointer of all nodes in the smaller (super)node is set to the larger supernode.

- Hot edges pointing to the smaller supernode either create a wormhole and are dropped, or become hot edges pointing to the larger supernode.

- The size of the larger supernode is augmented accordingly.

ADDEdge still runs in constant time, and MERGE runs in time dominated by the size of the smaller supernode: it takes constant-time per wire in the smaller supernode, plus constant time per hot edge pointing to the smaller supernode (thanks to the hotbox array)—and not all edges are hot, hence the upper-bound.

The number of iterations of the while loop is again at most $E$ and it does a constant number
<caption>■ Algorithm 1 Algorithm to collapse dense recursive mazes.</caption>

1: function FIND($\alpha$)
2:   if parent[$\alpha$] $\neq$ $\alpha$ then
3:     parent[$\alpha$] $\leftarrow$ FIND(parent[$\alpha$])
4:   return parent[$\alpha$]
5: procedure ADDEDGE($\alpha$, X, $i, \beta$)
6:   if hot[$\beta$, X] = some($\gamma, j$) then
7:     pending $\leftarrow$ ($\alpha, X, i, \beta, j, \gamma$) :: pending
8:     else
9:     hot[$\beta$, X] $\leftarrow$ some($\alpha, i$)
10:    procedure MERGE($\sigma, \pi$)
11:     if rank[$\pi$] < rank[$\sigma$] then
12:      tmp $\leftarrow$ $\pi$, $\pi$ $\leftarrow$ $\sigma$, $\sigma$ $\leftarrow$ tmp
13:     parent[$\sigma$] = $\pi$
14:     if rank[$\sigma$] = rank[$\pi$] then
15:      increment rank[$\pi$]
16:     for $0 \le X < B$ do
17:       if hot[$\sigma, X$] $\neq$ none then
18:         some($\omega, i$) $\leftarrow$ hot[$\sigma, X$]
19:         ADDEDGE($\omega, X, i, \pi$)
20:    procedure COLLAPSEMAZEDENSE($W, B, G$)
21:     pending $\leftarrow$ []
22:     for $0 \le \alpha < W$ do
23:       parent[$\alpha$] $\leftarrow$ $\alpha$
24:       rank[$\alpha$] $\leftarrow$ 0
25:     for $0 \le X < B$ do
26:       hot[$\alpha, X$] $\leftarrow$ none
27:     for each ($X, i, \beta$) in $G$[$\alpha$] do
28:       ADDEDGE($\alpha, X, i, \beta$)
29:     while pending $\neq$ [] do
30:       ($\alpha, X, i, \beta, j, \gamma$) :: tail $\leftarrow$ pending
31:     pending $\leftarrow$ tail
32:     $\sigma$ $\leftarrow$ FIND($\alpha$)
33:     $\pi$ $\leftarrow$ FIND($\gamma$)
34:     if $\sigma \neq \pi$ then
35:       MERGE($\sigma, \pi$)

▷ path compression

▷ detected $\alpha \xrightarrow{X.i} \beta \xleftarrow{X.j} \gamma$

▷ UNION

▷ Union-by-rank: $\sigma$ is absorbed in $\pi$

▷ Transfer hot edges

▷ looking at $\omega \xrightarrow{X.i} \sigma$

▷ replace by $\omega \xrightarrow{X.i} \pi$

▷ Setup

▷ $\alpha$ is a supernode by itself

▷ prime the wormhole pump

▷ main loop : process known wormholes

▷ popped $\alpha \xrightarrow{X.i} \beta \xleftarrow{X.j} \gamma$

▷ already merged?

▷ merge nodes containing $\alpha$ and $\gamma$
<figure><img src="image_23.png" /></figure>

original graph

<figure><img src="image_24.png" /></figure>

pending:

$$\gamma \xrightarrow{C} \delta \leftarrow C \delta$$

$$\beta \xrightarrow{B} \gamma \leftarrow B \zeta$$

before the main loop

<figure><img src="image_25.png" /></figure>

pending:

$$\gamma \xrightarrow{C} \delta \leftarrow C \delta$$

$$\beta \xrightarrow{B} \gamma \leftarrow B \zeta$$

<figure><img src="image_26.png" /></figure>

pending:

$$\gamma \xrightarrow{C} \delta \leftarrow C \delta$$

$$\beta \xrightarrow{B} \gamma \leftarrow B \zeta$$

$$\zeta \xrightarrow{D} \gamma \leftarrow D \gamma$$

<figure><img src="image_27.png" /></figure>

pending:

$$\beta \xrightarrow{B} \gamma \leftarrow B \zeta$$

$$\gamma \xrightarrow{C} \delta \leftarrow C \delta$$

$$\zeta \xrightarrow{D} \gamma \leftarrow D \gamma$$

$$\alpha \xrightarrow{A} \gamma \leftarrow A \delta$$

<figure><img src="image_28.png" /></figure>

pending:

$$\beta \xrightarrow{B} \gamma \leftarrow B \zeta$$

$$\gamma \xrightarrow{C} \delta \leftarrow C \delta$$

$$\zeta \xrightarrow{D} \gamma \leftarrow D \gamma$$

$$\alpha \xrightarrow{A} \gamma \leftarrow A \delta$$

<caption>■ **Figure 11** Step-by-step illustration of Algorithm 1. The plain edges are “hot”. The dotted edges represent the supernode leaders (for non-trivial supernodes).</caption>
of operation per iteration, excluding calls to MERGE. It thus remains to control the total time spent in MERGE—and this is the tricky part. As the algorithm progresses, the sequence of merges can be represented by a binary forest. The wires of the maze are the leaves, and each call to MERGE creates a new root whose two children are preexisting roots. It represents a new supernode containing all the wires associated to the leaves in the subtree. Each supernode is labelled by its size (as defined above). When two roots of labels $x \le y$ are joined, the result has label $x + y$, and we are “charged” $x$ operations (the smaller size).

In the example detailed in Fig. 11, this forest is in fact a binary tree:

<figure><img src="image_29.png" /></figure>

Let $\mathcal{F}$ denote an arbitrary merge forest built from the dual representation graph of a recursive maze. Its $W$ leaves are labelled with the size of the wires (one plus the number of incoming edges). Let $S$ denote the sum of sizes: if the dual representation graph has $E$ edges, then $S \le W + E$. Let $C(\mathcal{F})$ denote the total amount “charged” by this merge forest (i.e., an upper-bound on the total number of operations spent in MERGE during the process). Then we have:

**Lemma 8.** $C(\mathcal{F}) \le S \log_2 S$.

**Proof.** Let $t_\omega$ denote the number of times the supernode containing wire $\omega$ is absorbed into a larger supernode in $\mathcal{F}$ (this counts the number of times $\omega$ belongs to the smallest of two sets being joined). By definition,

$$C(\mathcal{F}) \le \sum_{\omega \in W} \text{size}[\omega] \times t_{\omega}.$$

Our plan is to upper-bound the $t_\omega$'s. Because of the union-by-size rule, each time the supernode containing $\omega$ is the smaller of the two, the size of new supernode created by the merge is at least twice as large. If follows that the root containing $\omega$ must have size at least $\text{size}[\omega]2^{t_\omega}$. Because this cannot be greater than $S$, it follows that $t_\omega \le \log_2(S/\text{size}[\omega])$. We conclude that

$$C(\mathcal{F}) \le \sum_{\omega \in W} \text{size}[\omega] \times \log_2 \frac{E}{\text{size}[\omega]}$$

and the lemma is proved because $S = \sum_{\omega} \text{size}[\omega]$.

<figure><img src="image_30.png" /></figure>

Therefore, the total running time of COLLAPSEMAZESPARSE is $O(BW + E \log E)$. At first glance, this could seem like a *decremental* improvement compared to COLLAPSEMAZEDENSE. However, the *only* part that requires BW operations is the initialization of the hot array. We therefore see two ways to cheat our way out of this embarrassing situation.
- We initially need the **hot** array to be filled with the **none** value. If the array was *provided* to us in this state, then everything would be perfect. **COLLAPSEMAZESPARSE** would run in time $O(E \log E)$, mission accomplished. And although this is a bit cheating, it is not too bad because we could easily *restore* the **hot** array to its initial state with only a constant factor increase in the running time (just store the indices of all modified locations and restore them to **none** at the end of the algorithm).

It follows that if a long sequence of mazes had to be solved in sequence, then a single (large enough) **hot** array could be initialized *once* and used several times, so the cost of its initialization could be amortized over an (arbitrarily long) sequence of uses.

- Initializing the **hot** array annoys us. We could simply get rid of it and use a hash table instead. It will ever only hold *E* entries, and we have a time budget to initialize an array of size *E* log *E*, so that we can keep the fill ratio of this hash table comfortably low. However, this requires some kind of randomization and we leave it as an open problem.

## 10 Construction of an exit path

All wires in an equivalence class of $\equiv^*$ are mutually reachable (without modifying the stack). In this section we show how to augment Algorithms 1 and 2 to provide the computation of such paths without asymptotically increasing their complexity.

In dual representation graph, an edge $\alpha \xrightarrow{X.i} \beta$ is labelled with an instruction ("X.i"). This describes a feasible move in the maze (and a valid transition in the pushdown automaton that pushes X).

We extend this as follows: each edge is labelled with a *box attribute* (*X*—what recursive box is entered by taking this edge) and the *identifier of an instruction sequence* (that describes what must be done to actually cross the edge). We write these identifier with a “sharp” (e.g. \#42). There is also a global *context* that maps instruction sequence identifiers to actual sequences of instructions and instruction sequence identifiers. This time, an edge $\alpha \xrightarrow{X} \beta$ means that the sequence of instruction \#42 takes the player from wire $\alpha$ to wire $\beta$, while entering box *X*. So, before the graph rewriting process even start, we transform the dual representation graph into the *extended dual representation graph* shown in Fig. 12.

We then perform the same graph rewriting process, except that we now take care of instruction sequence identifiers as shown in Fig. 13. All the edges incident to the supernode that gets “absorbed” gets a new instruction sequence identifier. In the figure, the sequence of instruction \#K := $\overline{I}; \overline{J}$ travels from $\alpha$ to $\gamma$. Edges incoming into $\alpha$ are now incoming into $\gamma$, therefore \#K must be added after their instruction sequence. Edges pointing out of $\alpha$ now point out of $\gamma$, so \#K must be added before their instruction sequence. We finally record the “spanning” edge $\alpha \xrightarrow{\#K} \gamma$.

We the rewriting process is over, the spanning edge form (rooted) spanning trees of the connected components. Therefore, when a pair of nodes are reachable by a path, this path can be assembled by following the spanning edges.

Compared to Algorithms 1 and 2, this requires the following modifications:

- Not only the target, but also the origin of hot edges incident to an “absorbed” node must be modified. This requires each node to be aware not only of its incoming hot edges, but also of the outgoing ones.
<figure><img src="image_31.png" /><figcaption>**Figure 12** Extended dual representation graph corresponding to the simple maze of Fig. 7.</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>**Figure 13** Illustration of the extended graph contraction process (showing only instruction sequence identifiers). The two thick edges have the same box attribute. It modifies the labels of all edges incident to $\alpha$ and registers one new instruction sequence identifier for each one.</figcaption></figure>
■ The instruction sequences on each edge must be maintained.

■ When a wormhole $\alpha \xrightarrow[\#I]{X} \beta \xleftarrow[\#J]{X} \gamma$ is discovered, one of the two edges is removed from the graph, but its instruction sequence identifier must not be lost (otherwise we will not be able to form the spanning edge). Therefore, $(\alpha, X, \#I, \beta, \#J, \gamma)$ must be pushed onto the pending list.

■ Spanning edges must be stored separately.

Fig. 14 illustrates the process. In the end, this produces the path #18, that expands as:

$$ \begin{aligned} \#18 &= \#16; \overline{\#14} \\ &= (A.4; \#15); (\overline{A.2}; \#11) \\ &= A.4; (\#12; \overline{D.1}); \overline{A.2}; (C.5; \overline{C.3}); \\ &= A.4; (\#10; \#11); \overline{D.1}; \overline{A.2}; C.5; \overline{C.3} \\ &= A.4; (\overline{\#9}; D.3); (C.5; \overline{C.3}); \overline{D.1}; \overline{A.2}; C.5; \overline{C.3} \\ &= A.4; B.1; \overline{B.2}; D.3; C.5; \overline{C.3}; \overline{D.1}; \overline{A.2}; C.5; \overline{C.3} \end{aligned} $$

This is indeed an exit path, but not one of optimal length (compare to the one given earlier in the text). Note that exponentially-long paths can be represented in polynomial space by the list of instruction sequence identifiers.

We leave the problem of producing a minimal-length exit path open for future work.

## 11 Conclusion: a daunting open problem

Checking if a context-free language is empty is non only decidable, but can be done in polynomial time. For this reason, it was clear from the outset that recursive mazes could not pose a major computational problem.

However, checking emptiness of the intersection of two context-free languages is undecidable (this enables the simulation of an arbitrary Turing machine). Therefore, it could very well be that trying to get out of two recursive mazes simultaneously might be difficult. This problem can be thought of as follows: suppose you have an application to play recursive mazes (\begin{shameless-advertisement} such as the one we designed, available at https://github.com/orelcosseron/Fractal-Maze-Python\end{shameless-advertisement}). In such a game, the mazes are orthogonal: paths are either horizontal or vertical. The player controls the location of a sprite using arrow keys, as is common in “top down” adventure games, such as *The Legend of Zelda*. Moving towards a wall does nothing: the sprite cannot cross the wall.

Now suppose that two instances of the application are launched, with two different mazes, and that both applications receive the same keyboard inputs (see Fig. 15). In the situation shown in the figure, going down does nothing; going up moves the sprite in the right maze; going left moves the sprite in the left maze; going right moves the sprite in both mazes. Given the geometric description of two mazes, the question is to decide if there is a (finite) sequence of keyboard inputs that exits both mazes.

It is not completely obvious that this problem is even decidable (we may get away with it because of the severe restrictions on the class of context-free languages associated to recursive mazes). In any case, this is an exciting perspective for future work.
<figure><img src="image_33.png" /><figcaption>Figure 14 Step-by-step illustration of the construction of an exit path. The plain edges are “hot”. The dotted edges represent are the extra spanning edges).</figcaption></figure>
<figure><img src="image_34.png" /><figcaption>■ **Figure 15** Solving two mazes at the same time—with a single keyboard. Is it decidable? The player is represented by a blue dot, and its current path is shown by a blue or red line.</figcaption></figure>

References

1. Rajeev Alur and P. Madhusudan. Adding nesting structure to words. *J. ACM*, 56(3), May 2009. doi:10.1145/1516512.1516518.

2. Ahmed Bouajjani, Javier Esparza, and Oded Maler. Reachability analysis of pushdown automata: Application to model-checking. In Antoni W. Mazurkiewicz and Józef Winkowski, editors, *CONCUR '97: Concurrency Theory, 8th International Conference, Warsaw, Poland, July 1-4, 1997, Proceedings*, volume 1243 of *Lecture Notes in Computer Science*, pages 135–150. Springer, 1997. doi:10.1007/3-540-63141-0\_10.

3. Preston Briggs and Linda Torczon. An efficient representation for sparse sets. *ACM Lett. Program. Lang. Syst.*, 2(1-4):59–69, March 1993. doi:10.1145/176454.176484.

4. N. Chomsky and M.P. Schützenberger. The algebraic theory of context-free languages. In P. Braffort and D. Hirschberg, editors, *Computer Programming and Formal Systems*, volume 26 of *Studies in Logic and the Foundations of Mathematics*, pages 118–161. Elsevier, 1959. URL: https://www.sciencedirect.com/science/article/pii/S0049237X09701041, doi:10.1016/S0049-237X(09)70104-1.

5. Nachum Dershowitz and David A. Plaisted. Rewriting. In John Alan Robinson and Andrei Voronkov, editors, *Handbook of Automated Reasoning (in 2 volumes)*, pages 535–610. Elsevier and MIT Press, 2001. URL: https://doi.org/10.1016/b978-044450813-3/50011-4, doi:10.1016/B978-044450813-3/50011-4.

6. Evan Driscoll, Aditya Thakur, and Thomas Reps. Opennwa: a nested-word automaton library. In *Proceedings of the 24th International Conference on Computer Aided Verification*, CAV'12, page 665–671, Berlin, Heidelberg, 2012. Springer-Verlag. doi:10.1007/978-3-642-31424-7_47.

7. Alain Finkel, Bernard Willems, and Pierre Wolper. A direct symbolic approach to model checking pushdown systems. In Faron Moller, editor, *Second International Workshop on Verification of Infinite State Systems, Infinity 1997, Bologna, Italy, July 11-12, 1997*, volume 9 of *Electronic Notes in Theoretical Computer Science*, pages 27–37. Elsevier, 1997. doi:10.1016/S1571-0661(05)80426-8.
8 John R Gilbert, Xiaoye S Li, Esmond G Ng, and Barry W Peyton. Computing row and column counts for sparse qr and lu factorization. *BIT Numerical Mathematics*, 41(4), 12 2000. URL: https://www.osti.gov/biblio/834431, doi:10.1023/A:1021943902025.

9 John E. Hopcroft. An $n \log n$ algorithm for minimizing states in a finite automaton. In Zvi Kohavi and Azaria Paz, editors, *Theory of Machines and Computations*, pages 189–196. Academic Press, New York, NY, 1971. doi:10.1016/B978-0-12-417750-5.50022-1.

10 Peter Gjøl Jensen, Stefan Schmid, Morten Konggaard Schou, and Jirí Srba. PDAAAL: A library for reachability analysis of weighted pushdown systems. In Ahmed Bouajjani, Lukás Holík, and Zhilin Wu, editors, *Automated Technology for Verification and Analysis - 20th International Symposium, ATVA 2022, Virtual Event, October 25-28, 2022, Proceedings*, volume 13505 of *Lecture Notes in Computer Science*, pages 225–230. Springer, 2022. doi:10.1007/978-3-031-19992-9\_14.

11 David R. Karger. Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm. In Vijaya Ramachandran, editor, *Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms*, 25-27 January 1993, Austin, Texas, USA, pages 21–30. ACM/SIAM, 1993. URL: http://dl.acm.org/citation.cfm?id=313559.313605.

12 Donald E. Knuth. *Seminumerical Algorithms*, volume 2 of *The Art of Computer Programming*. Addison-Wesley, Reading, Massachusetts, second edition, 10 January 1998.

13 Martin Kutrib, Andreas Malcher, and Christian Schneider. Finite automata with undirected state graphs. *Acta Informatica*, 59(1):163–181, 2022. URL: https://doi.org/10.1007/s00236-021-00402-0, doi:10.1007/S00236-021-00402-0.

14 Stefan Schwoon. *Model checking pushdown systems*. PhD thesis, Technical University Munich, Germany, 2002. URL: http://tumb1.biblio.tu-muenchen.de/publ/diss/in/2002/schwoon.html.

15 John R. Stallings. Topology of finite graphs. *Inventiones mathematicae*, 71(3):551–565, 1983. doi:10.1007/BF02095993.

16 Benjamin Steinberg. Finite state automata: A geometric approach. *Transactions of the American Mathematical Society*, 353(9):3409–3464, 2001. URL: http://www.jstor.org/stable/2693797.

17 Benjamin Steinberg. Inverse automata and profinite topologies on a free group. *Journal of Pure and Applied Algebra*, 167(2):341–359, 2002. URL: https://www.sciencedirect.com/science/article/pii/S0022404901000305, doi:10.1016/S0022-4049(01)00030-5.

18 Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. *J. ACM*, 31(2):245–281, March 1984. doi:10.1145/62.2160.

19 Mark J. P. Wolf. *101 Enigmatic Puzzles — Fractal Mazes, Quantum Chess, Anagram Sudoku, and More*. BookBaby, 2020.

## A Bonus material: the $\lambda$-maze

Start from a context-free grammar describing the syntax of everyone's favorite programming language: the pure lambda-calculus. Here in Backus-Naur form:

$$L ::= \lambda x.L|x|(L)|LL$$

To generate a recursive maze from this, we basically compute the Chomsky-Schützenberger representation of $L$. To this goal, we introduce several pairs of matching symbols $(a$ and $\bar{a}$, $b$
and $\bar{b}$, etc.). We modify the language to wrap each occurrence of a non-terminal between fresh matching symbols.

$$L' \to aL'\bar{a} \qquad (1)$$

$$L' \to x\bar{x} \qquad (2)$$

$$L' \to cL'\bar{c} \qquad (3)$$

$$L' \to dL'\bar{d} \qquad (4)$$

We also define an erasing homomorphism $h$ such that $h(\omega)$ is the empty string, except for:

$$h(a) = \lambda x.$$

$$h(x) = x.$$

$$h(c) = ($$

$$h(\bar{c}) =).$$

The goal is that $L = h(L')$, and $L'$ is made of ensure that it is made of well-nested words ($L'$ is contained in a Dyck language). Next, we describe a finite automaton describing the allowed sequencing of symbols in $L'$. It has two states per non-terminal in the grammar, here $L_{in}$ and $L_{out}$. Intuitively, $L_{in}$ in the state we are in before starting to read a string generated by the non-terminal $L'$, while $L_{out}$ is the state we are in when it is done. The initial state is $L_{in}$, and the accepting state is $L_{out}$. There is also an extra state per pair of adjacent terminal symbols in the productions of $L'$.

<figure><img src="image_35.png" /></figure>

To turn this into the dual representation graph of a maze: replace $q \xrightarrow{\bar{u}} q'$ by $q \leftarrow \bar{u} q'$, and add an extra symbol for the start and the end (pushed when the game starts, popped only at the end to exit the maze).

<figure><img src="image_36.png" /></figure>

Language of reduced words?