论文标题
关于特殊单词的单词问题
On the Word Problem for Special Monoids
论文作者
论文摘要
如果它承认所有定义关系均为$ w = 1 $的演示文稿，则称为特殊。每个小组都是特别的，但并非每个单脚都很特别。在本文中，我们从邓肯和吉尔曼（Duncan＆Gilman）的意义上描述了这个单词问题的语言理论属性，用于特殊的单位单位。我们证明，当且仅当它的一组单元实际上是免费的，从而对Muller-Schupp定理进行全面概括时，我们就会证明特殊的单词问题。这完全回答了特殊的Monoid类，这是Duncan＆Gilman在2004年提出的一个问题。我们在特殊的Monoid中描述了单词的一致性类别，并证明这些单词与“问题”一词具有相同的语言理论属性。这回答了张在1992年首先提出的一个问题。作为推论，我们证明（在多项式时间里）是可以决定的，是否有特殊的单相关性单体是否存在无上下文的单词问题。这完全回答了1992年的另一个问题，也由张提出。
A monoid is called special if it admits a presentation in which all defining relations are of the form $w = 1$. Every group is special, but not every monoid is special. In this article, we describe the language-theoretic properties of the word problem, in the sense of Duncan & Gilman, for special monoids in terms of their group of units. We prove that a special monoid has context-free word problem if and only if its group of units is virtually free, giving a full generalisation of the Muller-Schupp theorem. This fully answers, for the class of special monoids, a question posed by Duncan & Gilman in 2004. We describe the congruence classes of words in a special monoid, and prove that these have the same language-theoretic properties as the word problem. This answers a question first posed by Zhang in 1992. As a corollary, we prove that it is decidable (in polynomial time) whether a special one-relation monoid has context-free word problem. This completely answers another question from 1992, also posed by Zhang.
