数理解析研究所講究録
第 1655 巻 2009 年 1-4

1

FINITELY GENERATED SEMIGROUPS WITH SUCH
A PRESENTATION THAT ALL THE CONGRUENCE
CLASSES ARE CONTEXT-FREE LANGUAGES*KUNITAKA SHOJI
DEPARTMENT OF MATHEMATICS, SHIMANE UNIVERSITY
MATSUE, SHIMANE, 690-8504 JAPAN
Abstract In this paper, we investigate finitely generated semigroups with such a presentationthat all the congruence classes are context-free languages.

A monoid $M$ is called finitely generated if there exists a finite set of $X$ and there exists
a surjective homomorphism ofto $M$ which maps an empty word onto the identity
element of $M$ .
$X^{*}$

1. Presentations of monoids

Definition 1.

(1) Let $X$ be finite alphabets and $R$ a subset of
string-rewriting system.
(2) For $u,$ $v\in X_{f}^{*}(w_{1}, w_{2})\in R,$.

$X^{*}\cross X^{*}$. Then$R$is$uw_{1}v\Rightarrow_{R}uw_{2}v$

The congruence
ongenerated
is the Thue congruence defined by .
(3) A monoid $M$ is (finitely)presented if there exists a (finite) set of $X$ , there exists a$\mu_{R}$$X^{*}$

surjective homomorphism$R$$by\Rightarrow R$ofto$R$

and there exists a (finie) string-rewriting system
consisting of pairs of words over $X$ such that the Thue congruenceis the congruence$\phi$$X^{*}$$S$$\mu_{R}$$\{(w_{1}, w_{2})\in X^{*}\cross X^{*}|\phi(w_{1})=\phi(w_{2})\}$.

Definition 2. A monoid $M$ has a presentation with [finite, regular, contex-free] congruence classes if there exists a finite set $X$ and there exists a surjective homomorphism$\phi$of$X^{+}$

to $M$ such that for each words $w\in X^{+},$ $\phi^{-1}(\phi(w))$ is a [finite, regular, contex-free]language.
’This is an absrtact and the paper will appear elsewhere.

2
2. Syntactic monoids of languages and finitely generated presented monoids
the set of words over A. A subset ofDefinition 3 Let be finite alphabets andis defined by $w\sigma_{L}w’(w, w’\in A^{*})$
onis called a language. The syntactic congruence$L$$A^{*}$$A$$A^{*}$$A^{*}$$\sigma_{L}$if and only if $\{(x, y)\in A^{*}\cross A^{*}|xwy\in L\}=\{(x, y)\in A^{*}\cross A^{*}|xw’y\in L\}$ .
is called the syntactic monoid of .
Then a factor monoid$L$$A^{*}/\sigma_{L}$Example 1$A=\{a_{1}, \cdots, a_{n}\}$$L=\{ww^{R}|w\in A^{*}\}$ .

. For any $w=b_{1}b_{2}\cdots b_{r}$ , let $w^{R}=b_{r}\cdots b_{2}b_{1}$ . Let

Then

is a context-free language which is not accepted by any deterministic pushdown
automata.
on .
(2) $Syn(L)$ is the free monoid
(1)

$L$

$A$

$A^{*}$

That is,$\phi$: $A^{*}arrow Syn(L)(w\mapsto\sigma_{L}w)$ is an isomorphism.

Definition 4 Let $M$ be a monoid and $m$ an element of M. The syntactic congruence
on $M$ is defined by $s\sigma_{m}t(s, t\in M)$ if and only if $\{(x, y)\in M\cross M|xsy=m\}=$$\sigma_{m}$$\{(x, y)\in M\cross M|xty=m\}$ .

is called the syntacti monoid of $M$ at $m$ .

The factor monoid$M/\sigma_{m}$Lemma 1. Let

be a language of

$L$

Let

Proposition 1.

$L$$c$$X^{*}$. Thenbe a language ofis a union of$L$and$A^{*}$

Then $Syn(L)=Syn(L^{c})$ .

Theorem 1
is aLet be a language of.
-class in$L$$X^{*}$$L$(2)$xLy\cap L\neq\emptyset((x, y\in X^{*})\Rightarrow xLy\subseteq L$

(3)

$L$

$\phi^{arrow 1}(m)$(Shoji $[S]$ )homomorphism ofof $M$ atthe complement of the set.
$L$in$A^{*}$.

$A^{*}$.

of a homomorphism$m$$\phi$of$X^{*}$

to a monoid $M$ .

Let $M$ be a finitely generated monoid and$\phi$a surjective

to M. For $m$ an element of $M$ , let $L=\phi^{-1}(m)$ .

Then the syntactic monoid $Syn(L)=A^{*}/\sigma_{L}$ of$M/\sigma_{m}$$X^{*}$$X^{*}$

is an inverse image

Theorem 2-classes in. Then the following are equivalent ;(1)$\sigma_{L}$$L^{c}$$\sigma_{L}$$L$

is isomo rphic to the syntactic monoid.

3. Finitely generated semigroups with such a presentation that all thecongruence classes are context-free languages

3
Theorem 3(Shoji $[S]$ )$A$

finitely generated semigroup

regular congruence classes if and only if for any $s\in S,$

Theorem 4(Shoji $[S]$ )

Let

$S$

$S/\sigma_{s}$$S$

has a presentation withis a finite semigroup.

be a finitely generated semigroup.

has a presentation with finite congruence classes if and only if the following aresatisfied :
Then

(1)

$S$

$S$

has no idempotent.

(2) For any $s\in S,$

Example 2

all of$\sigma_{L}$$S/\sigma_{s}$is a finite nilpotent semigroup with a zero element .
$0$

Let $A=\{a, b\}$ and a context-free language-classes are$\{1\}_{f}${ab},$\{ba\}_{f}e_{n}=\{b^{\rho}a^{p+n}|p\in N\},$$\{a^{n}\},$$c_{n}=\{a^{p+n}b^{\rho}|p\in \mathbb{N}\},$$f_{n}=\{b^{q+n}a^{q}|q\in \mathbb{N}\}$

section. Also, $Syn(L)-\{1\}$ is acongruence classes.
Example 3$\{b^{n}\},$$\mathcal{D}$$L=\{a^{n}b^{n}, b^{n}a^{n}|n\in \mathbb{N}\}$. Then$d_{n}=\{a^{q}b^{q+n}|q\in \mathbb{N}\}_{f}$. Hence $Syn(L)$ has a regular cross--class. $Syn(L)$ has a representation with context-free

Let $A=\{a, b\}$ and: $Sarrow SSS|aSb|\epsilon$
Thengrammar and its accepted language $L(G)$ equals to $\{a^{n}b^{n}|n\geq 0\}$ .
$G$

$G$

is a context-free

The syntactic monoid $Syn(L(G))$ has the presentation $A^{*}/\{ab=1\}$ . It is easily seen that$Syn(L(G))$ has a representation with context-free congruence classes.

Example 4

Let $A=\{a_{1}, \cdots, a_{r}\}\cup\{b_{1}, \cdots, b_{r}\}$ and $F(A)$ the free inverse semigroupover A. Then there exists the canonical map : $A^{*}arrow F(A)(b_{i}\mapsto a_{i}^{-1})$ such that foreach $w\in F(A),$is not a context-free language. Thus,
inverse semigroups do
not have a representation with context-free congruence classes.
$\phi$$\phi^{-1}(w)$$I\dagger ee$

Remark. Even a monogenic free inverse smigroup do not have any representation with
context-free congruence classes.

Result 1
For every finitely generated groupthat is isomorphic to $Syn(L)$ .

$G$, there exists a language$L$of$A^{*}$

such$G$

Result 2$G$

(Muller and Schupp $[MS]$ ) (1) Every finitely generated vertually free group

has a (monoid)-representation with context-free congruence classes.

(2) Conversely, if a finitely generated group $G$ has a (monoid)-representation with context-free congruence classes then$G$

is a vertually free group.

4Theorem 5 Let be a semigroup having a representation with context-free congruenceis a completely (0-) simple semigroup, then both the -classes and theclasses. If-classes of is finite and the maximal subgroup is vertually free.
$S$

$S$

$\mathcal{L}$$S$$\mathcal{R}$

Theorem 6
Let be a finitely generated submonoids of a vertually free group G. Then
is a cancellative monoid having a representation with context-free congruence classes.
$S$$S$

Let

Example 5$A$

be finite alphabets containing $\{a, b, c\}$ . Let $R=\{(acb, c)\}$ be astring-rewriting system on. The monoid $M=A^{*}/\mu_{R}$ has a represntation with contextfree congruence classes. Moreover, $M$ is a cancellative monoid which is embedded in agroup $G=<a,$ $c|c^{-1}ac=b^{-1}>$ which is not vertually context-free.
$A^{*}$$b,$

be a finitely generated monoids having a presentation withhas a presencontext-free congruence classes. Then the free product $M_{1}*M_{2}$ oftation with context-free congruence classes.

Theorem 7Let$M_{1},$$M_{2}$$M_{1_{f}}M_{2}$References[1] M. J. Dunwoody,

The accessibility of finitely presented groups,

Invent.

Math.

26 (1985), 449-457.
[2] J. E. Hopcroft and J. D. Ullman, Introduction to Automata theory, Languages, andComputation, Addison-Wesley Publishing, 1979.
[3] Muller and Schupp, Groups, the theory of ends, and context-free languages, J. Comput. System Sci. 26(1983), 295-310.

[4] K. Shoji, Finitely generated semigroups having presentation with regular congruenceclasses, Math. Japonicae (2008),-.