On W.H.J.Feijen’s string equation

On W.H.J. Feyen's string equation

This note deals with a problem posed and solved by W.H.J. Feyn. It does not need to be written because one of these days he will write it down if he has not done so already. But I had an urge to write something technical and could not resist the challenge of trying to develop the little theory needed really nicely.

We use capital letters to denote finite strings from some alphabet. In what follows, the specific choice of alphabet is so irrelevant that the latter can remain anonymous; in fact, the alphabet will not be mentioned any more.

Concatenation of strings will be denoted by juxtaposition; concatenation is associative and the empty string is its identity element.

The length function will be denoted by $#$ .

We shall use the following lemmata (I think):

Lemma 0: The empty string is the only solution of the equation $x : \left( {# x = 0}\right)$ .

Lemma 1: $# .\left( {XY}\right) = # .X + # .Y$

Lemma 2: $# .A = # .C \land # .B = # .D \Rightarrow$

$$ (A B = C D \equiv A = C \land B = D) $$

The task posed by Feigen is to investigate the equation

(0) $X : \left( {{AX} = X\overrightarrow{B}}\right)$

i.e. to determine the conditions under which this equation is solvable and to determine under those conditions its solutions.

From Lemma 1 we immediately deduce

${AX} = {XB} \Rightarrow # .A = # .B.$

hence our first result:

(2) $# .A \neq # .B \Rightarrow \left( 0\right)$ has no solutions

From Lemma 0 and the fact that the empty string is the identity element of the concatenation, we derive our second result:

(3) $# \cdot A = 0 \land # \cdot B = 0 \Rightarrow$ any string solves (0).

Therefore, from now on we confine ourselves to the study of (o) with

(4) $# \cdot A = n \land # \cdot B = n \land n > 0$

I realize that I need a further lemma about concatenation:

Lemma 3 With $n \leq # X$ the equation

$$ Y, Z: (X = Y Z \land #. Z = n) $$

has a unique solution.

And now we are ready for the works. We observe under validity of $P\left( 4\right)$ for any $X,Y$ ,and $Z$ with #. $Z = n$

$$ \begin{array}{l} (X \mathrm {s o l v e s} (0)) \wedge X = Y Z \ = {(0) a n d p r e d i c a t e c a l c u l u s / L e i b n i z } \ A Y Z = Y Z B \wedge X = Y Z \ = {\mathrm {L e m m a} 2 } \ A Y = Y Z \wedge Z = B \wedge X = Y Z \ = {\mathrm {p r e d i c a t e c a l c u l u s / L e i b n i z} } \ A Y = Y B \wedge X = Y B \wedge Z = B \ \end{array} $$

i.e. $x = {YB}$ defines a one-to-one correspondence

between solutions differing n in length and

we can now confine our study to solutions

$X$ of (0) with # $X \leq n$ . Under that constraint

-lemma 3 - we can write

(5) $A = {PQ} \land B = {RS}\;$ with $# .P = # \cdot X \land # S = # \cdot X$

and observe

$$ \begin{array}{l} (X \mathrm {s o l v e s} (0)) \ = {0) a n d (5) } \ P Q X = X R S \ = {(5) a n d L e m m a 2 } \ P = X \wedge Q = R \wedge X = S \ = {\mathrm {c a l c u l u s a n d (5)} } \ P = X \wedge A = P Q \wedge B = Q P \ \end{array} $$

i.e. solvability of (0) is equivalent to solvability (6) $P,Q : \left( {A = {PQ}\;A = {QP}}\right)$

whose solvability expresses that A can be ob-. tained by rotating B. Each solution $P,Q$ of (6) generates the solutions $P{B}^{ * }$ of(0).

Remark A more symmetric way of expressing those solutions is ${A}^{ * }P{B}^{ * }$ . (End of Remark.)

The problem is not deep, but if it is nice it can be dealt with so nicely.

Nuenen, 25 Dec. 1986

prof. dr. Edsger W. Dgkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 United States of America