文法モノノイドがモノイドを分割するならば、モノノイドが言語を認識するという文章の一般化

$ A $を有限アルファベットとする。指定された言語$ L subseteq A ^ { ast} $ 構文モノイド $ M (L)$は、公式言語理論のよく知られた概念です。さらに、$
L = varphi ^ { – 1}( varphi(L))というように、モンモイド$ varphi:A ^ {
ast} が存在するならば、 ))$。

それから、いい結果が得られます:

$ M(L)$が$ M $($ M(L) prec M $と書かれている)の亜種の準同型画像であるならば、monoid $ M
$は$ L subseteq A ^ { ast} $を認識します。

上記は通常、通常の言語の文脈における状態であり、上記のモノイドはすべて有限です。

ここで、$ A ^ { ast} $を任意の単項式$ N $に置き換え、部分集合$ L subseteq N $が$ M
$によって認識されると言うとき、$ varphi:N to $ L = varphi ^ { – 1}(
varphi(L))$のようなM $である。それで$ M $が$ L $、$ M(L) prec M
$(S。Eilenberg、Automata、Machines and Languages、Volume
Bを参照)を認識すれば、逆の結果が得られます。

$ A ^ { ast} $の証明では、$ N = varphi(M)$をある種のモフィズム$ varphi:M
からN $と$ psiに変換すると、 $ varph( rho(u))= psi(u)$のように$ rho:A ^
{ ast} を見つけることができる。 A $の各$ x に対して$ rho(x) varphi ^ { – 1}(
psi(x))$を選択し、これを$ A ^ } $から$ M $までです。しかし、これは任意のモノイド$ N
$ではうまくいかないので、上記の逆が偽であると予想します。そしてもしそれが偽であれば、$ A ^ { ast}
$のそばのどのようなモノイドについても、それはまだ真実であり、これらのモノイドは研究文献に注目を集めていますか?

ベストアンサー

はい、これらのモノイドは研究文献で注目を集めており、実際には難しい質問につながっています。

Definition. A monoid $N$ is called
projective if the following property holds: if $f:N to R$
is a monoid morphism and $h:T to R$ is a surjective morphism, then
there exists a morphism $g:N to T$ such that $f = h circ g$.

定義4.1.33の直後に、[1]の射影モノイドについての長い議論を見つけることができます。特に、すべての投影有限集合がバンド(各要素が等冪である半群)であることが示されている。しかし、その逆は真実ではなく、有限の半グループが射影的であるかどうかを決定することは、実際には未解決の問題である。

[1] J. Rhodes and B. Steinberg, The $q$-theory of finite semigroups.
Springer Monographs in Mathematics. Springer, New York, 2009.
xxii+666 pp. ISBN: 978-0-387-09780-0

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です