论文标题
在由自动机生成的一类无多种文本的组上
On a class of poly-context-free groups generated by automata
论文作者
论文摘要
本文涉及与树木相关的图形自动机组和一些概括。我们首先显示树自动机组的一些代数属性。然后，我们表征了相关的半群，证明它与定义树的线图的补充相关的部分交换性单体是同构的。之后，我们通过引入相当广泛的可还原自动机组来概括这些组，该组在没有单数点的合同自动机组类别中进行概括。我们给出了一个通用结构定理，该定理表明所有可简化的自动机组都是无多种文本组的直接限制，这些群体实际上是自由组的直接乘积的亚组。请注意，该结果部分支持T. Brough的猜想。此外，我们证明，至少有两个发电机的树自动机组没有有限的呈现，并且它们是可正常的组，它们是不可否的组的直接限制。
This paper deals with graph automaton groups associated with trees and some generalizations. We start by showing some algebraic properties of tree automaton groups. Then we characterize the associated semigroup, proving that it is isomorphic to the partially commutative monoid associated with the complement of the line graph of the defining tree. After that, we generalize these groups by introducing the quite broad class of reducible automaton groups, which lies in the class of contracting automaton groups without singular points. We give a general structure theorem that shows that all reducible automaton groups are direct limit of poly-context-free groups which are virtually subgroups of the direct product of free groups; notice that this result partially supports a conjecture by T. Brough. Moreover, we prove that tree automaton groups with at least two generators are not finitely presented and they are amenable groups, which are direct limit of non-amenable groups.
