论文标题
特殊单体的几何形状
The Geometry of Special Monoids
论文作者
论文摘要
如果它承认所有定义关系均为$ w = 1 $的演示文稿，则据说它是特别的。小组是特殊单体的熟悉例子。本文研究了有限呈现的特殊单体的Cayley图的几何和结构特性，该图是Zhang和Gray-Steinberg的作品。结果表明，从Muller＆Schupp的意义上讲，当$ M $的单位群实际上是免费的，当时，特殊的monoid $ m $的右Cayley Graph $γ$是无上下文的图形。这概括了众所周知的Muller-Schupp定理的几何方面，从组到特殊的单体。此外，我们完全表征了$γ$的否则二阶理论是可以决定的：这正是在几乎免费的单位群体时，这正是这是当时的。这完全回答了2006年从2006年开始的kuske＆lohrey的特殊类型。作为推论，我们可以获得$ m $的理性子集成员资格问题当$ m $的单位几乎是免费的，从而扩展了Kambites＆Render的结果。我们还表明，具有几乎免费的单元组的特殊单体类别与带有右Cayley图的特殊单体类别的类别级别iS-iSomemotric to to Tree作为无方向的图。以上结果可以通过为图表的两个通用构造来证明，这些构造能够保留具有独立关注的上下文柔性。第一个获取无上下文图并构造了此图的副本树。第二个是所得拷贝树的有界确定。
A monoid is said to be special if it admits a presentation in which all defining relations are of the form $w = 1$. Groups are familiar examples of special monoids. This article studies the geometric and structural properties of the Cayley graphs of finitely presented special monoids, building on work by Zhang and Gray-Steinberg. It is shown that the right Cayley graph $Γ$ of a special monoid $M$ is a context-free graph, in the sense of Muller & Schupp, if and only if the group of units of $M$ is virtually free. This generalises the geometric aspect of the well-known Muller-Schupp Theorem from groups to special monoids. Furthermore, we completely characterise when the monadic second order theory of $Γ$ is decidable: this is precisely when the group of units is virtually free. This completely answers for the class of special monoids a question of Kuske & Lohrey from 2006. As a corollary, we obtain that the rational subset membership problem for $M$ is decidable when the group of units of $M$ is virtually free, extending results of Kambites & Render. We also show that the class of special monoids with virtually free group of units is the same as the class of special monoids with right Cayley graph quasi-isometric to a tree as undirected graphs. The above results are proven by developing two general constructions for graphs which preserve context-freeness, of independent interest. The first takes a context-free graph and constructs a tree of copies of this graph. The second is a bounded determinisation of the resulting tree of copies.
