时间的平行动力系统

文摘

在这项工作中,我们提供了条件,获得平行动力系统不动点定理在图表(布尔)最大项和小项随着全球进化操作符。为了做到这一点,我们先前证明周期轨道的不同时期不能共存,这意味着Sharkovsky订单是无效的这种动力系统。

1。介绍

这是无可争议的,数学建模的现象是应用数学的主要任务之一。然而,一旦模型适合一个现象,有必要从理论上分析这样一个模型,以结果发现适用于任何特定的情况下学习。

在过去的二十年里,图动力系统(GDS)被显示为计算机过程的数学建模的一个重要工具。等制定模型,这些系统分解为较低的单位聚合实体,每个实体(数值)值吗代表它的状态。当每个实体的可能状态是激活或不激活,一个实体的状态值是正式通过考虑。事实上,状态值可以属于一个更一般的布尔代数(1]。实体之间的关系由一个图形称为表示依赖关系图系统的,而进化或更新的系统实现本地(布尔)功能共同构成一个全球(进化)算子。即为动态演化的任何实体,对应的本地函数作用于这样的国家和那些对应于相关的实体。

当美国的实体以同步的方式更新,系统被称为平行动力系统(PDS) [2,3),而如果他们以异步方式更新,系统命名连续动力系统(SDS) [4]。

其他工具为数学建模细胞自动机(CA) (5- - - - - -11(BN)[]或布尔网络12- - - - - -14)是特定情况下的PDS (15]。它显示了巨大的多功能性的新范式,应用不同的分支的科学是生物学(12,16,17,生态18- - - - - -20.)、数学(21,22),密码(23,24)、物理(25)和化学(26]。(缩写GDS、PDS、SDS、钙、和BN为单数和复数形式编写的相应的条款,因为它看起来更好的从美学的观点。)

关于动力系统的研究的主要目的是给一个完整的描述的轨道结构(27]。也就是说,获得尽可能多的信息的相图,基于初始状态和系统的进化算子。具体来说,在[指出28),这意味着确定长度和数量的共存极限环和不同初始状态到达相同的极限环。

关于这些问题,在3PDS和SDS进行了研究,考虑最简单的布尔函数或(分别地。),也没有(分别地。,NAND) as global evolution operators. These results are extended in [2]PDS与任何通用逻辑最大项(分别地。小项)作为全局函数;特别是,它证明了PDS独特周期性或最终周期轨道低于或等于2是可能的。

结果在2]开其中一些问题设置了德里达和Pomeau [28关于这类系统的相图。其中之一在于研究周期轨道的不同时期的共存PDS与通用最大项(分别地。小项)相同的函数作为进化运营商Sharkovsky定理(29日,30.]。换句话说,它包含在猜测是否存在某些时期意味着其他的类似的方式的出现Sharkovsky的命令。

关于这个问题,在这个工作中,我们表明,Sharkovsky定理和秩序建立在PDS的背景下不适用。相反,我们表明,周期轨道的共存与不同时期是不可能的。

本文的主要目的是建立结果PDS与通用最大项(分别地。,minterm) functions as evolution operators in the sense of the fixed point theorem by Banach. In fact, as we show in Example8,存在PDS和几个固定的点,因此它自然出现的问题确定条件保证定点的独特性。

最初的结果,给出了基本的布尔代数中的实体的状态值,后来都属于任何一般的广义状态值的布尔代数元素,,。

具体系统对待这项工作出现真实的物理现象的动力学建模时的基因。特别是,当研究基因调控网络,它是观察到的结合位点基因受多个基因表现出协同效应。这可以通过连接布尔网络建模,但是他们不允许建模抑制性调节,需要从小项进化运营商形式化和分析相应的动力学(见[31日])。

本文组织如下。部分2给了一些关于PDS预赛最大项和小项布尔函数。节3,我们表明,周期轨道的共存与不同时期是不可能的,所以显示Sharkovsky定理不适用在这个上下文。节4,我们建立一个PDS的不动点定理。节5我们扩展我们的结果PDS与国家价值观属于任何一般的布尔代数元素。最后,部分6提供了一些结论和未来的研究方向。

2。预赛

在本节中,我们修改一些基本的观念有关平行动力系统(PDS)(见[15),其中引用的详细信息)。

众所周知,PDS完全是由自己决定的依赖关系图和它的进化或更新功能下面我们简要描述。

依赖图是由一个无向图,在那里顶点集和吗边集。我们将代表吗的状态的顶点,这意味着顶点是激活()或停用()。

我们将假设连接;否则,推理和结果我们将提供可以很容易地适应通过连接组件。

对于每一个顶点,我们将考虑一组相邻的顶点;也就是说, 然后,考虑到,我们定义

系统的进化或更新由当地实现功能,每,只有在。

定义1。让是一个图上。然后一个地图 在哪里更新后的实体的状态吗通过应用一个本地函数在美国的实体,构成离散动力系统平行动力系统(PDS)。

每一个通常是全局函数的限制只有在实体的状态,我们要想在这个文档。然而,每个可被视为另一个函数: 这样。

特别是,PDS的(全球)进化算子可以得到通过布尔函数的变量: 在哪里是获得使用逻辑“与”()、逻辑或(),逻辑不()和元素。特殊情况下的布尔函数最大项和小项。回想一下,一个最大项(分别地。小项)变量是一个布尔函数如 在哪里或。

在这项工作中,我们处理这个特殊的PDS。

定义2。让(无向)图。然后下面的(进化)算子 在哪里更新后的实体的状态吗通过应用局部布尔函数在美国的顶点,构成了PDS结束布尔函数进化算子,将用或pds当指定依赖图不是必需的。

特别是,我们将代表MAX-PDS(分别地。,MIN-PDS) a PDS whose evolution operator is the maxterm MAX (resp., the minterm MIN).

3所示。在PDS共存的周期轨道图

在[2)结果表明,MAX-PDS(职责的周期轨道。MIN-PDS)是固定的点或2-periodic轨道。此外,当最大项MAX(分别地。,minterm MIN) has all the variables in its direct form, then only (eventually) fixed points can appear, while if it has all the variables in its complemented form, then only (eventually) 2-periodic orbits are possible.

然而,一些重要的问题仍然开放。其中之一在于研究周期轨道的共存与不同时期同样的Sharkovsky定理(29日,30.)与通用最大项(resp PDS。,minterm) functions as evolution operators. In other words, it consists in guessing whether the existence of certain periods implies the appearance of other ones in a similar way to Sharkovsky’s order. Concerning this question, in this section, we prove that Sharkovsky’s Theorem and the order established with it do not apply in the context of PDS. In fact, we demonstrate that periodic orbits with different periods cannot coexist.

为了做到这一点,接下来,我们描述结构一个PDS必须以承认(最终)固定的点。我们将概述MAX-PDS的情况下的推理,虽然他们可以双重MIN-PDS重写。

定理3。让MAX-PDS PDS依赖图相关的最大项MAX。所有该系统的周期轨道是固定的点,如果且仅如果每个实体的状态变量在马克斯补充形式是相邻的一个实体的状态变量在马克斯在定向形式。

证明。让我们考虑一组(职责。)的顶点这样在最大值出现在相应的变量直接(分别地。补充)的形式。
首先,假设所有该系统的周期轨道是固定的点。
在的情况下,系统有两个不动点:一个与激活的所有变量,一个全部停用(见[2,3])。
因此,假设并采取一个不动点,代表(固定)值的顶点。注意,,它必须。否则(即。,如果),它会改变后下面的迭代。
假设存在这样。在这种情况下所以对于每一个它是。但这是不可能的,因为在接下来的迭代的价值将改变为0,这是一个矛盾。
为了证明相反的含义,让我们假设它是。我们将编写来表示实体的状态值后迭代进化操作符的马克斯。因此,让我们考虑一个任意初始值的变量。由于依赖图是有限的(因此是状态空间),注意,一定数量的迭代之后,让我们说,美国所有的顶点成为固定。让我们以让我们证明。事实上,让我们假设并采取。然后它会(因为我们假设的状态值从迭代是固定的吗)。但是,自,它必须,这是一个矛盾。因此,它是对所有和这些状态值不变化可以很容易地推断出从上面的推理。
因此,所有系统的变量成为固定后迭代和完成的证据。

会,我们有以下。

定理4。让MIN-PDS PDS依赖图与小项分钟。所有该系统的周期轨道是固定的点,如果且仅如果每个实体的状态变量在分钟补充形式是毗邻一个实体的状态变量最小定向形式。

类似地,双重的结果可以得到以下结果。为了简明起见,我们不会状态。

因为所有系统的周期轨道是固定的点或2-periodic轨道(见[2]),由于定理3我们有以下。

定理5。让MAX-PDS PDS依赖图相关的最大项MAX。2-periodic所有该系统的周期轨道的轨道,如果且仅当存在一个实体的状态变量马克斯是补充形式不靠近任何实体的状态变量在马克斯定向形式。

证明。首先,假设所有该系统的周期轨道2-periodic轨道。如果论文是不正确的,也就是说,如果,它是,然后从定理3我们都有这个系统的周期轨道是固定的点,这是一个矛盾。
相反,让我们假设存在这样。如果系统有一个固定的点,推理与证明的定理3,我们得到,每个实体的状态变量在马克斯补充形式是毗邻马克斯是一个实体的状态变量直接形式,这是一个矛盾。因此,所有系统的周期轨道必须2-periodic轨道。

注6。注意的情况下系统的演化算符,或者,NAND闪存,也不研究[3)可以立即获得作为定理的特殊情况下3和5。

作为定理的直接后果3和5这一部分,我们得到的主要结果。

定理7。让MAX-PDS PDS依赖图相关的最大项MAX。然后(最终)不动点(最终)2-periodic轨道不能共存。

4所示。PDS /图的不动点定理

评论的介绍,我们的主要目标是获得一个PDS的公共不动点定理。观察到,尽管不动点和2-periodic轨道不能共存,PDS的状态空间包含多个定点,如以下示例所示。

示例8与超过一定点(PDS)。让我们考虑图与和,让我们把进化算子 PDS的不动点,,。

因此,它将需要找到条件以确保系统有一个独特的定点。为了做到这一点,假设MAX-PDS至少有一个固定的点;也就是说,每一个顶点它是(见定理3)。

让是造成的连接组件当我们删除所有的顶点和边缘相邻的顶点。我们会说一个顶点在和一个连接组件是相邻的相邻的顶点吗。让我们考虑的子集和的给出的

让是一个系统的定点。正如我们所显示的定理的证明3,尽管,它是。

此外,如果,是这样的,,然后对所有它是。以看到,注意,在不动点所有的顶点必须激活或停用。让我们以。然后,如果它是对所有,因为它是对所有,然后的状态下一次迭代后将改变为0,这是一个矛盾。

因此,如果对每一个,,它是,那么系统有一个独特的定点:激活的所有变量。

另一方面,如果一个,,它是,然后在一个固定的点可能有两种情况:要么所有的顶点被激活或全部停用。关于这个最后的评价,我们必须指出,如果,连接组件相邻吗,并不是所有这些组件可以得到释放,同时在不动点;其他的价值将改变从1到0以下迭代。

鉴于上面的解释中,我们证明了下面的结果。

定理9。让MAX-PDS PDS依赖图与最大项MAX和相关假设它是。这PDS有独特的定点,如果且仅如果为每一个,,它是。在这种情况下,唯一不动点的所有顶点激活。

5。不动点定理对PDS图与一般的布尔州

在最近的工作(1),概括介绍了PDS /图表,考虑到美国实体可以值的任意布尔代数与元素,,。我们代表等PDS(职责。)来表示依赖关系图和最大项MAX(分别地。,minterm MIN) taken as evolution operator. Note that the previous study corresponds to the particular case where;也就是说,。

在这样一个工作,这是证明这些更一般的PDS的周期轨道也不动点或2-periodic轨道。证明这个结果的关键理念在于使用布尔代数的石头表示定理一个合适的方法分解这个一般动力系统PDS实体采取价值的地方(见[1,部分)的详细信息)。

然后,从我们的研究上面,一个简单的推理允许检查所有的结果部分3和4也对PDS的实体的状态值在任意布尔代数。(最终)固定分,(最终)2-periodic轨道不能共存。

定理10。让PDS的依赖图相关的最大项MAX。然后(最终)不动点(最终)2-periodic轨道不能共存。

特别是,我们有一个不动点定理在这更一般的上下文如下所述

定理11。让PDS的依赖图相关的最大项和假设它是。这PDS有独特的定点,如果且仅如果为每一个,,它是。在这种情况下,唯一不动点是所有顶点的状态等于。

证明。因为这个动力系统可以分解为将军PDS实体采取价值的地方所有这些PDS上定义相同的依赖图,系统有一个独特的不动点,类似于一个吗识别价值与和与。

6。结论和未来的研究方向

本文提供了一个重要的进步PDS的相图的描述(全球)布尔操作符图,通过分析两个经典定理的真实性在动力系统理论框架。

特别是,我们表明,周期轨道的共存与不同时期是不可能在这样的系统。这意味着Sharkovsky离散动力系统与连续函数的定理并不是真正的PDS的上下文中。我们还获得一个不动点定理对这种动力系统,提供条件保证PDS的不动点的唯一性。换句话说,我们描述的PDS任何初始状态演化的平衡,对于真正的模型,是一个有意义的信息。

最后,通过这项工作中提供的技术,结果获得邀请研究相同的问题在其他类型的GDS,这些指示图(32)和/或那些当地独立的进化算子给出通过布尔函数(33]。

其他工具为数学建模细胞自动机(CA)或布尔网络(BN)是特定情况下的PDS在考虑相同的进化算子。最大项,CA和BN(分别地。,minterm) Boolean functions over undirected graphs are particular cases of PDS with maxterm (resp., minterm) that we treat in this work. It shows the applicability to different branches of sciences and engineering that this new paradigm of PDS can have.

相互竞争的利益

作者宣称没有利益冲突。

确认

胡安·a·Aledo被军政府支持德Comunidades de恰拉(批准peii - 2014 - 049 - p)。路易斯·g·迪亚兹,西尔维亚马丁内斯和何塞·c·瓦尔韦德是支持菲德尔op2014 - 2020恰拉在格兰特GI20163581(西班牙)。西尔维亚马丁内斯和何塞·c·瓦尔韦德也支持西班牙的经济和竞争力(格兰特mtm2014 - 51891 - p)。

引用

1. j . a . Aledo s·马丁内斯,j·c·瓦尔韦德”图动力系统与一般的布尔州,”应用数学与信息科学,9卷,不。4、1803 - 1808年,2015页。视图:出版商的网站|谷歌学术搜索|MathSciNet
2. j . a . Aledo马丁内斯,f·l·皮雷约和j·c·瓦尔韦德“平行动力系统最大项和小项布尔函数,“数学和计算机模拟,35卷,第671 - 666页,2012年。视图:谷歌学术搜索
3. c·l·巴雷特w . y . Chen和m . j .郑”图和布尔函数,离散动力系统”数学和计算机模拟,卷66,不。6,487 - 497年,2004页。视图:出版商的网站|谷歌学术搜索|MathSciNet
4. h . s . Mortveit和c m·蕾迪介绍连续动力系统施普林格,纽约,纽约,美国,2007年。视图:MathSciNet
5. a . Ilachinski细胞自动机。一个离散的宇宙,世界科学,新加坡,2001年。
6. j . Kari”细胞自动机理论:一个调查,“理论计算机科学,卷334,不。1 - 3,3-33,2005页。视图:出版商的网站|谷歌学术搜索|MathSciNet
7. j·梅纳德进化和游戏理论英国剑桥,剑桥大学出版社,1982年。
8. p . Sarkar”,元胞自动机简史”,ACM计算调查,32卷,不。1,第107 - 80页,2000。视图:出版商的网站|谷歌学术搜索
9. j·l·希夫细胞自动机:一个离散的世界观约翰·威利& Sons,纽约,纽约,美国,2008年。视图:MathSciNet
10. 美国Wolfram”,元胞自动机的统计力学,”现代物理学的评论,55卷,不。3、601 - 644年,1983页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
11. s . Wolfram元胞自动机和复杂美国,addison - wesley,纽约,纽约,1994年。
12. s . a·考夫曼”以随机渐进的代谢稳定性和构建基因网络,”理论生物学杂志》上,22卷,不。3、437 - 467年,1969页。视图:出版商的网站|谷歌学术搜索
13. s . a·考夫曼秩序:起源自组织进化和选择英国牛津,牛津大学出版社,1993年。
14. 即Shmulevich和s . a·考夫曼,”布尔网络模型、活动和敏感性”物理评论快报,卷93,不。4篇文章ID 048701 4页,2004。视图:出版商的网站|谷歌学术搜索
15. j . a . Aledo s·马丁内斯,j·c·瓦尔韦德“平行动力系统图和相关的话题:一项调查,“应用数学学报ID 594294条,卷。2015年,14页,2015。视图:出版商的网站|谷歌学术搜索|MathSciNet
16. 答:Deutsch和s . Dormann生物模式形成的细胞自动机模型美国,Birkhauser波士顿,马萨诸塞州剑桥市,2004年。
17. z Toroczkai和h Guclu“接近网络和流行,”自然史答:统计力学及其应用,卷378,不。1,第75 - 68页,2007。视图:出版商的网站|谷歌学术搜索
18. p . Hogeweg”,元胞自动机作为生态建模范式”,应用数学和计算,27卷,不。1,第100 - 81页,1988。视图:出版商的网站|谷歌学术搜索|MathSciNet
19. 美国Dieckman、r .法律和j·a·j·梅茨的几何生态相互作用。简化空间复杂性英国剑桥,剑桥大学出版社,2000年。
20. j . Hofbauer和k·西格蒙德进化游戏和种群动态英国剑桥,剑桥大学出版社,2003年。
21. g . Chiaselotti t非犹太人,p . a . Oliverio”平行的两个离散模型和连续动态带符号整数分区,”应用数学和计算卷,232年,第1261 - 1249页,2014年。视图:出版商的网站|谷歌学术搜索|MathSciNet
22. g . Chiaselotti g·马里诺,p . A . Oliverio和d . Petrassi”签署的离散动力学模型分区,应用数学学报文章ID 973501卷,2013年,10页,2013。视图:出版商的网站|谷歌学术搜索|MathSciNet
23. a . Fuster-Sabater和p . Caballero-Gil”,在对称加密,使用元胞自动机”Acta Applicandae Mathematicae,卷93,不。1 - 3、215 - 236年,2006页。视图:出版商的网站|谷歌学术搜索|MathSciNet
24. 美国南帝,b . k .凹地,p . Pal乔杜里”理论和元胞自动机在密码学中的应用”,IEEE计算机,43卷,不。12日,第1357 - 1346页,1994年。视图:出版商的网站|谷歌学术搜索|MathSciNet
25. 萧邦和m . dro物理元胞自动机建模英国剑桥,剑桥大学出版社,1998年。
26. l·b·科尔,p . g .网络和C.-K。程,使用元胞自动机建模化学系统施普林格,纽约,纽约,美国,2005年。
27. s•威金斯介绍应用非线性动力系统和混乱施普林格,纽约,纽约,美国,1990年。视图:出版商的网站|MathSciNet
28. 德里达和y Pomeau”,随机自动机网络:一个简单的退火近似,”Europhysics字母,1卷,不。2,45-49,1986页。视图:出版商的网站|谷歌学术搜索
29. a . n . Sharkovsky”共存的连续映射的周期行到本身,”乌克兰数学杂志》16卷,第71 - 61页,1964年。视图:谷歌学术搜索
30. p .Štefan”定理Šarkovskii连续的周期轨道的存在实线的自同态,”通信的数学物理,54卷,不。3、237 - 248年,1977页。视图:出版商的网站|谷歌学术搜索|MathSciNet
31. 公园,k·h·李,和d·李”的组合逻辑规则推理协同集于癌症基因微阵列数据集,“生物信息学,26卷,不。12日,第1512 - 1506页,2010年。视图:出版商的网站|谷歌学术搜索
32. j . a . Aledo s·马丁内斯,j·c·瓦尔韦德“平行动力系统依赖图,”应用数学和计算,卷219,不。3、1114 - 1119年,2012页。视图:出版商的网站|谷歌学术搜索|MathSciNet
33. j . a . Aledo s·马丁内斯,j·c·瓦尔韦德“平行离散动力系统在独立的本地功能,”计算和应用数学杂志》上,卷237,不。1,第339 - 335页,2013。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet

版权

版权©2017胡安Aledo et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。