Elements of a theory of computer simulation - I: Sequential CA over random graphs
Elements of a theory of computer simulation - I: Sequential CA over random graphs
复制标题
DOI：
10.1016/s0096-3003(97)10166-7
复制
发表时间：
1999-02-01
影响因子：
4
通讯作者：
Reidys, CM
中科院分区：
文献类型：
--
作者：
Barrett, CL;Reidys, CM
这篇论文是发展仿真理论的数学基础的第一步。我们使用任意图上的顺序更新的元胞自动机(SCA)作为范例框架，在理论的发展过程中，我们重点研究了模拟中局部映射之间的因果依赖的性质。设Y是一个图，其中(A)每个顶点i都有一个状态x(I)是一个{0，1}的元素，(B)存在一个定义在Y-邻域的状态上的局部映射f(I)，并且返回y(I)的状态的x(I)是一个{0，1}的元素。设{I(L)，..，I(N)}是Y-顶点的置换，则局部映射FI的应用顺序诱导出Y上的一个顺序(或异步)元胞自动机.在本文中，我们引入了基图Y和更新图U(Y)之间的一种映射.在该基图上定义了一个表示局部映射的相互依赖关系的元胞自动机.两个排列NL、NZ在U(Y)中相邻，如果它们恰好在两个连续的坐标上不同，则{i(K)，i(k+1)}和{i(K)，i(k+1)}不是EY的元素。U(Y)表示一个概念框架，它允许确定给定图X的SCA的等价类，独立于局部映射族(f(I))(1小于或等于i小于或等于n)。我们考虑：(A)U是G(n，p)上的随机变量，分析了诱导随机图U(G(n，p))，并证明了(B)U具有协变函子的性质。(C)1999由爱思唯尔科学公司出版。版权所有。
This paper is a first step in the development of mathematical foundations for a theory of simulation. We employ sequentially updated cellular automata (sCA) over arbitrary graphs as a paradigmatic framework, In the development of the theory, we focus on the properties of causal dependencies among local mappings in a simulation. Let Y be a graph in which (a) each vertex i has a state x(i) is an element of {0,1} and (b) there exists a local map f(i) defined on the states of the Y-neighbors and x(i) that returns the state of y(i) is an element of {0, 1}. Suppose {i(l),..,, i(n)} is a permutation of the Y-vertices, then the order of application of the local maps fi, induces a sequential (or asynchronous) cellular automaton (sCA) over Y. In this paper we introduce a mapping between the base graph Y, over which the sCA is defined and which represents the mutual dependencies of the local maps, and the update graph U(Y), whose vertices are permutations of all Y-vertices. Two permutations nl, nz are adjacent in U(Y) if they differ in exactly two consecutive coordinates, {i(k), i(k+1)} and {i(k), i(k+1)} is not an element of eY. U(Y) represents a conceptual framework which allows to determine equivalence classes of sCA for a given graph X, independent of the family of local maps (f(i))(1 less than or equal to i less than or equal to n). We consider: (a) U as a random variable over G(n,p) and analyze the induced random graph U(G(n,p)), the update graph, and show (b) that U exhibits properties of a covariant functor. (C) 1999 Published by Elsevier Science Inc. All rights reserved.