How to characterize a Self-avoiding path.

Question

I cannot find any answer to that apparently simple problem : On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}.

Is there a rule that characterizes if a path is self-avoiding (or not) ?

Edit : Let me precise the kind of rule I am looking for: Let's imagine a walk described, this time, by absolute moves (N=move North, S=move South, E=move East, W=move West), then the presence of a loop in the sequence is characterized by a subsequence for which nb(N) = nb(S) and nb(E)=nb(W). That's a simple rule.

Is there such a rule in the case of a sequence of relative moves ? Or do we have to translate the sequence to absolute moves ? Thanks.

Example (to make myself clear): here is a walk (or part of a walk), written in absolute moves {North, East, West, South}: EENWNNWSSS => We immediately know it is a loop, without having to draw anything or keep track of the positions visited, because nb(N)=nb(S) and nb(E)=nb(W).

Now here is the same walk written in relative moves {Forward, Turn right, Turn left}: FFLFLFRFFLFLFFF => Without drawing anything, nor converting to absolute moves. Is there a rule that allows to say it is a loop ?

Answer 1

I'm only now starting to understand the question. Let me formulate it slightly differently, but I think it's easy to translate between this and your formulation. I'll imagine a little machine with three possible operations: take a step (which is always in the direction of an arrow on the machine's head, so would be your "forwards"), turn to the left (which changes the direction of the arrow but doesn't change the square the machine is on), and turn to the right.

If you're prepared to characterize self-avoidance with a statement like "There is no subsequence such that ...," as you seem to be, then it is enough to characterize loops. This is easy to do if we convert into absolute moves, as you say, so the idea is not to do that. It is quite hard to say precisely what it means not to keep track of the direction the machine is pointing in, but here is an attempt.

Now there are various ways that a sequence of moves can be simplified. For instance, RRR=L, LLL=R, and RL=LR="do nothing", so we can always rewrite so that there are at most two turns in a row, when they have to be the same. Also, FRRF can be simplified to RR, so if we ever have RR or LL we can cancel Fs on either side until we have three turns in a row and then cancel those.

After all this cancellation, we may assume that we never have two turns in a row. But that is not all the cancellation that can be done. For instance, $FRF^kRF$ cancels to $RF^kR$. So if we ever have $RF^kR$ we can cancel Fs on both sides until we get two turns in a row and go back to the previous method for getting rid of that.

So now we may assume that the sequence consists of Fs with isolated Rs and Ls that have to alternate. That won't be a loop unless the sequence is null.

I think this can be done without thinking about what the absolute direction is, but one could perhaps argue that the cancellation rules are working mod 4 and keeping track of the direction in an implicit way. But I'm not sure that's right, since we can do the cancellation in the middle of the sequence without caring about the absolute direction at all. So perhaps this counts as a sort of answer to your question.

Answer 2

This question is equivalent to asking if a finite-state-automaton can decide or accept a particular language, or if a push-down automaton could. I believe the only way to deduce the self-intersection or self-avoiding nature of a walk based on relative moves of {turn left, move forward, turn right} is to turn them into a sequence of absolute moves and simulate them on the square lattice, keeping track of state along the way.

Summary:

Convert the sequence of relative moves into a sequence of absolute moves. This step is not absolutely necessary but helps to make the next step easier to understand.

for any sequence of $n$ absolute moves $m_1 m_2 ...m_n,$ with $m_i \in$ {N,S,E,W}, it self-intersects if it contains a subsequence

$m_a m_{a+1}...m_b$, such that $1 \le a\lt b \le n$

such that the subsequence contains exactly the same number of $N$ as it does of $S$ and exactly the same number of $E$ as $W$.

This is equivalent to and can be restated as $N^cE^dS^cW^d$, or as saying $\Delta$(Longitude)$=0$ and $\Delta$(Latitude)$=0$.

Deciding a regular language $x^n y^n$ (or in this case $N^c S^c E^d W^d$ ) can not be decided by a FSA (finite state automaton) but can be decided by a push-down automaton, which keeps track of state in the push-down stack. My reference for computability or acceptability by a Finite State Automaton is (for me, in this case) Papadimitriou and Lewis Elements of the Theory of Computation, which I remember from my undergraduate course in computation theory. I don't remember the original source described in the book, though. In this case, the push-down stack is keeping track of the state of either the number of N,S,E,W, via the direction traveled or the state of which squares have been visited thus far. Either way is equivalent, and effectively requires simulating the walk.

---

I believe the only way to deduce the self-intersection or self-avoiding nature of a walk based on relative moves of {turn left, move forward, turn right} is to turn them into a sequence of absolute moves and simulate them on the square lattice. The reason for this is that the self-intersection may occur in two squares as the sequence (move forward), (turn left | turn right)${}^3$, (move forward). It may also occur $n$ steps later, with $n>1$, as in ( (move forward)${}^{10}$, (turn right) )${}^4$ which self intersects as a square of width $10$ after eighty relative moves $=$ forty absolute moves.

If you were to look at a series of relative moves or turtle-graphics-moves as a series of symbols, and attempt to apply some symbolic dynamics rules such as replace a (forward)(turnaround)(forward) $\to$ (INTERSECTIONFOUND), or (turn right)${}^3 \to$ (turn around), etc., then it would not be possible to create enough rules to keep track of state of each possible lattice point in the square lattice. You have to keep track of the state of the lattice points as having been "visited" or "not visited" and simulate the entirety of the walk or at least enough of the walk until an intersection first occurs in order to determine that the walk is self-intersecting.

You must simulate the entire length of the walk to determine that it is not self-intersecting.

This is similar to the result that certain languages are not acceptable or decideable by a finite-state-machine, but are decideable or acceptable by a push-down-stack turing machine: the canonical example is designing a finite-state-machine which decides the language $a^nb^n$ or checks for matching right-parentheses for every left-parenthesis. This type of matching exercise, where $n$ copies of the symbol $a$ are followed by exactly $n$ copies of the symbol $b$ are not recognizable by a finite state automaton, but can be recognized by a push-down automaton (also known as a stack-based finite-state-machine).

If instead, I think you are trying to ask if there are rules that can be applied locally, where by locally I mean by observing only the local neighborhood (which can be the Von Neumann neighborhood [N,S,E,W] or Moore neighborhood [NW,N,NE, W, E, SW, S, SE] in 2-d, or all nodes connected by edges to the current edge for cellular automata on a graph) and capture the behaviour of a self-avoiding walk.

Purely local rules are not enough to capture the global behaviour necessary to allow for the creation of a self-avoiding walk unless the cells to be walked on are also allowed to store "state" for their location. If a cell can also have associated with it a "state" corresponding to "having been walked on" as $1$ and "never having been walked on" as $0$, then it is possible to define a self-avoiding walk in such a way.

The rules for such a walk would be:

• Have the walker change the state of the cell it is currently in to $1$

• Have the walker move to a neighboring cell according to your random walk rules and probabilities only if that neighboring cell has a state corresponding to "never having been walked on" $=0$

• iterate until it is impossible for the walker to move in any direction (corresponding to all of the neighboring cells of the current position already having been walked on)

Thus to model or simulate something which captures global properties in this case, it is important to allow the model to hold and represent the global property of "the path walked thus far". It's also akin to and contrary to the ant-walking algorithms with the ants leaving a pheremone trail which can increase the likelihood of further walkers following a particular path. It's also similar to creating a path for a painter to walk without being "painted into a corner".

Answer 3

In describing the relative moves, I think you need to say "turn right (left)" rather than "move right (left)". The question then becomes, in my interpretation: given a string of moves, by what rule can you determine if the sequence takes you back to your starting point? The question of a self-avoiding path is then answered by applying the rule to every substring of the path.

The rule you give for absolute moves is simply expressed, but really only encapsulates the process of "track the coordinates you are at - you are back where you started when the coordinates reach (0, 0)"; it is only because one coordinate happens to be exactly "number of Up moves minus number of Down moves", and similarly for Right - Left, that it appears any simpler than the process it represents. The rule for relative moves isn't so simply expressed, but will also resolve to exactly the same thing: tracking your absolute position to see if you get back to your starting point.