论文标题
关于可压缩的单词的单词问题
On the Word Problem for Compressible Monoids
论文作者
论文摘要
从Adian＆Oganesian定义的邓肯和吉尔曼（Duncan＆Gilman）的意义上，我们研究了这个词问题的语言理论特性。我们表明，如果$ \ nathcal {c} $是逆转的超级 - $ \ operatorname {afl} $，则是格雷巴赫（Greibach）所定义的，则$ m $在$ \ mathcal {c} $ in $ \ mathcal {c} $ in in且仅当其压缩的左monoid $ l（m）$中的$ l（m）$ n $ \ nath $ \ nath c} $ \ c} c}。作为一种特殊情况，我们可以将$ \ Mathcal {C} $作为无上下文或索引语言的类别。作为推论，我们发现许多新类的单型类具有可决定的理性子集成员资格问题。最后，我们表明，是否有一个不动力的单词具有无上下文的单词问题，这是可以决定的。这回答了Zhang在1992年首次提出的问题的概括。
We study the language-theoretic properties of the word problem, in the sense of Duncan & Gilman, of weakly compressible monoids, as defined by Adian & Oganesian. We show that if $\mathcal{C}$ is a reversal-closed super-$\operatorname{AFL}$, as defined by Greibach, then $M$ has word problem in $\mathcal{C}$ if and only if its compressed left monoid $L(M)$ has word problem in $\mathcal{C}$. As a special case, we may take $\mathcal{C}$ to be the class of context-free or indexed languages. As a corollary, we find many new classes of monoids with decidable rational subset membership problem. Finally, we show that it is decidable whether a one-relation monoid containing a non-trivial idempotent has context-free word problem. This answers a generalisation of a question first asked by Zhang in 1992.
