数理解析研究所講究録
第 848 巻 1993 年 177-187

177

The algorithms for deciding some properties offinite convergent string rewriting systems
Guo Mingchao, Li Lian
Lanzhou University, Gansu, China
Abstract. The following problems are decidable in $O(mn^{2})$ time for convergent system on alphabet , where $m=|A|,$ is the length of $R,$ $i.e.$ ,the sum of all length of words appeared in .
$R$

$A$

$n$

$R$

(1) Is the monoid presented byfinite ?
(2) How many elements in the monoid presented by if it is finite ?
and a sofyware is given to decide these properties and some other properties
for such monoid.
$R$

$R$

1. String rewriting systems

Let be an alphabet, a subset ofwhich is called the set pf string rewritingrules. Elements in has the the form of $(x, y)$ . Let $>be$ an order which satisfies that if$x>y$ , then for arbitrary strings $w,$ $z\in R,$ $wxz>wyz$ . A string rewriting system $RS$ is adouble $(A, R)$ where is an alphabet and is a set of rewriting rules. An oriented $RS$
is triple $(A, R, >)$ , for each rule $(x, y)$ in , we have $x>y$ and denote as $xarrow y$ .
Some reduction relation on
is defined as follows:
$A$

$R$

$A^{*}\cross A^{*}$

$R$

$A$

$R$

$R$

$A^{*}$(a)$w_{1}arrow w_{2}$ffl there exists$z_{1},$ $z_{2},$$(x, y)\in R$ , such that $w_{1}=z_{1}xz_{2},$ $w_{2}=z_{1}yz_{2}$$(b)arrow^{*}$

is the reflexive $transiti\dot{v}e$ closure $ofarrow$ .

$(c)rightarrow^{*}$

is the symmetric closure

A word$w$$ofarrow^{*}$.

.

is called irreducible if there is no word$z$

such that $warrow z$ .

An $ORS$ is Noetherian if there is no infinite chain $w_{1}arrow w_{2}arrow\cdotsarrow w_{n}arrow\cdots$ .
An $ORS$ is confluent iff for arbitrary words
such that.
$rv_{1}arrow^{*}z,$$w_{1},$ $w_{2},$ $w_{1}rightarrow*w_{2}$, there exists a ward$z$$w_{2}arrow^{*}z$

An $ORS$ is convergent iff it is Noetherian and confluent.
is a generating relation of a monoid on alphabet
ence containing , then$G$$A$. Let be the minimum congru$\rho$$G$$M\cong A^{*}/\rho$.

when is reviewed as a set of rules, so we callis the monoid defined by$ORS$ . When $ORS$ is convergent, the following properties are decidable [2].

$p=rightarrow^{*}$$G$$A^{*}/rightarrow^{*}$

178(1) Is the monoid presented by$R$finite ?

(2) How many elements are there the monoid presented by$R$

if it is finite ?

(3) How is the multiplication table of the monoid presented by$R$created ?

(4) Is it a trivial monoid ?
(5) Is it a group ?

(6) Is it commutative ?
(7) Is it a free monoid ?

Whether an $ORS$ is convergent is decidable [2]. If the $ORS$ is not convergent, wecan use the Knuth-Bendix convergent procedure to get an equivalent one in most case
(But there indeed exists some $ORS$ that has no co.nvergent system). In the following
discussion, we always suppose that $ORS$ is convergent. About the properties of (4), (5),(6) and (7), F. Otto has given some algorithms in polynomial time $[2, 4]$ . Now we turn
our attention to the properties of (1), (2) and (3).
2. The decision of Properties (1), (2) and (3).

The number of equivalent classes is the number of elements in monoid when the $ORS$ isconvergent. And every class has exactly one irreducible element. The set of all irreduciblewords $IRR(R)$ is a regular language which can be accepted by a finite state automaton.
The cardinal of $IRR(R)$ is equal to get the cardinal of monoid defined by the rewriting
system. So we can count the cardinal to get the cardinal of the monoid. Some details are
as follows.
Denote suffix $(x):=\{v|x=uv, u, v\in A^{*}\}$$dom(R):=\{x|(x, y)\in R\}$prefix $(R):=\{x|l=xy, y\in A^{+}, l\in dom(R)\}$ .
We construct the automaton $FSA$ recognizing $IRR(R)$ . The states of $FSA$ are thosewords which are proper prefixs of the left-side of the rules inRwheree is the start state.
All the states are final states. We denote the state set as . The transitive function isconstructed by following way.
$F$$\delta(w, a)=\{\begin{array}{l}undefi nedsuffi x(wa)\cap dom(R)\neq\emptyset ss\in L=\{x|x\in suffi x(wa)\bigcap_{>}prefi x(R)\}andy\in L-\{s\},|s||y|\end{array}$

Lemma 1: $IRR(R)=L(FSA)[5]$ .

$\delta$

179
Theorem 2: Let $FSA(Q, A, \delta, e, F)$ be the automaton on alphabet constructed asabove, Then for the state $w\in F$ and $a\in A$ , to determine the next stateneeds$O(n)$ time, where $n=|R|$ .
$A$$\delta(w, a)$

Proof: The key to determine the next state$\delta(w, a)$is to find the suffix of $wa$ suchthat $wa$ is exactly a prefix of the left-side of a rule in .
Suppose the word is the left-side of a rule, $S(u)=$ {The longest word in prefix of.
and suffix of $wa$ }; obviously,
If itself is a suffix of $wa$ , thenis undefined, otherwise for arbitrary in theleft-side of the rule, the problem to find the longest word $S(u)$ is a substring recognizing
problem [1]. It takes $O(|u|)$ time. When runs all the left of the rule in , it needs $O(n)$time.
$R$

$u$

$S(u)\neq\emptyset$$u$$\delta(w, a)$

$u$

$u$

$R$

$u$

Theorem 3:$FSA$ as

above can be constructed in $O(mn^{2})$ time, where $m=|A|$ ,$n=|R|$ .

Proof: The automaton has been constructed if we have the transitive function. For

every state and $a\in A$ , the next state
can be determined in $O(n)$ steps. The
number of states is less than , so for all states and some $a\in A$ , to determine the nextstates needs $O(n^{2})$ time. When a runs through , it takes $O(mn^{2})$ .
$\delta(w, a)$$w$

$n$

$A$

Theorem 4: The monoid presented by$IRR(R)$ has a circle.

$R$

is infinite iff the automaton $FSA$ recognizing

Proof: If the monoid is infinite, then there is an element $w\in IRR(R),$ $w|>n$ , whereis the number of the states of $FSA$ . For $FSA$ has only states, so must pass somestate twice at least, $i.e.,$ $FSA$ contains a circle. Conversely, if $FSA$ has a circle, thereexist states
and a word $w=xyz$ , which satisfies
$n$

$w$

$n$

$q,$

$r$

$\delta(e, x)=q$,Then FSA accepts all the words like$\delta(q, y)=q$$xy^{k}z$,$\delta(q, z)=r$.

. The monoid presented byAlgorithm 5:
INPUT: A finite automaton recognizing $IRR(R)$ on alphabet

begin$s_{1}$$:=\{e\}$;for $i:=1$ tobegin$S_{2}$$n$do$:=\emptyset$;$S_{2}$$:= \bigcup_{p\in S_{1},a\in A}\delta(p, a)$$S_{1}$$:=S_{2}$;;end;
Ifend.

$S_{2}=\emptyset$then OUTPUT: The monoid is finite
else OUTPUT : The $mo$ noid is infinite$A$.

$R$is infinite.

180
Theorem 6: The algorithm above needs $O(mn)$ time to determine the existence ofcircle, where $m=|R|$ and is the number of states in automaton $FSA$ .
$n$

Proof: clearly.
If the monoid presented by is finite, then $FSA$ recognizing $IRR(R)$ has no circle,
denote the number of words accepted by state as $N(q)$ , obviously, $N(e)=1$ .
$R$$q$$R(q)=\{p|\exists a\in A : \delta(p, a)=q\}$$T(q,p)=|\{a\in A|\delta(p, a)=q\}|$.

.

Theorem 7: Let $FSA(Q, A, \delta, e, F)$ be a automaton recognizing $IRR(R)$ which has nocircle. Then it satisfies(a) For each$q$$q=eq\neq e$$N(q)=\{\begin{array}{l}1\sum_{p\in R(q)}N(p)T(p,q)\end{array}$(b) $|IRR(R)|= \sum_{q\in F}N(q)$Proof: (a). denote $L(q)$ as the path length from start state to the state . Now let us$q$induce on $L(q)$ .
$L(q)=0$ , then is start state. It is obviously that $N(q)=1$ .
If $L(q)<t$ , the result is true. Let $L(q)=t$ , every path from to must pass uniquelya state in $R(q)$ , by the induction, the number of word from to is $N(p)$ . So thenumber of words passing from to is $N(p)T(p, q),$ $i.e.,$ $N(q)= \sum_{p\in R(q)}N(p)T(p, q)$
$q$

$e$

$q$

$e$

$p$

$e$

$p$

$p$

$q$

(b) is clear.

Now we give the algorithm for calculating the order of the monoid.

Algorithm 8:
INPUT: Automaton $FSA(Q, A, \delta, e, F)$ accepting $IRR(R)$ .
begin$U$$:=\{e\}$$S$ $:=$;$:=1$ ;

$N\{e\}${, Edo$q|\exists p\in U$

While$S\neq\emptyset$

begin

$a$

$A$:

$\delta(p,$$a)=q$ };;for each $q\in S$ do
if $R(q)\subseteq U$ thenbegin $:=U\cup\{q\}$ ;$T:=\emptyset$$U$$N(q)$$:= \sum_{p\in R(q)}N(p)T(p, q)$;181
$T:=T\cup\{q\}$ ;

$S$

end;
$:=T$ ;end;end.
OUTPUT : order:$= \sum_{q\in F}N(q)$.

Theorem 9: The algorithm 8 takes $O(mn^{2})$ time where $m=|A|,$states of the automaton.

$n$is the number ofFor constructing the multiplication table from a monoid, we can calculate the irreducible words of monoid at first. Denote $W(p)$ $:=\{x|\delta(e, x);=p\}$ . The algorithm issimilar with algorithm 8 and given as follows:

Algorithm 10:
INPUT: A automaton $FSA(Q, A, \delta, e, F)$ recognizing $IRR(R)$ ,where $IRR(R)$ is finite.
beginW(e): $=\{1\}$ ;$:=\{e\}$ ;$U$$S$$:=\{q|\exists p\in U, a\in A : \delta(p, a)=q\}$While$S\neq\emptyset$

begin;

do;for each $p\in S$ do
if $R(p)\subseteq U$ then$T:=\emptyset$

begin $U:=U\cup\{p\}$ ;$W(p):=$$\cup$$\{xa|xEW(q), \delta(q, a)=p\}$ ;$p\in R(p),a\in A$$T$$:=T\cup\{p\}$;

end;
$S$

$:=T$ ;

end;

end.

OUTPUT: $IRR(R):= \bigcup_{p\in F}W(p)$ .
Theorem 11: If monoid presented by is finite, we can calculating $IRR(R)$ in polynomial $O(mn^{2}t)$ time, where $m=|a|,$ is the number of states of $FSA,$ $t=|IRR(R)|$ .
$R$

$n$

If the order of elements is and the length of longest element is , to calculate theirreducible words for all production of pairwise elements needs $O(n)$ time. For there is alinear time algorithm to get the irreducible word from a given word with length $2n[2]$ .
So we can create the multiplication table in $O(nt^{2})$ time.
$t$

$n$

182
If the order of the monoid to large, or it is infinite, to construct yhe whole multiplication table is impossible. But we can create a finite block of the table when the concreteelements is given. The following algorithm give finite elenents which lengths are less than
$K$ in a monoid.

Algorithm 12:
INPUT: $FSA(Q, A, \delta, e, F)$ recognizing $IRR(R)$ , an integer $k>0$ .

beginS: $=\{e\}$ ;$W$ $:=\{1\}$

While
begin

;

$(S\neq\emptyset)$$T:=\emptyset$and (loop $<k$ ) do;

loop: $=Ioop+1$ ;For each $(x, q)\in S$ do$:=\{(xa,p)|\delta(q, a)=p, a\in A\}$begin
Ifthenbegin $W:=W\cup\{y|(y,p)\in M_{(x,q)}\}$ ;$:=T\cup M_{(x,q)}$ ;end;$:=T$ ;
$M_{(x,q)}$$M_{(x,q)}\neq\emptyset$

$T$

$S$

end;

OUTPUT: If
then $IRR(R):=W$$W$
else
is a irreducible words set whose element’s length is less than .
$S=\emptyset$$k$When $|R|=1$ , then algorithm 12 takes $O(k)$ time. When $|A|>1$ , then it takestime.

$O( \frac{m^{k+1}-1}{m-1})$

3. Some examples about monoid presented by rewriting systems
Based on the discussion above and $[2, 4]$ . A software is designed and works well. It
can get a convergent system from a generated relation and decide the properties of 1 to7. The following are examples running on the software.

183
1.

GeIierated relation :$R=${aaaab $=ba$$bbb=1$aaaba $=b$aabab $=baba$ }$babb=aaaa$$baa=ab$aaaaaa $=babab$ababa $=bb$ $aabb=bba$
Lexicographical order
Convergent system:$R=$ {aabab $=baba$$aabb=bba$ ababa $=bb$ $bbab=aa$ aaaaaa $=babab$$baa=ab$ aaaba $=b$ $babb=aaaa$ $bbb=1$ aaaab $=ba$ }Properties :$bbab=aa$trivial:finite:order:
commutative:
free monoid:group:

NOYES
21
NONO
YES

184
2.
Generated relation :$R=$ { $abb=aa$
abababababab $=b$ $ab=ba$ }Lexicographical order
Convergent system:$R=$ { $ba=ab$aaaaaaaa $=b$ $abb=aa$ $bbb=ab$ }Properties:

trivial:finite:order:
commutative:
free monoid:group:

NOYES
19YES
NONO

185
3.
Generated relation:$R=$ {baba $=abab$cbacbab $=bcbacba$
Lexicographical order
Convergent system:
is convergent.
Properties:$cbcb=bcbc$$ca=ac$$R$trivial:finite:commutative:
free monoid:group:

NONO
NONO
YES

A finite multiplication table as following:$=======Semigro$ up Multiplication Table $========$$aa=1$$bb=1$$cc=1$}

186
4.
Generated relation:$R=\{cc=1$$bb=1$$aa=1$$ca=ac$$bab=aba$

cbacbacbcb

bcbcb cbcbac $=bcbcba$ cbacbacbacba $=bcabacbacbacb$ }Lexicographical order
Convergent system:
is convergent.
Properties:$R$

trivial:finite:order:
commutative:
free monoid:group:NOYES
120NONOYES

A finite multiplication table as following:$=======Semigroup$ Multiplication Table $========$$=$

bcbacbacbc cbcbc

$=$

187
References[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer algorithms.
Addison Wesley, 1974.
[2] B. Benninghofen, S. Kemmerich, and M. Richter. Systems of Reductions. Spring-Verlag,

1987.
[3] J. E. Hopcroft, and J. D. Ullman. Introduction to automate theory, language and computation. Addison Wesley, 1979.
[4] Paliath Narendran, and Friedrich Otto. Elements of finite order for finite weight-reducing
and confluent thue systems. Acta Informatica, 25:573-591, 1988.
[5] Wang Shuiting. Construction of the multiplication table of the semigroup and its complex
degree. J. of Lanzhou University, 28:38-42, 1992.