Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
1  
Not sure exactly what you're asking, but you seem to be looking for information on self-avoiding walks: en.wikipedia.org/wiki/Self-avoiding_walk –  j.c. Oct 8 '10 at 21:57
7  
The path is self-avoiding if and only if it's self-avoiding. I don't know what kind of rule you're looking for. Nothing that involves locally inspecting the sequence will do because self-avoidance is a global property, so there is some irreducible difficulty in this problem. –  Qiaochu Yuan Oct 8 '10 at 22:16
2  
Thanks. I have edited my question to precise the kind of rule I am looking for. It was not clear enough. Thanks. –  Alexis Monnerot-Dumaine Oct 9 '10 at 8:43
3  
I think you should formulate the question as follows: what is the fastest algorithm for determining (in terms of the moves) whether a walk is self-intersecting? The obvious algorithm is just to look at each subinterval of the moves and see whether it is a loop. But there are quadratically many subintervals -- can we do better? –  gowers Oct 10 '10 at 10:47
3  
How about first listing all the positions visited, then applying a fast sorting algorithm, and finally looking for two consecutive positions that are the same? I think that would take time Cnlogn, though at the cost of using quite a lot of memory. –  gowers Oct 10 '10 at 11:27
show 4 more comments

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer
    
for any sequence of $n$ absolute moves $m_1 m_2 ...m_n, m_i \in${N,S,E,W}, it self-intersects if it contains a subsequence $m_a m_{a+1}...m_b, a<b$, such that the subsequence contains exactly the same number of N,S,E, and W, is equivalent to $N^cE^cS^cW^c$. I describe in my answer that deciding a regular language $x^ny^n$ can not be decided by a FSM (finite state automaton) but can be decided by a push-down automaton. Reference would be Papadimitriou's and Lewis' Elements of the Theory of Computation, which I remember from undergrad. Don't remember the original source, though. –  sleepless in beantown Oct 10 '10 at 17:06
    
Thanks for this interesting answer ! Your simplification rules seem correct and it surely is a valid way to determine if a sequence of relative moves is a loop or not. I haven't found any counter-example so far. Now, it isn't really what I could call a "simple rule". Maybe I am looking for something that does not exist ? Unless...anybody else has got an idea ? –  Alexis Monnerot-Dumaine Oct 12 '10 at 13:24
1  
Here's a cheating answer. You first convert every L into RRR. You then count all the Fs up to the first R, subtract the number of Fs between the second and third R, then add the number of Fs between the fourth and fifth, etc. Then you do the same but starting between the first and second R, continuing between the third and fourth, etc. If both totals are zero then you have a loop. Of course, this is essentially the same as the algorithm with absolute directions. –  gowers Oct 12 '10 at 14:27
    
Nice one ! :-) The absolute moves algorithm applied to relative moves. –  Alexis Monnerot-Dumaine Oct 13 '10 at 9:10
    
I made an error in my simplification rule in the comments above; I've corrected it in my answer on this page to $N^cE^dS^cW^d$. For a particular subsequence $M$ to be self-intersecting, the number of North and South moves within $M$ have to match each other and the number of East and West moves within $M$ have to match each other; all four do not have to match all four in number. Gowers approach is effectively the same and, as I state in my answer separately, converting from relative to absolute is not necessary; however, keeping track of the numbers via a stack is necessary. –  sleepless in beantown Oct 13 '10 at 9:55
show 1 more comment

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".

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.