Ranks of finite semigroups of one-dimensional cellular automata
Ranks of finite semigroups of one-dimensional cellular automata
复制标题
一维元胞自动机的有限半群的秩
DOI：
10.1007/s00233-016-9783-z
复制
发表时间：
2016
期刊：
影响因子：
0.7
通讯作者：
Castillo-Ramirez A
中科院分区：
文献类型：
--
作者：
Castillo-Ramirez A
自从约翰·冯·诺依曼首次提出以来，细胞自动机的概念已经发展成为计算机科学，物理学和理论生物学中的一个关键概念。在其经典设置中，元胞自动机是一个规则网格的所有配置的集合的变换，使得网格的任何特定单元的图像由仅取决于固定有限邻域的固定局部函数确定。近年来，随着形式变换（其中G是任何群，A是任何集合）的广义定义的引入，细胞自动机理论因其与群论和拓扑学的联系而得到了极大的丰富。本文开始对元胞自动机的有限半群理论的研究，首先研究了循环群上的所有元胞自动机和有限集合A所组成的半群的秩（即最小生成集的基数）。特别是，我们确定这个秩时，等于顶部，或，为任何奇数素数，我们给出了一般情况下的上限和下限。
Since first introduced by John von Neumann, the notion of cellular automaton has grown into a key concept in computer science, physics and theoretical biology. In its classical setting, a cellular automaton is a transformation of the set of all configurations of a regular grid such that the image of any particular cell of the grid is determined by a fixed local function that only depends on a fixed finite neighbourhood. In recent years, with the introduction of a generalised definition in terms of transformations of the form(whereGis any group andAis any set), the theory of cellular automata has been greatly enriched by its connections with group theory and topology. In this paper, we begin the finite semigroup theoretic study of cellular automata by investigating the rank (i.e. the cardinality of a smallest generating set) of the semigroupconsisting of all cellular automata over the cyclic groupand a finite setA. In particular, we determine this rank whennis equal top,or, for any odd primepand, and we give upper and lower bounds for the general case.
登录
查看更多内容
DOI：
10.1017/s0305004115000389
发表时间：
2014
影响因子：
0.8
作者：
J. Araújo;W. Bentz;J. Mitchell;Csaba Schneider
通讯作者：
Csaba Schneider
影响因子：
0.7
作者：
R. Gray
通讯作者：
R. Gray
影响因子：
0.9
作者：
R. Carter
通讯作者：
R. Carter
DOI：
10.1007/978-1-84800-281-4
发表时间：
2008-12
期刊：
--
影响因子：
--
作者：
O. Ganyushkin;V. Mazorchuk
通讯作者：
O. Ganyushkin;V. Mazorchuk
DOI：
--
发表时间：
1983
期刊：
影响因子：
--
作者：
N. Metropolis;G. Rota
通讯作者：
G. Rota