A pseudo-random network mobile automaton with linear growth

Based on the mobile automaton model, an algorithm is introduced that grows planar, tri-valent graphs by exhibiting a peculiar, twofold dynamics. In a first phase, graph growth appears to be pseudo-random and O(n) then it settles to a very regular behavior and rate. A pseudo-random mobile automaton is already known; the new automaton provides now a finite, but surprisingly long, pseudo-random, linear growth process. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested.     

Complexity of reachability problems for finite discrete dynamical systems

Sequential Dynamical Systems (SDSs) are a special type of finite discrete dynamical systems that can be used to model simulation systems. We focus on the computational complexity of testing several phase space properties of SDSs. Our main result is a sharp delineation between classes of SDSs whose behavior is easy to predict and those whose behavior is hard to predict. Specifically, we show the following.

1.

Several state reachability problems for SDSs are PSPACE-complete, even when restricted to SDSs whose underlying graphs are of bounded bandwidth (and hence of bounded pathwidth and treewidth), and the function associated with each node is symmetric. Moreover, this result holds even when the underlying graph is d-regular for some constant d and all the nodes compute the same symmetric Boolean function. An immediate corollary of this result is a PSPACE-hard lower bound on the complexity of reachability problems for regular generalized 1D-Cellular Automata and undirected systolic networks with Boolean totalistic local transition functions.

2.

In contrast, the above reachability problems are solvable in polynomial time for SDSs when the Boolean function associated with each node is symmetric and monotone.

The PSPACE-completeness results follow as corollaries of simulation results which show for several classes of SDSs, how one class of SDSs can be efficiently simulated by another (more restricted) class of SDSs. We also prove several structural properties concerning the phase space of an SDS. SDSs are closely related to Cellular Automata (CA), concurrent transition systems, discrete Hopfield networks and systolic networks. This observation in conjunction with our lower bounds for SDSs, yields new PSPACE-hard lower bounds on the complexity of state reachability problems for these models, extending some of the earlier results in [K. Culik II, J. Karhumäki, On totalistic systolic networks, Inform. Process. Lett. 26 (5) (1988) 231-236; P. Floréen, E. Goles, G. Weisbuch, Transient length in sequential iterations of threshold functions, Discrete Appl. Math. 6 (1983) 95-98; P. Floréen, P. Orponen, Complexity issues in discrete Hopfield networks, Research Report No. A-1994-4, Department of Computer Science, University of Helsinki, 1994. Also appears in: I. Parberry (Ed.), Comp. and Learning Complexity of Neural Networks: Advanced Topics, 1999; D. Harel, O. Kupferman, M.Y. Vardi, On the complexity of verifying concurrent transition systems, Inform. and Comput. 173 (2002) 143-161; S.K. Shukla, H.B. Hunt III, D.J. Rosenkrantz, R.E. Stearns, On the complexity of relational problems for finite state processes, in: International Colloquium on Automata Programming and Languages, ICALP, 1996, pp. 466-477; A. Rabinovich, Complexity of equivalence problems for concurrent systems of finite agents, Inform. and Comput. 127 (2) (1997) 164-185].     

Bounding the firing synchronization problem on a ring

In this paper we improve the upper and lower bounds on the complexity of solutions to the firing synchronization problem on a ring. In this variant of the firing synchronization problem the goal is to synchronize a ring of identical finite automata. Initially, all automata are in the same state except for one automaton that is designated as the initiator for the synchronization. The goal is to define the set of states and the transition function for the automata so that all machines enter a special fire state for the first time and simultaneously during the final round of the computation. In our work we present two solutions to the ring firing synchronization problem, an 8-state minimal-time solution and a 6-state non-minimal-time solution. Both solutions use fewer states than the previous best-known minimal-time automaton, a 16-state solution due to Culik. We also give the first lower bounds on the number of states needed for solutions to the ring firing synchronization problem. We show that there is no 3-state solution and no 4-state, symmetric, minimal-time solution for the ring.     

Efficient processing of label-constraint reachability queries in large graphs

In this paper, we study a variant of reachability queries, called label-constraint reachability (LCR) queries. Specifically, given a label set S and two vertices u₁ and u₂ in a large directed graph G, we check the existence of a directed path from u₁ to u₂, where edge labels along the path are a subset of S. We propose the path-label transitive closure method to answer LCR queries. Specifically, we t4ransform an edge-labeled directed graph into an augmented DAG by replacing the maximal strongly connected components as bipartite graphs. We also propose a Dijkstra-like algorithm to compute path-label transitive closure by re-defining the “distance” of a path. Comparing with the existing solutions, we prove that our method is optimal in terms of the search space. Furthermore, we propose a simple yet effective partition-based framework (local path-label transitive closure+online traversal) to answer LCR queries in large graphs. We prove that finding the optimal graph partition to minimize query processing cost is a NP-hard problem. Therefore, we propose a sampling-based solution to find the sub-optimal partition. Moreover, we address the index maintenance issues to answer LCR queries over the dynamic graphs. Extensive experiments confirm the superiority of our method.     

Embedding a family of disjoint 3D meshes into a crossed cube

Crossed cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint 3D meshes into a crossed cube. Two major contributions of this paper are: (1) for n?4, a family of two disjoint 3D meshes of size 2×2×2^n-3 can be embedded in an n-D crossed cube with unit dilation and unit expansion, and (2) for n?6, a family of four disjoint 3D meshes of size 4×2×2^n-5 can be embedded in an n-D crossed cube with unit dilation and unit expansion. These results mean that a family of two or four 3D-mesh-structured parallel algorithms can be executed on a same crossed cube efficiently and in parallel. Our work extends the results recently obtained by Fan and Jia [J. Fan, X. Jia, Embedding meshes into crossed cubes, Information Sciences 177(15) (2007) 3151-3160].     

Asynchronous cellular learning automata

Cellular learning automata is a combination of cellular automata and learning automata. The synchronous version of cellular learning automata in which all learning automata in different cells are activated synchronously, has found many applications. In some applications a type of cellular learning automata in which learning automata in different cells are activated asynchronously (asynchronous cellular learning automata) is needed. In this paper, we introduce asynchronous cellular learning automata and study its steady state behavior. Then an application of this new model to cellular networks has been presented.     

On the effectiveness of cellular automata to add real numbers

This paper investigates the effectiveness of cellular automata to compute arithmetic functions over the set of real numbers. Since cellular automata (CA) have parallel computational ability in conjunction with the capacity to accept an infinite length input, the CA should be able to effectively compute real number arithmetic. This paper shows that typical representations of real numbers do not lend themselves to effective computation by a CA and that a nonstandard representation must be employed in order to accomplish this.     

Embedding a family of disjoint multi-dimensional meshes into a crossed cube

Crossed cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint multi-dimensional meshes into a crossed cube. We prove that for n?4 and 1?m?⌊n/2⌋−1, a family of m² disjoint k-dimensional meshes of size t₁²×t₂²×?×tk² each can be embedded in an n-dimensional crossed cube with unit dilation, where and max1?i?k{ti}?n−2m−1. This result means that a family of mesh-structured parallel algorithms can be executed on a same crossed cube efficiently and in parallel. Our work extends some recently obtained results.     

基于顶点度数的完全独立生成树研究

在计算机互连网络中,完全独立生成树在信息的可靠传输、并行传输、安全分发等方面具有重要的作用。假设图G中存在n棵生成树T₁,T₂,…,T_n,若对于图G中任意两个顶点u和v,满足u和v之间的路径在这n棵树中都是顶点不相交的,则称这n棵树为完全独立生成树(CISTs)。在2015年,Chang等人证明了对于包含n(n≥6)个顶点的任意图G,如果图G的最小顶点度数至少为n－2,那么,G中存在至少 n/3 棵CISTs[1]。在Chang等人的基础上,文中继续深入研究了图G中顶点度数和CISTs的棵数之间的关系。对于包含n(n≥5) 个顶点的任意图G,假设图G的最小顶点度数至少为n－2,得出度数为n－2的顶点的个数、度数为n－1的顶点的个数与图G中CISTs的棵数之间关系的推导等式,并证明了其正确性,从而改进了文献[1]中的结果。     

基于元胞遗传机制的虚拟网络映射算法

满足节点和链路约束条件的虚拟网络请求最优映射问题是NP-难问题,粒子群算法和遗传算法等启发式算法是解决这类问题的主要手段。这类启发式算法从数学模型优化的角度来求解问题,但未考虑虚拟网络映射节点本身的变化对最优解的影响,存在收敛速度较慢和容易陷入局部最优解的问题。文中将元胞遗传机制引入虚拟网络映射问题中,提出了虚拟网络映射算法VNE-CGA。该算法利用元胞自动机对节点建模,使用“B4567/S1234”规则来替代传统遗传算法中的交叉操作;通过对邻居的学习来指导个体的寻优过程,弥补了传统遗传算法的固有缺陷,最终提高了虚拟网络请求的接受率以及底层物理网络的运营收益。     

State explosion in almost-sure probabilistic reachability

We show that the problem of reaching a state set with probability 1 in probabilistic-nondeterministic systems operating in parallel is EXPTIME-complete. We then show that this probabilistic reachability problem is EXPTIME-complete also for probabilistic timed automata.     

Optimal book embeddings of the FFT, benes, and barrel shifter networks

This paper gives 3-page book embeddings of three important interconnection networks: the FFT network, the Benes rearrangeable permutation network, and the barrel shifter network. Since all three networks are eventually nonplanar, they require three pages and the present embeddings are optimal. Also, the embeddings have pages of comparable widths.The embeddings of the FFT and barrel shifter networks are obtained by decomposing these recursively defined networks into smaller copies of themselves and using induction. The embedding of the Benes network uses a novel decomposition of the network into eight copies of a smaller FFT network.This work was accomplished as a part of the MITRE Corporation's Independent Research and Development Program.     

On time reduction and simulation in cellular spaces

We prove a generalized and corrected version of the time reduction theorem for cellular spaces. One basic tool for investigations in this field is the concept of simulation between systems of automata. We propose a general formal definition of the intuitive concept and relate it to the notions which appear in the literature     

Effects of cell size and configuration in cellular automata based prey–predator modelling

Cellular automata (CA) have shown to be a viable approach in ecological modelling, in particular when dealing with local interactions between species and their environment. In CA modelling complex patterns emerge on a global scale through the evolution of interactions at a local level. Although the validity of a cell-based approach has successfully been demonstrated in numerous cases, very few studies have been reported that address the effects of cell size and configuration on the behaviours of CA-based models. In this paper, the performance of a cellular automaton based prey–predator model (EcoCA) developed by the author was first calibrated against the classical Lotka–Volterra (LV) model. The model was then used to investigate effects of cell size and cellular configurations (viz. the ‘computational stencil’). By setting up systematic simulation scenarios it was observed that the choice of a particular cell size has a clear effect on the resulting spatial patterns, while different cellular configurations affect both spatial patterns and system stability. On the basis of these findings, it is proposed to use the principal spatial scale of the studied ecosystem as CA model cell size and to apply the Moore type cell configuration. Methods for identifying principal spatial scales have been developed and are presented here.     

Characterizing the scale sensitivity of the cellular automata simulated urban growth: A case study of the Seberang Perai Region, Penang State, Malaysia

In modeling the complex behaviour of urban systems using a cellular automata approach, scale is an important concept in representing space since the result obtained at specific scale shall not be expected to be valid at another scale. The selection of scale, however, has often been taken for granted on the basis of information available to be mapped. Although it is desirable to run a model with fine spatial scale datasets, such datasets may well be costly to collect and add computational expenses in processing. This article investigates the effect of changing scale on the performance of a GIS-based cellular automata (CA) model developed to simulate the spatial pattern of urban growth. The sensitivity of scale of the input data used to parameterize the model was undertaken by evaluating the resulting prediction accuracy of the model and the morphology of urban areas. It seemed that the model managed to perform well and produce realistic urban form only up to specific range of scale. Thus, the selection of scale to represent urban system under consideration has to be undertaken with care, in order to ensure that the output produced maintains the overall accuracy of the model and morphology of urban areas.     

On the edge-tenacity of the middle graph of a graph

We consider the problem of efficiently breaking a graph into small components by removing edges. One measure of how easily this can be done is the edge-tenacity. Given a set of edges of G, the score of S is defined as sc(S)=[| S|+τ (G?S)]/[w(G?S)]. Formally, the edge-tenacity of a graph G is defined as T′(G)=min sc(S), where the minimum is taken over all edge-sets S of G. A subset S of E(G) is said to be a T′-set of G if T′(G)=sc(S). Note that if G is disconnected, the set S may be empty. For any graph G, τ(G?S) is the number of vertices in the largest component of G?S and w(G?S) is the number of components of G?S. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. In this paper, we give the edge-tenacity of the middle graph of specific families of graphs and its relationships with other parameters.     

A cellular learning automata-based deployment strategy for mobile wireless sensor networks

One important problem which may arise in designing a deployment strategy for a wireless sensor network is how to deploy a specific number of sensor nodes throughout an unknown network area so that the covered section of the area is maximized. In a mobile sensor network, this problem can be addressed by first deploying sensor nodes randomly in some initial positions within the area of the network, and then letting sensor nodes to move around and find their best positions according to the positions of their neighboring nodes. The problem becomes more complicated if sensor nodes have no information about their positions or even their relative distances to each other. In this paper, we propose a cellular learning automata-based deployment strategy which guides the movements of sensor nodes within the area of the network without any sensor to know its position or its relative distance to other sensors. In the proposed algorithm, the learning automaton in each node in cooperation with the learning automata in the neighboring nodes controls the movements of the node in order to attain high coverage. Experimental results have shown that in noise-free environments, the proposed algorithm can compete with the existing algorithms such as PF, DSSA, IDCA, and VEC in terms of network coverage. It has also been shown that in noisy environments, where utilized location estimation techniques such as GPS-based devices and localization algorithms experience inaccuracies in their measurements, or the movements of sensor nodes are not perfect and follow a probabilistic motion model, the proposed algorithm outperforms the existing algorithms in terms of network coverage.     

A simple graph theoretic characterization of reachability for positive linear systems

In this paper we consider discrete-time linear positive systems, that is systems defined by a pair (A,B) of non-negative matrices. We study the reachability of such systems which in this case amounts to the freedom of steering the state in the positive orthant by using non-negative control sequences. This problem was solved recently [Canonical forms for positive discrete-time linear control systems, Linear Algebra Appl., 310 (2000) 49]. However we derive here necessary and sufficient conditions for reachability in a simpler and more compact form. These conditions are expressed in terms of particular paths in the graph which is naturally associated with the system.