Probabilistic approach to cellular automata and related models

元胞自动机和相关模型的概率方法

• 批准号: 1513340
• 负责人: Janko Gravner
• 金额: $ 15.3万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1513340&HistoricalAwards=false
• 关键词: Probabilistic; approach; cellular; automata; related

Among the most convenient models of physical processes are deterministic and random cellular automata. These mathematical objects describe configurations on lattices which evolve by a repeated update of a local rule. They have been utilized to model natural phenomena and have offered insights into fundamental organizational principles in many scientific fields, including physics, biology, computer science, and social sciences. From a more abstract perspective, cellular automata are a suitable tool used to characterize and catalog local dynamics which generate a prescribed global phenomenon. The first aim of this project is to develop and use techniques from modern probability theory, as well as computational tools, to study diverse aspects of cellular automata. Then second aim is to use the gathered insights to investigate more complex dynamics of diffusive, nonlocal and high-dimensional models inspired by crystal growth, genetics and social networks.Three themes connect cellular automata with probability theory. The first issue, motivated by studying self-organization, involves evolution of a given rule from random initial states. The addressed topics include: nucleation, that is, random formation of centers that orchestrate a takeover of the available space; highly dependent percolation structures that determine the behavior of typical trajectories; and Lyapunov stability analysis through large deviations of branching random walks. The second direction are random rules, with a branching process approach to formation of stable periodic structures. The third, classical, theme is perturbation of deterministic updates by random noise. For more general models, the project aims to study non-local dynamics, focusing on nucleation theory, the nature of phase transitions, effects of space heterogeneity, and the boundary between short- and long-range interactions. Computation is a significant component of the research and involves simulations, analysis of algorithms, computer-aided proofs, numerical and statistical methods, and visualization techniques.

在物理过程的最方便的模型是确定性和随机元胞自动机。这些数学对象描述了通过局部规则的重复更新而进化的晶格上的配置。它们被用来模拟自然现象，并为许多科学领域的基本组织原理提供了见解，包括物理学，生物学，计算机科学和社会科学。从一个更抽象的角度来看，元胞自动机是一个合适的工具，用于表征和目录的局部动态生成一个规定的全球现象。这个项目的第一个目标是开发和使用现代概率论的技术，以及计算工具，研究细胞自动机的各个方面。第二个目标是利用收集到的见解来研究受晶体生长、遗传学和社交网络启发的扩散、非局部和高维模型的更复杂的动力学。第一个问题，研究自组织的动机，涉及到一个给定的规则从随机初始状态的演变。讨论的主题包括：成核，即，随机形成的中心，协调接管的可用空间;高度依赖的渗流结构，确定典型的轨迹的行为;和李雅普诺夫稳定性分析，通过大偏差的分支随机行走。第二个方向是随机规则，用分支过程方法形成稳定的周期结构。第三，经典的，主题是随机噪声扰动的确定性更新。对于更一般的模型，该项目旨在研究非局部动力学，重点是成核理论，相变的性质，空间异质性的影响，以及短程和长程相互作用之间的边界。计算是研究的重要组成部分，涉及模拟，算法分析，计算机辅助证明，数值和统计方法以及可视化技术。