Semi-Thue Systems with an Inhibitor.
A i>semi-Thue system with an inhibitor is one having a special symbol, called an i>inhibitor, that appears on the right side of every rule but does not appear on the left side of any rule. The main result of this paper is that the uniform halting problem is decidable for the class of such systems. The concept of i>inhibitor is related to the concept of i>well-behaved derivation in systems without an inhibitor. The latter concept has received some attention from those interested in the open question as to whether the uniform termination problem for one-rule semi-Thue systems is decidable.
April, 1998 (revised)
1. Introduction, notation and terminology. Semi-Thue systems constitute a
universal model of computation, in the sense that any decision problem about
computations is reducible to a problem about semi-Thue systems. Every recursively
enumerable language is the language of some semi-Thue system. (E.g., see Chapter 7
of [3].)
And yet the concept is simple: A semi-Thue system is an ordered pair (\Sigma; \Pi),
where \Sigma is a finite alphabet of characters and \Pi a finite set of rules (u; v), where in each
case u and v are words over \Sigma. These systems are called "semi-Thue systems" because
the rules are not necessarily reversible, u being referred to as "the left side" and v "the
right side" of the rule (u; v). Semi-Thue systems are distinguished from Thue systems
(named for their originator Axel Thue [15]) whose rules operate in both directions.
The important notion in the study of semi-Thue system is that of a derivation
from one string to another. We write to mean that w 2 is derived in one step
from w 1 , i.e., that there exist words x and y such that w
(u; v) is a rule of the system. We say that z is derivable from w or that there is a
derivation from w to z, if there exist strings w
Each w i is a line of the
derivation, which has lines, and has p steps; p is the length of the derivation. An
infinite derivation is an infinite sequence w
nonnegative integers i.
Although the class of semi-Thue systems is quite powerful, there have been some
applications in which not all this power is appropriate. An example is the context-free
Supported by Grant No. CCR-9500182 from the National Science Foundation.
grammar, which had as its origin the phrase-structure grammar put forth tentatively
and critically by Chomsky [2] for natural languages, but which by now has its chief
application in the domain of formal languages (see [11]). A context-free grammar is a
semi-Thue system that (1) distinguishes between "terminal" and "nonterminal"
characters of the alphabet, (2) restricts rules to those having single nonterminals as
their left sides, and (3) restricts derivations to those whose first lines all consist of a
single occurrence of a particular nonterminal designated as the start symbol (usually S
in the literature) and whose last lines have only terminal characters.
Another application has arisen in the area of computer science concerned with
theorem proving by machine, where semi-Thue systems are used and thought about
extensively. Typically, these semi-Thue systems, often called "rewrite systems," are
used to reduce words to simpler equivalent words (see, e.g., [7] or [1]). Rewrite systems
and context-free grammars are quite different both in their purpose and their
operation. Nevertheless, these enterprises do have in common their use of
computationally weak semi-Thue systems.
The research program into which the present paper fits is not concerned with
particular applications of semi-Thue systems such as grammars and rewrite systems.
Rather it considers various subclasses of semi-Thue systems that appear to be usefully
weaker than the entire class (without regard to any particular application), and then
attempts to assess how useful and weak they are. One method of assessing a subclass is
to determine whether certain decision problems are decidable for it. If so then that is
evidence that the subclass is weak, since most significant decision problems are
undecidable for the full class of all semi-Thue systems. And, if the decision problem is
a computationally important one, it is evidence also that the subclass may be useful.
There are several decision problems that can be used as criteria in this way. Let us
focus on three of them:
(1) The halting problem. Given a semi-Thue system (\Sigma; \Pi) of the
subclass, and given x 2 \Sigma   , is every derivation whose first line is x finite?
(2) The uniform halting problem. Is every derivation in a given
semi-Thue system of the subclass finite?
(3) The derivability problem. Given a semi-Thue system of the subclass,
and given x; y 2 \Sigma   , does there exist a derivation of y from x?
For example, for both the class of context-free grammars and the class of rewrite
systems used by many theoreticians of machine theorem proving, all three of these
problems are decidable. Moreover, any subclass of the semi-Thue systems for which
any of these three problems is solvable is weaker and possibly more useful than the
class of all semi-Thue systems. Weaker because all three problems are undecidable for
the class of all semi-Thue systems. And more useful, albeit in a restricted set of
possible applications, because the ability to tell whether or not derivations will
terminate gives the user an advantage. The importance of termination in the practical
use of rewrite systems is described in detail in [6].
The uniform halting problem seems more difficult than the other two, although
there seems to be no general proof that if that problem is solvable for any subclass of
semi-Thue systems then the other two problems are solvable also. At any rate, several
research workers have decided to focus on the uniform halting problem; in particular,
the question of whether or not that problem is decidable for the subclass of one-rule
semi-Thue systems has received some attention, so far without an answer, in [4], [5],
[8], [9], [10], [12], [13], [14] and [16]. This subclass will be discussed in Section 4.
The subclass that is the main focus of this paper is the subclass of semi-Thue
systems with an inhibitor, i.e., an alphabetic character that occurs at least once on the
right side of every rule, but does not occur on the left side of any rule. The main result
is that the uniform halting problem for this subclass is decidable, proved in Section 3,
where it is also proved that the halting problem and the derivability problem are
decidable. Derivations in semi-Thue systems with an inhibitor will be analyzed in
detail in Section 2.
The subclass of semi-Thue systems with an inhibitor was noticed in the course of
studying the subclass of one-rule systems [13]. The results of the present paper on
semi-Thue systems with an inhibitor lead to a distinction that promises to be fruitful
in analyzing derivations in one-rule systems without an inhibitor. That distinction,
between well behaved derivations and ill behaved derivations, is explained in Section 4.
In this paper lower-case Greek iota (') will be used as an inhibitor. So, in a
semi-Thue system with an inhibitor, ' 2 \Sigma, every right side has at least one occurrence
of ', and no left side has any occurrence of '. Our convention will be that a semi-Thue
system has k rules:
We shall write x ! n y to mean that there is a derivation of n steps (n - 0) from x
to to mean that there is a derivation from x to to mean that
there is such a derivation of at least one step.
For mean that there exist z 1 ; z 2 2 \Sigma   such that x ! z 1 yz 2 . We
shall write x . + y to mean that there exist z 1 ; z 2 2 \Sigma   such that
The well known fan theorem states that an infinite rooted tree in which each node
has only finitely many children nodes has an infinite path. The following generalization
will be useful in Section 2; the proof is left to the reader:
Theorem 1.1. If a forest of finitely many rooted trees has infinitely many nodes,
each of which has only finitely many children nodes, then the forest has an infinite path.
Definition (the y). If x; y and z are words and xyz is a line in a derivation then
it may be that y occurs several times as a factor (i.e., substring) of that line. For
example, then there are
three occurrences of y in xyz, the second of which we shall refer to as "the apparent
occurrence of y in xyz," or "the y in xyz," or (frequently, when the designation xyz is
understood) "the y." The article "the" will indicate that we are referring to a
particular occurrence of y and not to the word y itself. When we wish to talk about the
word apart from any occurrence in a line we shall simply say "y."
Definition (the same occurrence). If x 1 bx 2 u h x 3 th line of a
derivation where b is a letter and x 1 bx 2 v h x 3 is the (j st line of that
derivation, then we talk of the apparent occurrence of b in the j th line as being the
same as the apparent occurrence of b in the (j st line. On the other hand, no
occurrence of a character in the apparent occurrences of u h or v h exists in the other
line: any character occurrence in the apparent u h is destroyed, and any character
occurrence in the apparent v h is created, in going from the j th line to the (j st line.
2. Analysis of derivations. Section 3 will present the decision procedure to
determine whether a given semi-Thue system with an inhibitor is uniformly
terminating. In preparation, this section will develop a method of analyzing derivations
in such systems. To begin, it is stipulated that there be no occurrence of the inhibitor '
in the first line of a derivation. This stipulation will help us establish important
structural concepts. It is justified by the fact that (since ' does not occur on the left
side of any rule) if there is an infinite derivation from x 1 'x then there is an
infinite derivation from one of the x i 's. All semi-Thue systems discussed in this section
and Section 3 will be systems with the inhibitor '.
Definition (vital). For b 2 \Sigma, if xby is a line other than the first in a derivation,
then the apparent occurrence of b is vital if it is not ' and has been created either in
that line or in some preceding line of the derivation (in other words, if that occurrence
of b does not exist in the first line).
Definition (S-occurrence, the set S). (1) If w 6= - and xwy is a line of a
derivation then the w is an S-occurrence in that line if all its character occurrences are
vital, the x does not end in a vital character occurrence, and the y does not begin with
a vital character occurrence. (That is to say, the x must either be null or end in a
nonvital character occurrence. And the y must either be null or begin with a nonvital
character occurrence.) In short, a nonnull S-occurrence is a maximal factor of vital
character occurrences in a line of a derivation. (2) If a line of a derivation begins with
(ends in) ' then the occurrence of - at the left end (right end) of the line is an
S-occurrence. And if bc is a factor of a line where both the b and the c are nonvital
character occurrences, at least one of the two being ', then the - between the b and the
c is an S-occurrence. (3) S is the set of all words having an S-occurrence in some line
of some derivation.
Note that if x's'y !   z and s has no ' then
and y !   y 0 . This follows from the segregating power of the inhibitor ', and shows the
importance of S-occurrences in lines all of whose non-iota character occurrences are
vital. Even more revealing of the importance of S-occurrences is the next theorem.
Definition (S-sequence). The sequence s is an S-sequence if, for each i,
Theorem 2.1. In a semi-Thue system with an inhibitor, there exists an infinite
derivation only if there is an infinite S-sequence.
Proof: If there is an infinite S-sequence s then an infinite derivation
can be defined as follows: For each i, define z i and z 0
i so that s
(guaranteed by the definition of s i . s
is an infinite derivation.
Now assume there is an infinite derivation w
where the character occurrences of w 1 that are never destroyed in the derivation are
precisely those that occur in the apparent factors y . So, for every i,
for some z . Consequently, for some j, 1 - j - m, the sequence
z
is an infinite derivation possibly with repetitions; that is to say, there is an infinite
sequence
For convenience we alter the notation and set z
is an infinite derivation in which every character occurrence of z 1 is eventually
destroyed. Since z 1 is only finitely long, there exists a p such that, for all i - p, the line
z i has no character occurrences in common with z 1 .
Thus for all i - p,
where each s i;h 2 S, and q is the number of "s in z i .
For each line i - p, there is exactly one h such that the s i;h is rewritten by a rule,
becoming (for some in the (i st line; for all
is copied to become the very same S-occurrence in the
st line (but with a different subscript for
to mean that the s i;h 0
is copied to become the s i+1;h 00
in the
st line. Then define C to be the transitive, symmetric and reflexive closure of the
relation C 0 . Thus C(!
and the s i;h is copied, recopied, etc., until it becomes the s i 0 ;h 0
in the (i 0 ) th line, or
is copied, recopied, etc., to become the s i;h .
Clearly, C is an equivalence relation; furthermore if C(! then the
word s
. Note also that, for any i and h - q i , if there is no h 0 - q i+1 such that
for finitely many values of h 0 , s i;h . s i+1;h 0
Consider now the graph H whose nodes are the equivalence classes of the C
relation: The roots of H are the classes having the respective pairs
as members; there is an edge from a node N 1 to a node N 2 of H
if and only if there are and the s i+1;h 0
in the (i st line is part of what is obtained by rewriting from the s i;h in the i th line.
Clearly, H is a forest of rooted trees. Define
Since the z-derivation is infinite, H has infinitely many nodes, each of which has
only finitely many children nodes. Hence, by Theorem 1.1, there is an infinite path
through the Putting s
Definition (v-section, L(v h ); R(v h )). The word w is a v-section if ' does not
occur in w and there is a v h such that, for some x and y, either v
or x'w. Thus the null word is a v-section if and only if some v h either begins in ',
ends in ', or has '' as a factor. If v
In particular, L(v h ) (R(v h only if v h begins
with (ends in) '.
Note that every v-section has an S-occurrence in some derivation. Whenever a
rule applied in a derivation where v the apparent
occurrences of the internal v-sections always become S-occurrences. The apparent
occurrences of L(v h ) and R(v h ) become either S-occurrences or parts of S-occurrences.
E.g., for the system
in the third line of the derivation
a
a'bc'd
a'be'f'g'd
the occurrence of g is an S-occurrence, but the occurrence of of the
S-occurrence be.
An S-occurrence of - must, in its first line, be the result of an application of a rule
having lambda as a v-section. However, if L(v h ) or R(v h the application of the
rule need not result in an S-occurrence of -. E.g., in the system
In the derivation
a
a'bc'd
a'b'f"d
the application of the second rule results in the third line in which R(v 2 ) becomes an
S-occurrence of - but L(v 2 ) does not, being absorbed into the S-occurrence b.
Generally, we can think of a nonnull S-occurrence in a line as a maximal substring
occurrence consisting of consecutive vital character occurrences; it is brought about by
one or more rule applications each of which is responsible for creating some of its vital
character occurrences. The earliest S-occurrences are v-sections, which come about as
a result of rule applications. The more complex S-occurrences are brought about by
the modification of simpler S-occurrences. The theorems that follow will describe this
process in detail.
Theorem 2.2. If the s is an S-occurrence in a line xsy of a derivation, then
either x ends in ' or y begins with ' or both.
Proof: Let s be any word having an S-occurrence in the derivation. Let xsy be
the first line that has that occurrence of s as an S-occurrence. Then
some ff; i; fi, the preceding line being ffu i fi. Let us make three observations.
(1) The v i must have either the rightmost character occurrence of the x, a
character occurrence of the s or the leftmost character occurrence of the y. (Otherwise
s would have an S-occurrence in the preceding line.)
(2) The v i must have a character occurrence in common with either the x or the y.
(Since s has no ' but v i does, s cannot account for all of v i .)
(3) If the v i has any two character occurrences of the line xsy then it has every
character occurrence between.
From (1), (2) and (3) we infer that the v i contains either the rightmost character
occurrence of the x or the leftmost character occurrence of the y.
Case I: is a single character, and the v i contains the b. Then since
the s is an S-occurrence, the b is not vital. And since it is part of the v i , it is not a
character occurrence of the first line. Hence
Case II: is a single character, and the v i contains the c. Then, by
similar reasoning,
We have proved that our theorem is true of the first line having that s as an
S-occurrence. But since "s are indestructible in a derivation, our theorem is true of all
the lines having that s as an S-occurrence.2
We consider two examples. The first is the system with the two rules (ab; aac')
and (c; b'), and the derivation
ab
aac'
whose S-occurrences are underlined. These are the first four lines of an infinite
derivation, which is obtained by applying the two rules alternately. The lines of this
derivation have increasingly long S-occurrences at their left ends, followed by several
S-occurrences of -.
Our second example is the system with the two rules (ab; b'ac) and (c; b'a) and the
derivation
ab
b'ac
b'ab'a
b'b'ac'a
b'b'ab'a'a
Each line of the resulting infinite derivation will have several S-occurrences of b,
followed by an S-occurrence of either ab or ac, and then several S-occurrences of a.
Definition (the sets S L and SR ). S fxjsome derivation has a line x'y in
which the x has no nonvital character occurrencesg. fyjsome derivation has a line
x'y in which the y has no nonvital character occurrencesg. It is not difficult to see that
is the number of
rules.)
It is clear from the definitions that S L [ SR ' S.
Theorem 2.3. If xbsy (xsby) is a line of a derivation in which the s is an
S-occurrence and the apparent letter b is an occurrence from the first line, then
Proof for xbsy: By Theorem 2.2, . The result of deleting all
lines of the derivation after the line xbsy, and then deleting the noted b and all
characters to its left from all lines, is a derivation possibly with repeated lines, having
the line sy = s'y 0 in which the apparent s is an S-occurrence, and hence is vital. Thus
The proof that s 2 SR when the line is xsby is symmetric.2
Theorem 2.4. (a) S the smallest set C such that, for all j, (1) L(v j
the smallest C 0 such that, for all j,
Proof that C ' L from the two-line derivation
y has no ' and there is a derivation of xu j y'z, for some z. This
derivation can be extended to become a derivation of xv j y'z, which shows that
Proof that S L ' C: In any derivation D, put th line does not
begin with a character occurrence of the first lineg. If and D has a j 0th
line then also. For each j 2 J(D), let the j th line be x j 'y j , where x j is
iota-free. Clearly, if J(D) 6= ; and j 0 is the smallest member of J(D) then x
for some h. Also,
j(D)g. We have proved that
L(D) where the union is taken over all derivations D in the
system, we have S L ' C.
Thus S C. The proof that
We shall generally focus on S L knowing that, whatever we prove about S L , an
appropriate similar assertion can be proved about SR .
Definition (The set S Li ). For each
The proofs of the following two theorems are straightforward:
Theorem 2.5. S
Theorem 2.6. If xu j y 2 S Lj 0
then xS Lj ' S Lj 0
Continuing the examples given above, in the system whose rules are (ab; aac') and
(c; b') we have S f-g. In the system whose rules are
(ab; b'ac) and (c; b'a), we have S ag.
Theorem 2.7. the smallest set S 0 such
(1) every v-section is in S
Proof: To prove that S 0 ' S we verify that (1)-(5) are all true of S. Items (1)
and (2) are clear.
The verification for item (3) is as follows: Assume u
some z 0 there is a derivation whose last line is yz'z 0 where the yz is vital. The result of
appending x to the left end of every line is a derivation whose last line is
. We can extend this derivation by adding the line v h z'z 0 , in which the
word R(v h )z will have an S-occurrence, showing that R(v h )z 2 S. The verification for
item (4) is similar.
To verify that (5) is true of S, assume xu h y 2 S. Then, for some z and z 0 , there is
a derivation whose last line is zxu h yz 0 in which the xu h y is an S-occurrence. If we
append to this derivation the line zxv h yz 0 the result is a derivation whose last line has
both xL(v h ) and R(v h )y as S-occurrences, showing that both these words are in S.
(Examples illustrating (3) and (5) are provided after this proof.)
To prove that S ' S 0 we assume an arbitrary derivation D and prove that every
S-occurrence in D is in S 0 . We do so by proving the following proposition by
mathematical induction on i: If D has at least i lines then every S-occurrence in the i th
line is in S 0 .
This proposition is true for since the first line has no S-occurrences.
Assume it is true for the i th line and let the (i st line be xsy in which the s is an
S-occurrence. Assume also that s does not have an S-occurrence in the i th line, and
that is the rule by means of which the i th line is rewritten as the (i st line.
either (a) at the left end of the line, which begins in ', (b) at the
right end of the line, which ends in ', (c) flanked by two consecutive ''s, (d) flanked by
nonvital b 6= ' on the left and ' on the right, or (e) flanked by ' on the left and nonvital
c 6= ' on the right. Since - is not an S-occurrence in the preceding line in the
derivation, the s must be a factor of the v h in the (i st line. In each of the cases (a),
(b), (d) and (e), the ' flanking the s must be part of the v h and - is a v-section of v h .
In case (c) either both "s are part of the v h and hence - is an interior v-section of v h ,
or only one of the two "s is part of the v h and - is an end v-section of v h .
Henceforth we assume s 6= -. Let the noted occurrence of s in the (i st line
consist of the B(s) th through the E(s) th characters of that line, in left-to-right order.
And let the noted occurrence of v h in that line consist of the B(v h ) th through the
E(v h ) th characters. Note that B(v h E(s). To carry through the
proof, we divide into cases based on the relative positions of s and v h in the
st line.
Case I: B(v h ) - B(s) and E(s) - E(v h ). Then s is a factor of v h , and since s is an
S-occurrence of the (i st line, s must be a v-section of v h . By (1), s 2 S 0 .
In the remaining cases either E(v h
v h has an occurrence of ' but s does not, the v h cannot be wholly inside the s. The
possibility E(v h give rise to Cases II and III, while the possibility
give rise to Cases IV and V, which are right-left symmetric to
Cases II and III, respectively.
Case II: E(v h E(s). Then
there would be no change in the vicinity of the s in
going from the i th line to the (i st line, and the s being an S-occurrence in the
st line would also be an S-occurrence in the i th line, contrary to our assumption.
Furthermore, the rightmost character of v h must be ', otherwise that character
occurrence would be vital and the s would not be an S-occurrence in the (i st line.
Thus R(v h since s does not have an S-occurrence in the i th line, the s must
be a proper suffix of an S-occurrence rs in that line.
Case IIa: r is a proper suffix of u h , i.e., u rs is an
S-occurrence in line i preceded by a character occurrence of the first line. (The
rightmost character occurrence of r 0 cannot be ' since it is part of u h , and cannot be
vital since it is not part of the S-occurrence rs.) It follows by Theorem 2.3 that
rs 2 S L . Taking apply (3) getting R(v h )s 2 S 0 . Since
Case IIb: r is not a proper suffix of u h . Then . Here we
apply (5) to get completing Case II.
Case III: E(v h cannot be a substring of s, we
get E(s). Consider the
character occurrence b immediately to the left of the leftmost character occurrence of s.
It must be an ', for otherwise it would be vital and would have to be part of the
S-occurrence s. Furthermore, it must be the rightmost ' in the v h , for otherwise, there
would be an ' inside of the S-occurrence s. Therefore, we can assume that the (i st
line is x y, where v th line is x 0 u h z 3 y.
Case IIIa: all the character occurrences of the u h are vital in the i th line. Then, for
some x 00 ; x 000 where x the x 000 u h z 3 is an S-occurrence in the i th line. By the
inductive hypothesis, x 000 u h z 3 2 S 0 , and by (5),
Case IIIb: not all the character occurrences in the u h in the i th line x 0 u h z 3 y are
vital. Then u all the character occurrences in the u 00 are vital
but the rightmost character occurrence in the u 0 is not vital. This character occurrence
is not an ', so it must be a character occurrence of the first line of the derivation. It
follows that u 00 z 3 is an S-occurrence, since all its character occurrences are vital but it
is not adjacent to a vital character occurrence in the i th line, either on the left or on the
right. Moreover, by Theorem 2.3, u 00 z 3 2 S L . Thus
Case IV: This case is left-right
symmetric to Case II. (It is obtained from Case II by simultaneously interchanging !
and ? and interchanging B and E.)
Case V:
This case is left-right symmetric to Case III.2
We illustrate (3) of Theorem 2.7 by the Thue system
Taking Hence
by (3) we get derivation with an S-occurrence of ga is:
bc
baa'e
h'ga'e
We illustrate (5) by the Thue system
Assume for the moment that abcd 2 S 0 , and take by (5) we
get derivation with S-occurrences of abcd,
ah and jd is
h'abf
Definition (ABC property). A word w has the ABC property if there exist
words A; B; C such that
Theorem 2.8. Every s 2 S has the ABC property.
Proof: Theorem 2.7) we can complete our proof by showing that
every s 2 S 0 has the ABC property.
To this end we note that (1) if s is a v-section then we can take
For (2), if s 2 S L (S R ) then we can take
For (3), if then we can take
y.
For (4), if then we can take
For (5) we should demonstrate that if xu h y has the ABC property then both
it. Accordingly, we assume that xu h
We shall prove that s 1 has the
property, leaving the similar proof for s 2 to the reader. A division into cases is
required according to whether or not x is a prefix of A 0 and, if not, whether or not it is
a prefix of A 0 B 0 .
Case I: A
which satisfies the requirement, since Ax
Case II:
which satisfies the requirement, since A is the same as A 0 , B is
no longer than B 0 and x 2
Case III: y, we have C
y. We now take
2 . Clearly
the requirement, since they are the same as A 0 , x 0
It remains to prove x 2 C 2 S L . Note first that
So, by Theorem 2.4, x 0
our proof is complete.2
Theorem 2.9. If S is infinite then either S L or SR is infinite.
Proof: If S is infinite then fjsjjs 2 Sg is an unbounded set of lengths. By
Theorem 2.8, each accord with the ABC property. Since fjB s jjs 2 Sg is
bounded, either fjA s jg or fjC s jg is unbounded. But each A s (C s ) is a factor of a
member of SR (S L ). It follows that either SR or S L is infinite.2
3. The algorithm. This section presents the algorithm to determine whether a
given semi-Thue system with an inhibitor is uniformly terminating, 1 using the analysis
of the preceding section. At the conclusion of this section, it is proved that the halting
problem and the derivability problem are also decidable.
The algorithm will begin by constructing finite automata for the languages S L
and SR .
Definitions related to finite automata. A nondeterministic finite automaton
(automaton for short) is a finite directed graph each of whose arcs has either a letter or
the symbol - as a label; one node is designated as the initial node and any number of
nodes are designated as accepting nodes. A walk through the graph is a sequence
where the N i 's are nodes and the A i 's are arcs, such that for each i, A i goes from N i\Gamma1
to N i . This walk goes from N 0 to N p . The word spelled out by this walk is the result of
deleting all -'s from the word a 1 a 2 \Delta \Delta \Delta a p where, for each i, a i is the label of N i . In
particular, the word spelled out is the null word itself if a i. The language
of an automaton is the set of all words spelled out by walks from the initial node to an
accepting node.
We begin by constructing, for the finite language fL(v h )j1 - h - kg, a loopless
finite automaton G 0
(1) exactly one initial node N I with no arc entering it;
(2) exactly one accepting node N T with no arc leaving it;
(3) exactly one path from N I to N and exactly one path from N to N T , for
each node N other than N I and N T ;
(4) nodes N Lk such that, for each i, the path from N Li to N T spells
out L(v i ); in particular, if L(v i there is simply a lambda arc, i.e.,
arc labeled -, from N Li to N T ; and
(5) for each i, a lambda arc from N I to N Li .
The construction is done so that
there are no nodes in G 0 other than those required by (1)-(4), and there
are no lambda arcs except those explicitly mentioned in (4) and (5).
From G 0 we construct a finite automaton G L for the language S L by repeating the
following step as often as possible: for a pair of nodes N; N 0 and an integer
I am grateful to Friedrich Otto for pointing out a defect in a previous version of this algorithm
in [13].

Figure

1: G 0

Figure

2: G L
if there is a walk from N to N 0 spelling out u i , insert a lambda arc from N to N Li ,
provided that there is not one already there.
Note that G L and G 0 , having the same set of nodes, differ only in that G L has
certain lambda arcs that G 0 does not have. It follows that the construction step is
repeated only finitely many times and the graph G L so constructed is a
nondeterministic finite automaton.
As an example, G 0 and G L for the semi-Thue system
are shown in Figures 1 and 2, respectively. Thus S
The automaton GR for the language LR is like G L except that N I and N T are
interchanged and all arrows are reversed. More explicitly, we first construct G 0R for
the same as (1),(2),(3);
Rk such that, for each i, the path from N I to N Ri
spells out R(v i this is simply a lambda arc; and
each i, a lambda arc from N Ri to N T .
The construction is done so that
are no nodes in G 0R other than those required by (1 0 )-(4 0 ), and
there are no lambda arcs except those explicitly mentioned in (4 0 ) and (5 0 ).
From G 0R , GR is constructed by repeatedly finding N , N 0 and i such that there is
a walk from N to N 0 spelling out u i ; and then inserting a lambda arc from N Ri to N 0 .
GR is similar enough to G L so that we can carry through detailed reasoning about G L
knowing that corresponding things about GR will also follow.
Theorem 3.1. The language of G L (GR ) is S L (S R ).
Proof for G L : With Theorem 2.4, the proof that S L is a subset of the language of
G L is straightforward and is left to the reader.
For the converse let A q be the lambda arcs in G L other than those of
in the order in which they are added in the construction. For each h, 1 - h - q, let
G h be the graph that results from G 0 by adding the lambda arcs A . Thus for
Where A h+1 goes from N to N Li ,
there is a walk in G h from N to some node N 0 spelling out u i .
Let P (h; n), for q - h - 1 and n - 0, be the following assertion: For all i,
spelled out by a walk in G h from N Li to N T in which the lambda arc
A h occurs at most n times then w 2 S Li .
Our objective will be to prove that P (q; n) is true for all n. First we note that
is true, since for each i there is only one walk in G 1 without the arc A 1 from
N Li to N T , which is a walk in G 0 , and that walk spells out the word L(v i
Next we prove that, for each h - q and n,
n) and let w be spelled out by a walk W in G h from N Li to N T in which A h occurs
times. Let occurs n times in W 1 but does not occur in
respectively. Assume A h goes from node N to
N Lg . By the construction of G h from G h\Gamma1 there is a walk W 3 in G h\Gamma1 from N to N T
spelling out a word u g y for some y. The walk W 1 W 3 spelling out w 1 u g y has only n
occurrences of the arc A h . Thus P (h; n) implies w 1 u . The walk W 2 from N Lg
to N T has no occurrences of the arc A h . Hence w 2 2 S Lg , which, by Theorem 2.6,
implies
From this it follows by mathematical induction that, for all n and h - q, P (h;
implies P (h; n). But, for all h ! q, P (h; n) for all n is equivalent to P
Putting all this together we get the proposition
For all n; P (q; n)
which, by Theorem 2.5, clearly implies that the language of G is included in S L ,
concluding the proof that the language of G L equals S L .
The proof that the language of GR is SR is similar.2
Next it is proved that certain derivations in the semi-Thue system can be obtained
from certain walks in G L and GR . In particular, loops in the automaton graphs will
yield derivation loops in the semi-Thue system. We confine our attention to G L ,
knowing that corresponding results about GR will also be valid. We refine our
consideration of the algorithm in obtaining the graph G L from G 0 , considering the
sequence as defined in the proof of Theorem 3.1.
Definition (w 0 (N)). For any node N other than N I , w 0 (N) is the word spelled
out by the unique walk from N to N T in G 0 .
Theorem 3.2. For each i, 0 - i - q, and for any two nodes N and N 0 in G i other
than N I , if there is a walk from N to N 0 spelling out a word x, then
z. If the walk has at least one lambda arc then
some z. These derivations are obtainable effectively.
Proof: We begin by proving the first sentence by mathematical induction on i.
That sentence is clearly true for 0: in this case w 0 since the only
relevant walks are segments of the walks from the N Li 's to N T , which are disjoint from
one another. We now assume it is true for inductive hypothesis)
and prove it is true for i + 1. This proof is itself by mathematical induction on the
length of the walk from N to N 0 . The proposition is clearly true when this length is 0.
We assume it for walks of length e (the e inductive hypothesis) and we prove it for
walks of length e + 1. Thus let
be this walk in G i+1 , and let the word x a be the word spelled out by it, x e
being the word spelled out by the walk N of length e. By the e inductive
Case I: a 6= -. Then the arc from N e to N e+1 labeled a is on the walk in G 0 from
N e to N T . Consequently, w 0 (N e
Case II: h, and (whether the lambda arc from
N e to N e+1 is the new lambda arc of G i+1 or one already in G i ) there is a walk from N e
to N T in G i spelling out a word u h z 0 , for some z 0 . By the i inductive hypothesis,
. Thus we have, for some z 000 :
since x
This concludes the proof of the first sentence in the statement of our theorem.
The second sentence follows from the fact that a lambda arc in the walk causes Case II
to apply, insuring that the derivation has at least one step. Clearly, all these
derivations are obtained effectively.2
Definition (loop derivation). If w .   y and y . + y then we say the system has a
loop derivation on y from w. Note that a loop derivation provides us with one kind of
infinite derivation: from w we get the infinite derivation
From the proof of Theorem 3.2 we also get
Theorem 3.3. If node N is on a loop in G L then there is a loop derivation on
in the semi-Thue system.
(It should be mentioned that a loop does not imply that S L is an infinite set. It is
possible for the loop to consist entirely of lambda arcs and for S L to be finite. For
example, this happens with the system with the two rules (a; b'c), (b; a'c), for which
bg. Following the constructions we get a . + a, which we could have inferred in
this simple example from the observation that a ! 2 a'c'c.)
Theorem 3.4. If s 2 S and jsj ? (2k 1)m then there is a loop derivation from s.
Proof: That s has the ABC property (by Theorem 2.8) and that jsj ? (2k
together imply that
either jAj ? km or jCj ? km.
Case I: jCj ? km. Since x 2 C 2 S L , there is a walk in G L spelling out C ending at
N T . But, by the construction of G L , all words spelled out by loop-free paths in G L have
length - km. Thus there is a loop in the walk spelling out C, and so by Theorem 3.3
there is a loop derivation on some suffix of C, and hence a loop derivation from s.
Case II: jAj ? km. The proof is similar, using the graph GR for SR :2
Theorem 3.5. There is an algorithm that determines whether both G L and GR
are without loops and, if so, enumerates the finite set S.
Proof: By Theorem 3.1, S It is easy to tell whether
both graphs are without loops.
Assume now that they are without loops. Then the sets S L and SR are finite and,
by Theorem 2.9, so is S. S L and SR are enumerable from G L and GR . Let S 0 be the
smallest set satisfying (1)-(4) of Theorem 2.7. From the finite enumeration of S L and
SR we can enumerate S 0 . Noting that S is the smallest class that contains S 0 and is
closed under (5) of Theorem 2.7, let us recursively define the sets S i+1 , for all i - 0:
Clearly, S i+1 is computable from S i ; and
. But since S is finite by
Theorem 2.9, in computing the successive S i 's, eventually we shall reach an i such that
which implies that, for this i,
Theorem 3.6. If a semi-Thue system with an inhibitor in which S is finite has an
infinite derivation then there exists an s 2 S such that s .
Proof: Since there is an infinite derivation, there is an infinite S sequence
Theorem 2.1. Because S is finite there must exist p and q, q ? p, such
that s
Theorem 3.7 (Main Theorem). There is an algorithm that produces either a
loop derivation in a given semi-Thue system with an inhibitor, or the information that
the system is uniformly terminating.
Proof: The algorithm begins by constructing the automaton G L for S L . If G L has
a loop then from that loop a loop derivation is effectively determined, by Theorem 3.3.
If G L has no loop, the analogous automaton GR for SR is constructed. If GR has a
loop, analogously a loop derivation is effectively determined.
If neither G L nor GR has a loop then, by Theorem 3.5, S is finite and can be
enumerated. The . relation on S is computed and, from this, the . + relation on S. If
there is an s 2 S such that s . + s then we have a loop derivation, effectively.
Otherwise, by Theorem 3.6, the system has no infinite derivation.2
Corollary 1. The uniform termination problem for semi-Thue systems with an
inhibitor is decidable.
Corollary 2. If a semi-Thue system with an inhibitor has an infinite derivation
then it has a loop derivation.
In studying the complexity of the algorithm of Theorem 3.7, we assume that the
expression T naming the semi-Thue system is simply the list of its rules,
The following assertions should be clear to the reader: The
automaton G 0 is constructible in polynomial time. Each G i+1 is constructible from G i
in polynomial time. Since all the automata G have the same set of
nodes and each G i+1 is obtained from G i by adding an arc, q is bounded by a
polynomial in the number of these nodes. Thus the construction of the
nondeterministic finite automaton G L is accomplished in polynomial time, and
similarly for GR . It is possible to determine in polynomial time whether G L (GR ) has a
loop, and if so to produce the loop derivation in polynomial time.
However, I cannot prove that the enumeration of S L (S R ), if it is finite, can be
done in polynomial time, since jS L j (jS R j) may be exponential in the size of G L (GR ).
Thus if G L or GR has a loop, the main algorithm produces a loop derivation in
polynomial time and terminates. But if neither G L nor GR has a loop then the main
algorithm has to enumerate the finite set S. Since there is no polynomial bound on jSj
for those S that are finite, the algorithm as written in the proof of Theorem 3.7 is not a
polynomial-time algorithm. However, this does not imply that the following has a
negative answer:
Open question 1. Is there a polynomial-time algorithm for the problem of
whether a given semi-Thue system with an inhibitor is uniformly terminating?
This section closes by settling the two remaining problems of Section 1, the
halting problem and the derivability problem for semi-Thue systems with an inhibitor.
Theorem 3.8. The halting problem for semi-Thue systems with an inhibitor is
decidable. If such a system has an infinite derivation from a word w then it has a loop
derivation from w.
Proof: For a given w and be the set of
derivations from w of length i, and
let\Omega i be the set of all S-sequences that can be
taken from those derivations (as in the proof of Theorem 2.1). Note that \Delta 1
and each \Delta i+1
and\Omega are readily computable from \Delta i
and\Omega i . Consider three
possibilities:
(1) For some i ? 1, ;. Then there is no infinite derivation from w.
(2) There is an i and an S-sequence
in\Omega i with a repeated S-expression.
Then there is an loop derivation from w.
(3) There is an i and an S-sequence
in\Omega i with an S-expression s such that
m. Then by Theorem 3.4 there is a loop derivation from s, and hence
a loop derivation from w.
If any of these possibilities occurs, then we have the answer to the question after a
finite amount of time. It remains to prove that one of them must occur. Theorem 1.1
can be used to prove that if there is no infinite derivation from w then the set of
lengths of the derivations from w has an upper bound and possibility (1) will occur. If
there is an infinite derivation from w then by Theorem 2.1 there is an infinite
S-sequence \Delta. The proof of that theorem makes it clear that w .   s 1 , and hence
w .   s i , for all i. If that S-sequence has a repeated element then possibility (2) will
occur. If not there will be no bound on the length of the elements occurring in that
S-sequence and possibility (3) will occur.2
Theorem 3.9. The derivability problem for semi-Thue systems with an inhibitor
is decidable.
Proof: We define I(w) to be the number of iotas in the word w. Where
is a derivation and be the weight of the
st step, which equals I(v), (u; v) being the rule used. Let the weighted length of
a derivation be the sum of the weights of all the steps of the derivation. Given x and y,
any derivation of y from x must have a weighted length of I(y) \Gamma I(x).
The algorithm that decides whether y is derivable from x simply enumerates all
derivations from x whose weighted length equals I(y) \Gamma I(x). Because all weights are
positive, no line z such that I(z) ? I(y) can be part of a such a derivation.
Consequently, the list of such derivations can be enumerated readily. Finally, y is
derivable from x if and only if the last line of one of these derivations is y:2
Open question 2. Does there exist an algorithm for the following problem:
Given a semi-Thue system with an inhibitor and words x and y, does x .   y hold?
4. Well behaved derivations. 2 We now turn our attention to semi-Thue
systems without an inhibitor, with an emphasis on those having only one rule. Some
derivations in these systems turn out to be like those in systems with an inhibitor.
Definition (inhibited rule, inhibition system). If u a rule of a
semi-Thue system T without ' then is an inhibited rule of T . (v 0 or v 00 can be
the null string.) The inhibition system of T is the semi-Thue system whose rules are all
the inhibited rules of T . An immediate consequence of this definition is
Theorem 4.1. If x is a finite or infinite derivation in the inhibition
system of the semi-Thue system T then, where each x 0
i is x i with all "s erased,
is a derivation in T .
Definition (well behaved, ill behaved). A derivation D in a semi-Thue
system T without ' is well behaved if there is a derivation in the inhibition system of T
from which D is the result of deleting all "s. Otherwise D is ill behaved.
From Theorems 4.1 and 3.7 we get
Theorem 4.2. There is an algorithm that produces, given a semi-Thue system
without ', either a well behaved loop derivation in the system or the information that
the system has no well behaved infinite derivation.
Example 1. The inhibition system T 0 of the system T whose one rule is (cb; bbcc)
has five rules:
This section is based on material from [13].
This system T 0 has an infinite derivation. In fact, all we need for this infinite
derivation is the one rule (cb; bb'cc). The infinite derivation is based on the following
loop of length 2:
ccb
cbb'cc
bb'ccb'cc
(In this and the examples to follow, the part of the line with an underscore is the
occurrence of u that is rewritten as the v in the next line, which has an overscore.) The
th line in the infinite derivation is (bb') st line is
Accordingly, the original system also has an infinite well behaved derivation based
on the loop
ccb
cbbcc
bbccbcc
The (2n) th line of this infinite derivation is (bb) st line is
Example 2. The following is an ill behaved derivation in the system with the one
rule (ccb; bbccc):
ccccbb
ccbbcccb
bbcccbcccb
bbcbbccccccb
bbcbbccccbbccc
bbcbbccbbcccbccc
To prove that this derivation is ill behaved we note that the inhibition system has
six rules, whose right sides are, respectively, 'bbccc, b'bccc, bb'ccc, bbc'cc, bbcc'c and
bbccc'. Thus the second line in the corresponding derivation in the inhibition system
has six possibilities. It is left to the reader to verify that in each of these six cases the '
will inhibit the replacement of the occurrence of bbc in one of the lines below. (For
example, if the ccb in the first line is rewritten as bb'ccc in the second line then the ccb
in the fifth line cannot be rewritten.)
However, the first five lines of the above derivation form a well behaved derivation,
which can be verified by considering the following derivation in the inhibition system:
ccccbb
ccbbc'ccb
'bbcccbc'ccb
'bbc'bbcccc'ccb
If all the "s from this derivation are deleted, what remains are the first five lines of the
above derivation in T .
The system with the single rule (ccb; bbccc) has an infinite derivation. This is clear
from the first five lines of our original derivation, which shows that
ccccbb . 4 ccccbb
The sixth line of this infinite derivation is the sixth line of the above derivation, which
shows that the infinite derivation is ill behaved.
This system has no infinite well behaved derivation. To verify this fact we can
refer to Theorem 4.1 and prove that its inhibition system has no infinite derivation.
Using the algorithm of Section 3 for this is tedious as it involves enumerating S.
Rather than do this we work with a superset of S:
3g. Then it is rather simple to verify using
Theorem 2.4 that
Thus in particular, for each rule (u; v), we have L(v); R(v) 2 T .
Next, we use Theorem 2.7 to verify that
by proving the following:
(1) every v-section is in TT ;
(3) (since all rules have the same left side ccb) if
then R(v)z 2 TT (for all right sides v);
Parts (1) and (2) are clear. For (3), yz 2 S L implies
. The reasoning for (4) is similar to the
reasoning for (3).
For (5), implies that . So, a fortiori,
From L(v); R(v) 2 T , we then get xL(v); R(v)y 2 TT .
Having proved that S ' TT , we complete the proof that the inhibition system has
no infinite derivation by proving there is no infinite S sequence (invoking Theorem 2.1).
The proof is by contradiction. Assume there is an infinite S sequence s
Then each s h
with
and 3. The following must be true:
nothing could be derived from u h .)
(b) Either
(Part (b) can be verified by first noting that there is only one occurrence of ccb in
. Thus if s h ! w, then w is a word resulting from
by placing a single ' anywhere between the two slashes and deleting the slashes; s h+1 is
either the word to the left of the ' or the word to its right. If to the left then
if to the right, k
Taking
, we have by (b) either
1. By (a) again we get k
Where s
we get by (b) either j
By (a) we then see that s 4 cannot exist, which completes our proof that the system
with the one rule (ccb; bbccc) has no infinite well behaved derivation, ending our
discussion of Example 2.
In [13] there is a much more expeditious algorithm for the problem of whether a
given one-rule semi-Thue system has an infinite well behaved derivation. That
algorithm does not require consideration of the inhibition system of the given system,
but involves a structural analysis of one-rule systems that is well outside the purview of
this paper. That structural analysis having been established, the proof in [13] that the
one-rule system (ccb; bbccc) has no infinite well behaved derivation takes one quarter
the space used in the proof given above as part of Example 2.
This example generalizes. Zantema and Geser [16] prove that a system with one
rule
in which (1) p ? n, either p is a multiple of n or q is a multiple of
m, has an infinite derivation. In [13] it is proved that such a system in which either
2m has no infinite well behaved derivation. From these two results it
follows that any such system in which either 2n in for i an integer - 2
or else 2m ? in has an infinite ill behaved derivation but no infinite well
behaved derivation.
Interestingly, it is proved in [16] that there is no infinite derivation at all in any of
the following cases: (1) q is not a multiple of m,
is not a multiple of n. (Senizergues [14] has extended these results of
Zantema and Geser.) In [13] it is proved that if p - 2n and q - 2m then there is an
infinite well behaved derivation.
The two examples discussed in this section illustrate the distinction between well
behaved infinite derivations and ill behaved infinite derivations. They are intended to
suggest the importance of this distinction to the question of whether the uniform
halting problem for one-rule semi-Thue systems is decidable. It is generally conjectured
that this problem is decidable, and some progress has been made in proving partial
results along that line. However, the question of whether the uniform halting problem
for one-rule semi-Thue systems is decidable is very much open. It seems to me that
further progress on this question will come only if research workers achieve a structural
understanding of ill behaved derivations. There are partial results towards this end
in [13].
The halting problem is open for one-rule semi-Thue systems. On the other hand,
we have
Theorem 4.3. The derivability problem is decidable for one-rule semi-Thue
systems.
Proof: Given x, y and a semi-Thue system whose one rule is (u; v) our algorithm
to determine whether y is derivable from x divides into three cases according to the
relative lengths of u and v: Case I, jvj ! juj; Case II,
In Cases I and II, the finite set of words derivable from x can be enumerated, and the
presence or absence of y in the set easily determined. In Case III, the finite set of
words derivable from x whose length does not exceed that of y can be enumerated,
again yielding an answer to the question.2
For a class of semi-Thue systems an interesting question is, does every semi-Thue
system in the class with an infinite derivation have a loop derivation? The result in
Section 3 shows that this question has an affirmative answer for the class of semi-Thue
systems with an inhibitor. When restricted to well behaved infinite derivations, it has
an affirmative answer for all semi-Thue systems. However, it is an open question for
one-rule semi-Thue systems; which means that the question restricted to infinite ill
behaved derivations is open for one-rule semi-Thue systems.



--R


"Three models for the description of language,"

"Termination of rewriting,"
"Topics in termination,"
"On proving uniform termination and restricted termination of rewriting systems,"
Monographs on Theoretical Computer Science
Termination und Konfluenz von Semi-Thue-systemen mit nur einer Regel
"Explanations to the text,"
"One-rule semi-Thue systems with loops of length one, two or three,"
"The development of formal language theory since 1956,"
"The uniform halting problem for one-rule semi-Thue systems: progress report,"
"Well behaved derivations in one-rule semi-Thue systems,"
''On the termination problem for one-rule semi-Thue systems"
"Probleme - uber Ver-anderungen von Zeichenreihen nach gegeben Regeln,"
"A complete characterization of termination of 0
--TR

--CTR
Matiyasevich , Graud Snizergues, Decision problems for semi-Thue systems with a few rules, Theoretical Computer Science, v.330 n.1, p.145-169, 31 January 2005
string rewriting;uniform termination;well behaved derivation;semi-Thue system;termination