MIDTERM Is a Deterministic Technique to Exit Recursive Mazes

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¹¹1For instance https://amurielagi.github.io/fractal-maze/ or [shameless advertisement] https://orelcosseron.github.io/fractal-maze/..

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 boxes are often distinguished with capital letters. There are also special locations, such as $\oplus$ and $\ominus$ 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 $\ominus$ to $\oplus$ 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:

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.

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 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 $\oplus$ starting from $\ominus$), 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.

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. 6).

After presenting some context, we review in section 4 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 $𝒪\left(W^{2}EB\right)$. In section 5, we review improved algorithms to decide reachability of arbitrary states in pushdown automata, that yield a faster decision procedure with complexity $𝒪\left({𝒲}^3\right)$. Finally, in section 6 we discuss a new algorithmic technique to compute equivalence classes of wires inside a recursive maze. In section 7 we discuss the efficient implementation of this procedure, and show a version that terminates in time $𝒪\left(WB+E\alpha (W)\right)$, where $\alpha$ is the inverse-Ackermann function, improving the state of the art. We discuss how to bring this down to $𝒪\left(E\log E\right)$, but this seems to either require: a) cheating, or b) randomization. Lastly, in section 8, 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. $𝒪\left(W+E+B\right)$ is left as an intriguing open problem.

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. 6 are:

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. 6, right): it is a directed graph whose nodes are the wires of the maze, and where there is a directed edge $\alpha \stackrel{X.i}{\to }\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:

• $\mathrm{■}$

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

• $\mathrm{■}$

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

• $\mathrm{■}$

  Then, for each wire $\varphi$, do:

  • –

    For each inner pin $X.i$ in $\varphi$, add an edge labelled by $X.i$ from $\varphi$ 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 \stackrel{X.i}{\to }\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$.

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 the simple maze of Fig. 6 (that presumably exits):

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: $\overline{A.4;B.1;\overline{B.2}}=B.2;\overline{B.1};\overline{A.4}$. Applying a sequence of legal instructions then its mirror is a no-op.

There is a way to efficiently check if a sequence of instructions is valid, i.e. if the desired moves are actually feasible. The validity of a move depends on the last box that was entered (for instance $\overline{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 “$\frac{\text{wire}}{\text{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 $\varphi \stackrel{X.i}{\to }\psi$ in the dual representation of the maze, then the player may move between positions $\varphi |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 $𝒫$ (think $1,\mathrm{\dots },n$), the set of recursive boxes is $ℬ$ (think $\perp ,A,B,C,\mathrm{\dots }$) and the set of wires is $𝒲$ (think $\alpha ,\beta ,\mathrm{\dots }$).

• $\mathrm{■}$

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

• $\mathrm{■}$

  The input alphabet is $\mathrm{\Sigma }:=ℬ\times 𝒫\cup \overline{ℬ\times 𝒫}$.

• $\mathrm{■}$

  The stack alphabet is $\mathrm{\Lambda }:=ℬ$.

• $\mathrm{■}$

  The start state is a designated wire $\alpha \in 𝒲$ (part of the specification of the maze).

• $\mathrm{■}$

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

• $\mathrm{■}$

  The transition function $f:Q\times \mathrm{\Sigma }\times \mathrm{\Lambda }\to Q\times {\mathrm{\Lambda }}^{\ast }$ is defined as follows. For every edge $\varphi \stackrel{X.i}{\to }\psi$ in the dual representation graph and for any box $Y\in ℬ$, $f(\varphi ,X.i,Y)=(\psi ,XY)$ and $f(\psi ,\overline{X.i},X)=(\varphi ,\mathrm{\varnothing })$. If the goal is to exit the maze, additionally set $f(\omega ,\text{done},\perp )=(\text{goal},\mathrm{\varnothing })$ 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},\mathrm{\varnothing })$.

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. 6 (that exits the maze):

${\displaystyle \frac{\alpha }{\perp }}\stackrel{A.4}{\to }{\displaystyle \frac{\beta }{A\perp }}\stackrel{B.1}{\to }{\displaystyle \frac{\gamma }{BA\perp }}\stackrel{\overline{B.2}}{\to }{\displaystyle \frac{ϵ}{A\perp }}\stackrel{D.3}{\to }{\displaystyle \frac{\delta }{DA\perp }}\stackrel{C.5}{\to }{\displaystyle \frac{\delta }{CDA\perp }}\stackrel{\overline{C.3}}{\to }{\displaystyle \frac{\gamma }{DA\perp }}\stackrel{\overline{D.1}}{\to }{\displaystyle \frac{\gamma }{A\perp }}\stackrel{\overline{A.2}}{\to }{\displaystyle \frac{\delta }{\perp }}\stackrel{\text{done}}{\to }{\displaystyle \frac{\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 [8] or PDAAAL [6] (just to mention a few) that can therefore be used to solve 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 𝒲$ and $X\in ℬ$. Intuitively, $[\alpha X\beta ]$ is the set of sequences 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$.

• $\mathrm{■}$

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

Then for each edge $\varphi \stackrel{X.i}{\to }\psi$ in the dual representation of the maze:

• $\mathrm{■}$

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

• $\mathrm{■}$

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

So, there are $B{W}^2$ non-terminals, and $1+B{W}^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 $𝒪\left(W^{2}EB\right)$.

There is a more efficient technique that can be better suited to laaaaaaaaaaaarge recursive mazes. It is heavily inspired by algorithms designed almost simultaneously by Bouajjani, Esparza and Maler [1] on the one hand and Finkel, Willems and Wolper [3] on the other hand. These algorithms 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 \stackrel{X.i}{\to }\beta \stackrel{X.j}{\leftarrow }\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 \stackrel{X.i}{\to }\beta \stackrel{X.j}{\leftarrow }\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:

The sequence ${\mathrm{\Gamma }}_i$ is increasing (with respect to set inclusion) and upper-bounded by $𝒲\times 𝒲$, therefore it converges (in a finite number of steps) to a limit denoted as ${\mathrm{\Gamma }}_{\mathrm{\infty }}$. We write $\alpha {\equiv }_i\beta$ (resp. $\alpha \stackrel{\ast }{\equiv }\beta$) as syntactic sugar for $(\alpha ,\beta )\in {\mathrm{\Gamma }}_i$ (resp. ${\mathrm{\Gamma }}_{\mathrm{\infty }}$).

The main contribution of this paper is that, in the case of recursive mazes, it is possible to do better than [1, 3]. Our starting point is that the reversible nature of all movements makes it possible to exploit equivalence classes of wires. If $\alpha \stackrel{\ast }{\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 [1, 3] 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^{\prime }$ that leaves the stack unchanged, while there might not be a sequence of transitions from $q^{\prime }$ to $q$ that leaves the stack unchanged. In recursive mazes, we now that the latter exists.

On this occasion, we cannot resist the urge of a little digression. 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 mentioned in section 3 – 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).

Back to the problem at hand, this makes it possible for us, instead of explicitly building a clique between equivalent wires as in [1, 3], to build a (much smaller) spanning tree: this preserves reachability properties. The same technique is used in the context of sparse matrix factorization [4] 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 [7]. The core idea of our proposal is simple: when a local wormhole $\alpha \stackrel{X.i}{\to }\beta \stackrel{X.j}{\leftarrow }\gamma$ is identified, we add an edge 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 add 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. 7 for an illustration. The underlying idea is that all wires inside of a supernode are known to be in relation by $\stackrel{\ast }{\equiv }$. Our algorithm consists in iterating this graph rewriting process as long as possible.

After a draft of this paper was written, we discovered that the same operation has been called “folding” in [9, 10, 11], in quite a different context – profinite topologies on a free group, if you can believe it. The main properties of this process have already been proved in these works, and because of space constraints we will not repeat them: wormholes can be contracted in any order, and at the end we get exactly the equivalence classes of $\stackrel{\ast }{\equiv }$. 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.

Starting from the dual representation graph of a maze, we run the contraction process until death ensues. 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).

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 $\text{G}[\omega ]$ is the (linked) list of edges coming out of node $\omega$. The edge $\alpha \stackrel{X.i}{\to }\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” $\text{edge}::=\text{box}\times \text{pin}\times \text{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 $\text{G}[\omega ]$.

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

• $\mathrm{■}$

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

• $\mathrm{■}$

  $L\leftarrow \text{head}::\text{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).

• $\mathrm{■}$

  $\text{head}::\text{tail}\leftarrow 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. 1.

   The same pair of wires can be merged by two (or more) wormholes (as shown in Fig. 8, left). In our implementation, the pending list may contain several wormholes merging the same pair of nodes.

2. 2.

   The number of wormholes can be quadratic in the size of the maze, even if it has only $E=𝒪\left(W\right)$ edges (see Fig. 8, 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). In addition, when a wormhole $\alpha \stackrel{X.i}{\to }\beta \stackrel{X.j}{\leftarrow }\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 the edge under scrutiny 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, one of them is in fact “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. 7 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 8.

All wires in an equivalence class of $\stackrel{\ast }{\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 the dual representation graph, an edge $\alpha \stackrel{X.i}{\to }\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 \underset{\mathrm{\#}42}{\overset{𝑋}{\to }}\beta$ means that the sequence of instruction $\mathrm{\#}42$ takes the player from wire $\alpha$ to wire $\beta$, while entering box $X$. So, before the graph rewriting process even starts, we transform the dual representation graph into the extended dual representation graph shown in Fig. 10.

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

When 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:

• $\mathrm{■}$

  Not only the target, but also the origin of hot edges incident to an “absorbed” node must be modified. This requires each node to we aware not only of its incoming hot edges, but also of the outgoing ones.

• $\mathrm{■}$

  The instruction sequences on each edge must be maintained.

• $\mathrm{■}$

  When a wormhole $\alpha \underset{\mathrm{\#}ℐ}{\overset{𝑋}{\to }}\beta \underset{\mathrm{\#}𝒥}{\overset{𝑋}{\leftarrow }}\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,\mathrm{\#}ℐ,\beta ,\mathrm{\#}𝒥,\gamma )$ must be pushed onto the pending list.

• $\mathrm{■}$

  Spanning edges must be stored separately.

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

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.

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²²2Such as the one we designed, available at https://github.com/orelcosseron/Fractal-Maze-Python.. 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. 12). 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.