On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids
On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids
复制标题
关于有限完全重写系统、有限推导类型和齐次幺半群的自动性
DOI：
10.1016/j.ic.2017.05.003
复制
发表时间：
2017
影响因子：
1
通讯作者：
Cain A
中科院分区：
文献类型：
--
作者：
Cain A
本文从计算的角度研究了由齐次(保长)关系定义的有限表示么半群。研究了这类么半群的容许有限完全重写系统、具有有限导子类型、自动机和双自动机的性质。第一个主要结果表明，对于这些性质和它们的否定的任何一致组合，存在恰好具有这些性质组合的齐次么半群。然后，我们引入抽象Rees可公度性的新概念(群的抽象可公度性概念的类比)，以推广这一结果，以表明即使将注意力限制在n元齐次么半群(其中每一关系的每一边都有固定长度n)，同样的命题也是成立的。然后，我们引入了一种新的编码技术，它允许我们将结果部分地推广到n元多齐次么半群类。
This paper investigates the class of finitely presented monoids defined by homogeneous (length-preserving) relations from a computational perspective. The properties of admitting a finite complete rewriting system, having finite derivation type, being automatic, and being biautomatic are investigated for this class of monoids. The first main result shows that for any consistent combination of these properties and their negations, there is a homogeneous monoid with exactly this combination of properties. We then introduce the new concept of abstract Rees-commensurability (an analogue of the notion of abstract commensurability for groups) in order to extend this result to show that the same statement holds even if one restricts attention to the class ofn-ary homogeneous monoids (where every side of every relation has fixed lengthn). We then introduce a new encoding technique that allows us to extend the result partially to the class ofn-ary multihomogenous monoids.
登录
查看更多内容
换向
DOI：
--
发表时间：
1962
期刊：
Transactions of the American Institute of Electrical Engineers Part III Power Apparatus and Systems
影响因子：
--
作者：
Erle M. Shobert
通讯作者：
Erle M. Shobert
构造没有有限完整表示的有限表示幺半群
DOI：
--
发表时间：
1997
期刊：
影响因子：
--
作者：
M. Katsura;Yuji Kobayashi
通讯作者：
Yuji Kobayashi
队列动作的幺半群
影响因子：
0.7
作者：
Martin Huschenbett;D. Kuske;Georg Zetzsche
通讯作者：
Georg Zetzsche
具有有限 Rees 指数子半群的自动半群
影响因子：
0.8
作者：
Michael Hoffmann;R. Thomas;N. Ruškuc
通讯作者：
N. Ruškuc
关于幺半群不从其 Schützenberger 群继承的性质
影响因子：
1
作者：
R. Gray;António Malheiro;S. J. Pride
通讯作者：
S. J. Pride