数理解析研究所講究録 1222 巻 2001 年 98-104

98

Linear Markov Properties and Undecidability
東邦大学理学部

小林ゆう治

京都産業大学理学部

勝良

昌司(Yuji Kobayashi)(Masashi Katsura)

Introduction and Preliminaries

1

Afinitely presented monoid $M$ is given by a finite alphabet (a finite set of generators) and afinite
rewriting system (a finite set of defining relations). Even though $M$ is defined by affiite set of data,
many algebraic properties of $M$ are undecidable. In fact, for any Markov property $P$ of monoids,
there is no algorithm to decide whether agiven finitely presented monoid satisfies $P$ (Markov [4]).
In the proof of this undecidabilty result, amonoid with unsolvable word problem was used. So theundecidabilty of Markov properties was proved in aclass of monoids that contains monoids with

unsolvable word problem.
Sattler-Klein [8] proved that some of Markov properties are still undecidable in aclass of ffiitely
presented monoids with solvable word problem (see also [4]). She employed her monoids, which she
used to show the divergence phenomena of the completion procedure ([6], [7]). Actualy, for any
parameterized byrecursively enumerable language , she constructed finitely presented monoids
has word problem solvable in polynomial
words with the following properties. The monoid
time, and it is trivial if $w\in L$ , on the other hand it is infinite, non-commutative, non-free etc. if. Thus, such properties as finiteness of monoids are undecidable in the class of monoids withword problem solvable in polynomial time.
In this paper we improve her results in two directions. First we improve the results bom polynomial
to linear time. &0ndly we give asystematic my to carry over Markov’s proof of undecidabilty toprove that any Markov property related to linear
our restricted class of monoids, so that wecomplexity in some sense is undecidable for finitely presented monoids with word problem solvable inlnear time. In fact, most of ordinary Markov properties are Markov properties in our sense.
Let be a(finite) alphabet and let ’be the &ae monoid generated by Z. The empty word,,. For aword
which is an identity element of the monoid, is denoted by 1. Set. An element
denotes its length. Arewriting system is aset of ordered pairs $(u, v)$ with, we write $arrow Ry$ if $=x_{1}ux_{2}$ and$(u,v)$ ofis oeUd arule and written as $uarrow v$ . For $x,y$is the reflexive transitive closure of$=X1VX2$ for someand $uarrow v\in R$. As usual,is an ancestor of and is adescendant of .
. Ifis the that congruence generated by . The monoid
The reflexive symmetric transitive.The word problem for $M=M(\Sigma,R)$$M(\Sigma,R)$ preented byis the quotient monoid, decide if $=y$ in $M$ . Two systems
is the following decision problem: Given two words ,, that is, and $ff$ define the same quotient monoid
and $K$ over are equivalent$S_{w}$$L$$S_{w}$$w$$w$$\not\in L$$\mathrm{m}$$\Sigma$$\Sigma$$\Sigma^{+}=\mathrm{Z}$$u,v\in \mathrm{Z}^{*}$$\in\Sigma.$$R$$x_{1},x_{2}\in\Sigma^{*}$

$y$

$x$

$arrow R^{\cdot}$

$x$

$x$

$y$

$R$

$\mathrm{d}\mathrm{o}\mathrm{e}\mathrm{u}\mathrm{r}\mathrm{e}rightarrow.R$$\Sigma./rightarrow.R$$(\mathrm{Z}, R)$$x$$\Sigma$$x$$arrow.R$$y$$y_{1}x$$x\in\Sigma’$$\backslash \{1\}$

$R$

$|x|$

$arrow R$.

$\mathrm{i}\mathrm{f}rightarrow_{R}^{*}=rightarrow_{R}^{2},$$R$$y\in\Sigma.$

$x$

$R$

99
and
When the system is fixed and there is no confusion, we simply write
respectively.
Arewriting system $R$ is noetherian (terminating) if there is no infinite sequence$R$$arrow^{2}$$arrow,$$rightarrow^{2}$for$arrow R$,$\prec_{R}^{\mathrm{r}}\mathrm{a}\mathrm{n}\mathrm{d}rightarrow_{R}^{l}$$x_{1}arrow x_{2}arrow\cdotsarrow$. It is confluent if any words

with common ancestor have acommon descendant.
if no rule
complete if it is both noetherian and confluent. Aword is
Asystem isfrom can be applied to it. An irreducible descendant of is called a normal form of . If $R$ is, there is aunique normal form which is denoted by . Moreover, for twocomplete, for any. Hence, the word problem for afinite complete system,
if and only ifwords
is solved by anormal form algorithm, namely, given words and we compute the normal forms
and of and and check whether they are identical.
is complete if and only if all the critical pairs are
It is well known that anoetherian system, $u_{2}arrow v_{2}\in R$
of words is acritical pair, if there are rules
resolvable. Here, apair
ing holds:
such that one of the(are different), or,(i) $u_{1}=xu_{2}y$, $z_{1}=v_{1}$ $z_{2}=xv_{2}y$ for some.
, $z_{2}=xv_{2}$ for some $x,y$ ,(ii) $u_{1}=xz$ , $u_{2}=zy$ ,is resolvable if and have acommon descendant.
Acritical pair
if $u>v$ for all.Arewriting systemis
We fix acompatible well-0rder$uarrow v\in R$ . If
complete,
we can applyis -reducing, it is noetherian. If afinite system is not-Bendix completion procedure [3], see also [1]) to get acomplete
the completion procedure (theso that becomes -reducing. If there is acritical pairsystem equivalent to . First, orient$(x,y)$ , compute normal forms
and of and respectively (we can compute them because $R$ is), add the(resp.
, then the critical pair is resolved. If
finite and noetherian). If) to the system. Repeat this until all the critical pairs are resolvable. This
(resp.
rule
procedure may not terminate even if the original system is finite. It terminates if and only if there-reducing finite complete system equivalent to $R$, and if it terminates, it gives such asystem.
is-reducing infinite complete system
Even if the procedure does not terminate, it gives, in the Omit,$x_{n}arrow\cdots$$R$’$x,y\in\Sigma$$|.\mathrm{n}\mathrm{e}d\mathrm{u}\dot{\alpha}bk$$\mathrm{c}\mathrm{a}\mathbb{I}\mathrm{d}$

$R$

$x$

$x$

$x\in\Sigma^{*}$$x,y\in\Sigma^{*}$$\hat{x}$$xrightarrow^{*}y$$\hat{x}=\hat{y}$

$R$

$x$

$\hat{x}$$\hat{y}$

$x$

$y$

$y$

$R$

$(z_{1}, z_{2})$$u_{1}arrow v_{1}$$\mathrm{f}\dot{\mathrm{o}}\mathrm{U}\mathrm{o}\mathrm{w}$$x,y\in\Sigma^{*}$$z\in\Sigma^{+}$$z_{1}=\mathrm{v}\mathrm{i}\mathrm{y}$$(z_{1},z_{2})$$u_{1}arrow v_{1},$ $u_{2}arrow v_{2}$$z_{2}$$z_{1}$$R$$<\mathrm{o}\mathrm{n}\Sigma.$$R$$<- \mathcal{M}ucing$

$R$

$<$

$Knu\theta\iota$

$R$

$R$

$R$

$\hat{x}$$\hat{y}$

$x$

$<$

$y$

$\hat{y}>\hat{x}$$\hat{x}>\hat{y}$$\hat{x}=\hat{y}$$\hat{y}arrow\hat{x}$$\hat{x}arrow\hat{y}$$R$$\mathrm{a}<$$\mathrm{a}<$equivalent to $R$ .

2Linear Markov properties
Let
be the class of finitely presented monoids with word problem solvable in linear time. By
aproperty $P$ of monoids, we mean an invariant property of monoids, that is, if amonoid $M$ satisfies$P$ , every monoid isomorphic to $M$ satisfies $P$ .
Aproperty of monoids is called aMarkov property relative to linear compkity (a linear Markov$C_{1}$$P$

property for short), if(i) there is amonoid(ii) there is amonoid$M_{1}$$M_{2}$

other words, any monoid ininin$C_{1}$

with property $P$ , andwith property $P$ , inthat is not embeddable in any monoid in.
does notcontaining asubmonoid isomorphic to$C_{1}$$C_{1}$$C_{1}$$M_{2}$$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\Psi P$

Example. (1) Left-cancellativity is linear Markov. So the following stronger properties are also linear

100
being agrouptrivialty etc.
(2) Satisfying some fixed nontrivial (quasi-)identities is linear Markov, for$\bullet$cancellativity$\bullet$$\bullet$freeness$\bullet$:$\alpha \mathrm{a}\mathrm{n}\mathrm{p}\mathrm{l}\mathrm{e}$commutativity idempotency nilpotency finiteness etc.
(3) Negation of having an element (subset) with some local properties is linear Markov. For
example, the negations of the foUowing.
having anontrivial idempotent containing anontrivial subgroup etc.
$\bullet$$\bullet$$\bullet$$\bullet$$\cdot$$\bullet$$\bullet$Here we state our main theorem. Asketch of the proof is given below but the details$\mathrm{w}\mathrm{i}\mathrm{u}$appearin [2].
Theorem 2.1 Any linear Markov property is undecidable for finitely presented monoids with word
problem solvable in k.oear time.

3Rewriting systems simulating Turing machines
For the proof of the main theorem, we need to consider aTuring machine accepting anon-recursive
language and arewriting system simmulating the machine. Let be recursively enumerable language
be asingle-tape deterministic Turing machineover afinite alphabet . Let TM
accepting given as follows. is the set of tape symbols, $Q=\{\infty, q_{1}, \ldots, qk\}$ is the set of states,.
is the Mting state. We suppose $k\geq 1$ and aet $q$
the initial some and, where is the blank symbol outside . The transition function is amappingLetLi, where and $R$ are the symbols for the right and left moves of the6: $q$$L$$=(\Gamma, Q, \mathrm{r}, q_{k},\delta)$$\Gamma$$L$$\Gamma$$=Q\backslash \{q_{k}\}$$q_{k}$$\mathrm{r}\mathrm{i}\epsilon$$\Gamma_{b}=\Gamma$$b$$\{b\}$$\Gamma$$L$$\mathrm{x}\Gamma_{b}arrow Q\mathrm{x}\Gamma_{b}\mathrm{x}\{R L\}$head respectively.
. Let
the one stop
and $q\in Q$ is aconfiguration of
Aword $xqy$ with, that is,computation relation on the set of configurations of, $q\in q$ and $t$ $\in Q$ ,, $x,y$forif(a) $xqay\vdash x,$, $q\in q$ and $t$ $\in Q$ , and,
if $\delta(q,a)=(\phi,d, L)$ for $a,a’,c$(b) xcqayor (b) for $x,x’,\sqrt\in\Gamma i$ , $q\in q$ and $t$ $\in Q$ .
if $xqb\vdash dtt\mathrm{w}$(c) $xq$
If aconfiguration $d\phi J$ is obtained&0m aconfiguration $xqy$ through computation steps, we write
after afinite number ofstop in state. Given aword in as input TM$xqy$
computation steps, and on the other hand given aword not in , TM will not stop and run forever;$\mathrm{T}\mathrm{M}$$x,y\in\Gamma_{b}^{*}$$\vdash \mathrm{d}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}$$\mathrm{T}\mathrm{M}$$y$$a,a’\in\Gamma\iota$$6(\mathrm{q},\mathrm{a})=(\phi,a’,R)$$\vdash x’\omega’y$$\in\Gamma \mathfrak{y}$$\vdash d\phi\sqrt$$\in\Gamma i$$x,y\in\Gamma_{b}^{*}$$(\mathrm{a})$

$n$

$w$

$\vdash^{n}t\phi\sqrt$$L$$\mathrm{w}\mathrm{i}\mathrm{U}$$q_{k}$

$L$

$w$

$L=$

.

{

$w\in\Gamma^{\cdot}|\mathrm{g}w$$\vdash’ xqy$

for some ,.

$x$$y\in\Gamma_{b}^{*}$},. Moreover, without loss
denotes the reflexive transitive closure of , that is,whereof generalty we may assume that the head of TM never moves to the left of the initial position.
arewriting system simulating the machine TM in some way. Let
Now, we$Q\cup\{H,E,A,\overline{A},B,\overline{B},O\}$ , where $H,E$ ,, are new letters. Below, $a,a’$ and are arbitrary,
letters in , and $t$ are arbitrary states in , and for aset $X$ of words, $Xarrow O$ denotes the collectionof rules $xarrow O$ for $x\in X$ . The system consists of the following rules:$\vdash$$\vdash$$—=\Gamma_{b}\cup$$A,\lambda$

lb :$\mathrm{a}\mathrm{J}$$arrow\overline{A}a$$B,\overline{B}$

$Q$

$q$

$T$

la :

$= \bigcup_{1*=0}^{\infty}\vdash^{n}$$T$$\dot{\mathrm{p}}\mathrm{v}\mathrm{e}$$\Gamma\iota$$\vdash$,,$H\overline{A}arrow HA$

$O$

$c$

101
: $Aaarrow aA$ ,
,
la’ :
’
: $B-EEarrow BbE$,: $aBarrow Ba$,
$1\mathrm{c}$$\overline{B}aarrow a\overline{B}$$1\mathrm{b}$$1\mathrm{c}’$for $(q,a,\phi,a’,R)\in\delta$ ,:for $(q,a,\phi,a’,L)\in\delta$ ,: $aAq_{k}B$ $arrow Aq_{k}B$ , $Aq_{k}Ba$ $arrow Aq_{k}B$ ,: $HAq_{k}BE$ $arrow HE$ ,: $HEEarrow HE$ ,
,
,
for
,
:
,
:
: $\{AE,HB\}arrow O$,
,
:
for
.
:
for

$2\mathrm{a}:AqBaarrow\overline{A}a’\phi\overline{B}$$2\mathrm{b}$$3\mathrm{a}$$3\mathrm{b}$$3\mathrm{c}$$cAgEaarrow\overline{A}\phi ca’\overline{B}$$\sigma Oarrow O$$4\mathrm{a}:O\sigmaarrow O$$4\mathrm{b}$$4\mathrm{c}$$4\mathrm{d}$$4\mathrm{e}$$4\mathrm{e}’$$\sigma\in---$$\{A,\overline{A},B,\overline{B}\}^{2}\backslash \{\overline{A},B\}\{A,\overline{B}\}arrow O$$\{\mathrm{g}\mathrm{B}\cdot \mathrm{V}, q\phi,\overline{B}q, q\overline{A}, \mathrm{a}\mathrm{A}, \mathrm{q}\mathrm{B}\mathrm{J}\}$$\sigma Harrow O$$E\sigma$$arrow O$$\sigma\in---$$arrow O$$\sigma\in\underline{=}\backslash \{E\}$

Lemma 3.1 The system $T$ is complete.

The following lemma shows how the system $T$ simulates
Lemma 3.2 Let $x,y$ , $x’,\phi$$\in\Gamma_{b}^{*}$$\mathrm{T}\mathrm{M}$, $q,f$ $\in Q$ and $n\geq 0$ . If xqyb.

$\vdash^{n}x’\phi y’$, then$HxAqy \overline{B}E^{t}\prec_{T}^{*}Hx’A\oint y’\overline{B}E^{t-n}$

for $t>n$ . If, moreover,$t$ $=q_{k}$and $t>n+1$ , we have
$HxAqy\overline{B}E^{t}\prec_{T}^{*}$HE.

For each word
we consider the rule
$HAq0w\overline{B}EarrowO$:.
$w\in\Gamma^{*}$$0_{w}$

Definition 3.3 Let$w\in\Gamma^{*}$. Define the system$T_{w}$

by adding rule$T_{w}=T\cup\{0_{w}\}$and let $N_{w}=M(_{-}^{-}-,T_{w})$ be the monoid presented by

The system$HAq_{0}w\overline{B}E^{t+1}$

for some ,$x$$0_{w}$

to $T$;,$(_{-}^{-}-,T_{w})$.

is noetherian but not complete any more. In fact, aPPlying ruleto the. word
, which is reduced to . On the other hand, if
for $t>0$ , we obtain, then by Lemma 3.2 we have $HAq0w\overline{B}E^{t+1}\prec_{T}^{*}HxAqy\overline{B}E$. Thus,$T_{w}$$0_{w}$$OE^{t}$$O$$q_{0}wb^{t}\vdash^{t}xqy$$y\in\Gamma_{b}^{*}$. O.

$HxAqy\overline{B}Erightarrow_{T}^{*}$

Here, if $q=q_{k}$ , then

$HxAqy\overline{B}EEarrow_{T}^{2}$(3.1)

HE by Lemma 3.2. Hence, we see$HE\mapsto_{T_{v}}^{*}$

O.

(3.2)

102
and $q(t)\in q$ such thatis not in , then for any $t>0$ , there uniquely exist, because TM is deterministic. The words on both sides of (3.1) are -irreducible.
So, to make the system complete, we add the rule
: $Hx_{t}Aq(t)\mu\overline{B}Earrow O$
for every $t>0$ .
, and (3.2)
for some $n>0$ and some ,On the other hand, if is in , thenNow, if$x_{t},y_{t}\in\Sigma^{*}$

$L$

$w$

$T_{w}$$rwb^{t}\vdash^{t}x_{t}q(t)y_{t}$$0_{w}^{t}$

$L$

$w$

$q_{0}wb^{n}\vdash^{n}xq_{k}y$$x$$y\in\Gamma_{b}^{*}$

holds. To make the system complete we add the rule$4\mathrm{f}:HEarrow O$.

In this case we remove rule , because it is aconsequence ofequivalent toIn this way we have the complete system$3\mathrm{c}$$\hat{T}_{w}$Lemma 3.4(I)If$w$.

$4\mathrm{f}$$T_{w}$

in the following lemma.

is not in ,$L$$\hat{T}_{w}=T_{w}\cup\{0_{w}^{t}|t=1,2, \ldots\}$

infinite complete system equivalent to .
(2) If is in and is the positive integer such thatis an$T_{w}$

$w$

$L$

$n$

$rwb^{n}\vdash^{n}$xqky for $x,y\in\Gamma i$ , then$\hat{T}_{v}=(T_{w}\backslash \{3\mathrm{c}\})\cup\{\mathrm{O}_{w}^{t}|t=1,2, \ldots,n\}\cup\{4\mathrm{f}\}$is a finite complete system equivalent toCorollary 3.5 A word

$w\in\Gamma$.

is in ,
$L$

$T$

$|.f$

.
and only$.\cdot f$$HE=O$ holds in the motexpid Nw.

An important feature of our construction is stated in the following lemma.
Lemma 3.6 The monoid$\mathrm{S}\ovalbox{\tt\small REJECT} \mathrm{i}\cdot \mathrm{g}$$N_{w}$

has word yobkm solvable in linear time.

we have

has word pmb&m solvable in linear time, and we have the following.
Theorem 3.7 The monoid.
(2) If is in , then $HE=O$ in.
(2) If is not in , then $HE\neq O$ in$N_{w}$

$w$

$w$

$L$

$N_{w}$$L$$N_{w}$

4Embedding lemma and aproof of the main theorem
Let (CJ) be an arbitrary monoid presentation and let $M=M(\mathrm{Z},R)$ . Let
given byoutside and let $x,y\in\Sigma.$ .Consider the system over$\alpha,\beta,\gamma$$S$$\Sigma$$S=\{\alpha x\betaarrow 1, ay\betaarrow\gamma\}$Libe new letters$\Sigma’=\Sigma\cup\{\alpha,\beta,\gamma\}$$\{\sigma\gammaarrow\gamma, \gamma\sigmaarrow\gamma|\sigma\in\Sigma’\}$.

, by $\Phi_{a,y}(M)=M(\Sigma’, R\cup S)$ .
We define amonoid $\Phi_{x,y}(M)$ , which is determined by $x,y$ and.
Let : $Marrow\Phi_{x,y}(M)$ be the morphism of monoids induced by the inclusion$(\Sigma,R)$$\Sigma$$\phi$

is the trivial monoid. If $x\neq y$ in $M$ ,Lemma 4.1 If $x=y$ in $M$ ,$fM$ has word problem solvable in linear time, so does $\Phi.,(\nu M)$ .
$\Phi_{ae,y}(M)$$\phi$$-\rangle$$\mathrm{Z}’$is injective. Moreover,103
Definition 4.2 For a monoid$M=\mathrm{A}\mathrm{f}(\mathrm{C},R)$and a word

$w\in\Gamma^{*}$

we define$\Psi_{w}(M)=\Phi_{HB,O}(M*N_{w})$, that is, the monoid $\Psi_{w}(M)$ is defined over the alphabet
by the relation $R\cup T_{w}\cup S$, wherewith the free product $M*N_{w}$ of $M$ and$\Sigma’\mathrm{u}_{-}^{-}-with$$\Sigma’\mathrm{n}_{-}^{-}-=\emptyset$$N_{w}$$S=\{\alpha HE\betaarrow 1,\alpha O\betaarrow\gamma,\sigma\gammaarrow\gamma,\gamma\sigmaarrow\gamma|\sigma\in\Sigma’\cup\overline{=}\}$.

Theorem 4.3 (I) If $w$ is in , $\Psi_{w}(M)$ is&trivial monoid.
$L$, $\Psi_{w}(M)$ contains $M$ as submonoid(3) If $M$ has word problem solvable in linear time, so does $\Psi_{w}(M)$ .
(2) If $w$ is not in$L$$\cdot$Proof of the main theorem
Once we have Theorem 4.3, the proof of Theorem 2.1 is now standard. Let $P$ be alnear Markov
property. Let
be amonoid inwith the property $P$ and $M$ be amonoid inthat is notembeddable in amonoid inwith $P$ . We choose the recursively enumerable language
to be$\Psi_{w}(M)$nonrecursive. For
let $M_{w}=M_{1}\mathrm{x}\Psi_{w}(M)$ be the direct product ofand. If and$M$ are presented by
,
and
with
respectively,
is presented by,$R_{1}\cup R\cup T_{w}\cup S\cup S’)$ , where$M_{1}$$C_{1}$$C_{1}$$L$$C_{1}$$w\in\Gamma^{*}$$(\Sigma_{1},R_{1})$$M_{1}$$(\Sigma,R)$$\Sigma_{1}\cap\Sigma=\emptyset$$M_{1}$$M_{w}$$( \Sigma_{1}\cup\Sigma’\bigcup_{-}^{-}-$.

$S’=\{\tau\sigmaarrow\sigma\tau|\sigma\in\Sigma_{1}, \tau \in\Sigma’\cup---\}$

It is easy to see thathas word problem solvable in linear time because bothand $\Psi_{w}(M)$ havelinear word problem by Theorem 4.3, that is, $M_{w}\in C_{1}$ . Moreover, if $w\in L$ ,is isomorphic to$M$$\Psi_{w}(M)$becauseis trivial, and otherwise,
contains
as asubmonoid because so does $\Psi_{w}(M)$ .
$P$So,satisfies if and only if is in . This completes the proof of the main theorem.
$M_{w}$$M_{1}$$M_{w}$$M_{1}$$M_{w}$$M_{w}$$w$$L$$\square$

References[1] D. Kapur and P. Narendran, The Knuth-Bendix completion procedure and Thue systems, SIAM
J. Comp. 14 (1985), 1052-1072.

[2] M. Katsura and Y. Kobayashi, Un&\mbox{\boldmath $\alpha$}\dot dable properties of monoids uriffl word problem solvable inlinear time, Theoret. Comp. ScL, to appear.
[3] D.E. Knuth and P. Bendix, Simple word problems in universal algebras, h:J. Leech (ed.) :Computational Problems in Abstract Algebra (Pergaman Press, New York, 1970), 263-297.
[4] A.A. Markov, The impossibility of algorithms for recognizing some properties of associative$\eta s-$terres, Doklady Acad. Nauk SSSR 77 (1951), 953-956.
[5] F. Otto, Unifom decision problems for certain restricted classes of finite monoid-presentations

a survey on recent undecidability results, In: J.M. Howie and N. Ruikuc (ed.): Semigroups andApplications (World Scientific, Singapure, 1998), 152-170-

104[6] A. Sattler-Klein, Divergence jheteomena during completion’ Proc. RTA’91, Lect. Notes Comp.

Sci. 488 (1991), 374-385.
[7] A. Sattler-Klein, A systematic study of infinite canonical systems generated by Knuth-Bendix cornpletion and related proble m, Dissertation, Fachbereich Informatik, Universitit Kaiserslautern,

1996.

.

[8] A. Sattler-Klein, New
results for finitely presented monoids, Proc. RTA’97, Lect.
Notes Comp. Sci. 1232 (1997), 6&82.
$undecda\mathrm{W}^{\cdot}\mathrm{u}$$y$