SOME COMBINATORIAL PROPERTIES

OF COMPLETE SEMI-THUE SYSTEMS

Winfried Kurth

A reduction system (R, ⟶) consists of a set R and a binary relation ⟶ on R. Let ⟶^{∗} be the reflexive-transitive closure of ⟶ and [x] the class of an x ∈ R with respect to the equivalence generated by ⟶. x is called irreducible (or in normal form) if there is no y ∈ R such that x ⟶ y. A reduction system can have the following properties:

• Chain Condition: There is no infinite chain x_{1} ⟶ x_{2} ⟶ x_{3} ⟶ ⋯ in R. (Then ⟶ is called terminating or Noetherian.)

• Confluence: ∀w, x, y ∈ R: (w ⟶^{∗} x ∧ w ⟶^{∗} y ⇒ ∃z ∈ R : x ⟶^{∗} z ∧ y ⟶^{∗}

z).

• Completeness: Chain condition and confluence. If a reduction system is complete, normal forms always exist and are unique. See

[3] for further details.

Let Σ be a finite alphabet. Σ^{∗} denotes the free monoid over Σ and □ the empty word. A semi-Thue system (STS) on Σ is a subset S ⊆ Σ^{∗} × Σ^{∗}. Each element (u, v) of S is called a rule and written in the form u ⟶ v. An STS S defines a reduction relation ⟶ on Σ^{∗} by xuy ⟶ xvy ⇔ (u, v) ∈ S.

Let OV (u) = {x ∈ Σ^{∗} | ∃y, z ∈ Σ^{∗} : u = yx = xz}\{□, u} be the set of non-trivial self-overlaps of u ∈ Σ^{∗}. Generalizing results of Book [2], Otto and Wrathall [6], one obtains the following.

Theorem. Let the single-rule STS u ⟶ v satisfy the chain condition, and let u = u_{0}u_{1}u_{2} … u_{k} (k ≥ 0), such that OV (u) = {u_{1}u_{2} … u_{k}, u_{2} … u_{k}, …, u_{k}}. The STS is confluent if and only if one of the following two conditions is satisfied:

(a) v has u_{1}u_{2} … u_{k} as a self-overlap, or

(b) there is a j ∈ {1, 2, …, k + 1}, such that v = u_{j}u_{j+1} … u_{k} (for j = k + 1: v = □) and u = u_{j−1}^{j}u_{j}u_{j+1} … u_{k}.

For the case v = □, this means that u must be a power of a word y without proper self-overlap [2]. The classes |w| of such complete systems y^{r} ⟶ □ are deterministic context-free languages [1]. One can show that the unambiguous grammar (Σ ∪ {S}, Σ, P, S) with P = {S ⟶ □, S ⟶ (a_{1}Sa_{2}S … a_{k−1}Sa_{k})^{r}S}, where y = a_{1}a_{2} … a_{k} (a_{i} ∈ Σ), generates |□|. (There is a similar grammar for the general case |w|.) From this presentation it follows that the structure generating function S(z) (cf. [4]) of |□| is the unique solution of the equation S(z) = 1+z^{rk}(S(z))^{r(k−1)+1} in ℤ[[z]], which is a variant of the well-known “trinomial equation” (T): A(x) = 1 + x(A(x))^{t} (t ∈ ℕ). (T) has the unique solution A(x) = ∑_{n=0}^{∞} a_{n}x^{n} with a_{n} = \frac{1}{n(t−1)+1} \binom{tn}{n} (the a_{n} having a lot of combinatorial interpretations, see, e.g., [5]). This is usually proved by the Lagrange inversion formula, but it can also be deduced from the set equation [a^{p}] = [a^{p−1}]a+[a^{p+k−1}]b for the special STS a^{k−1}b ⟶ □. The enumeration of words in the classes [w], w irreducible, can be carried out in the same manner.

References

[1] R. V. Book, Confluent and other types of Thue systems, J. ACM 28 (1982), 171–182.

[2] , A note on special Thue systems with a single defining relation, Math. Systems Th. 16 (1983), 57–60.

[3] G. Huet, Confluent reductions: abstract properties and applications to term rewriting systems, J. ACM 27 (1980), 797–821.

[4] W. Kuich, On the entropy of context-free languages, Information and Control 16 (1970), 173– 200.

[5] , A context-free language and enumeration problems of infinite trees and digraphs, J. Combin. Theory Ser. B 10 (1971), 135–142.

[6] F. Otto and C. Wrathall, A note on Thue systems with a single defining relation, Math. Systems Th. 18 (1985), 135–143.

Technische Universität Clausthal, Institut für Mathematik, Erzstr. 1, D-3392 Clausthal–Zellerfeld