Fundamenta Informaticae - Volume 87, issue 2

Article Type: Other

Citation: Fundamenta Informaticae, vol. 87, no. 2, pp. i-ii, 2008

Authors: Ganguly, Niloy | Sikdar, Biplab K. | Chaudhuri, P. Pal

Article Type: Research Article

Abstract: This paper reports the complete characterization of additive cellular automaton (ACA) that employs xor and xnor logic to realize its next state function. Compared to linear cellular automaton (LCA) [3], which employs only xor logic in its next state function, an ACA displays much more wider varieties of state transition behavior leading to enhanced computing power. An analytical framework is developed to characterize the cyclic vector subspaces of an ACA that can be derived from careful …analysis of the vector subspaces covered by the LCA. A scheme is proposed to explore the ACA structures having different state transition behavior than that of its LCA counterpart. The reported theoretical analysis justifies the nature of differences. Show more

Keywords: Cellular Automata, Additive Cellular Automata, Cycle Structure, Cyclic Vector Subspaces

Citation: Fundamenta Informaticae, vol. 87, no. 2, pp. 137-154, 2008

Authors: Umeo, Hiroshi | Uchino, Hiroki

Article Type: Research Article

Abstract: The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed so far. In the present paper, we propose a new optimum-time algorithm for synchronizing two-dimensional cellular automata. The algorithm can synchronize any two-dimensional rectangle array of size m × n in optimum m + n + max(m, n) − 3 steps. A partial implementation of the algorithm for small …cellular arrays is also given. Show more

Keywords: Cellular automaton, Firing squad synchronization problem

Citation: Fundamenta Informaticae, vol. 87, no. 2, pp. 155-164, 2008

Authors: Flocchini, Paola | Cezar, Vladimir

Article Type: Research Article

Abstract: Continuous cellular automata (or coupled map lattices) are cellular automata where the state of the cells are real values in [0, 1] and the local transition rule is a real function. The classical observation medium for cellular automata, whether Boolean or continuous, is the space-time diagram, where successive rows correspond to successive configurations in time. In this paper we introduce a different way to visualize the evolution of continuous cellular automata called Radial Representation and we …employ it to observe a particular class of continuous cellular automata called fuzzy cellular automata (FCA), where the local rule is the "fuzzification" of the disjunctive normal form that describes the local rule of the corresponding Boolean cellular automata. Our new visualization method reveals interesting dynamics that are not easily observable with the space-time diagram. In particular, it allows us to detect the quick emergence of spatial correlations among cells and to observe that all circular FCA from random initial configurations appear to converge towards an asymptotic periodic behavior. We propose an empirical classification of FCA based on the length of the observed periodic behavior: interestingly, all the minimum periods that we observe are of lengths one, two, four, or n (where n is the size of a configuration). Show more

Keywords: Continuous Cellular Automata, Fuzzy Cellular Automata, Visualization of dynamics, Evolution, Asymptotic Behavior

Citation: Fundamenta Informaticae, vol. 87, no. 2, pp. 165-183, 2008

Authors: Basu, Subhasree | Basu, Sumita

Article Type: Research Article

Abstract: A linear array of interconnected fuzzy automaton is called linear fuzzy cellular automaton. It is shown that the language class of linear fuzzy cellular automata strictly contains the language class of linear cellular automata. This justifies the wide spread use of linear fuzzy cellular automaton as is evident from the literature. In this paper a special type of cellular automaton (CA) model is investigated. This CA model computes effect due to interaction of neighboring …cells and effect due to external disturbance on the cells simultaneously. The transition due to both the effects may be represented by a single function which is the composition of two functions. Further it is shown that the class of language accepted by linear hybrid fuzzy cellular automata is included in the class of language accepted by linear hybrid fuzzy cellular automata with external input(HFCAI). HFCAI is useful for computing growth in evolutionary systems which are also affected by external cause. Show more

Keywords: Cellular automata, Fuzzy set, Formal languages, Parallel computing

Citation: Fundamenta Informaticae, vol. 87, no. 2, pp. 185-205, 2008

Authors: Bandini, Stefania | Vanneschi, Leonardo | Wuensche, Andrew | Shehata, Alessandro Bahgat

Article Type: Research Article

Abstract: This paper presents a general framework to automatically generate rules that produce given spatial patterns in complex systems. The proposed framework integrates Genetic Algorithms with Artificial Neural Networks or Support Vector Machines. Here, it is tested on a well known 3-values, 6-neighbors, k-totalistic cellular automata rule called the "burning paper" rule. Results are encouraging and should pave the way for the use of the proposed framework in real-life complex systems models.

Keywords: Complex Systems, Cellular Automata, Pattern Recognition, Automatic Rule Generation, Machine Learning, Genetic Algorithms, Artificial Neural Networks, Support VectorMachines

Citation: Fundamenta Informaticae, vol. 87, no. 2, pp. 207-226, 2008

Authors: Moitra, Debashis | Dhar, S. | Mallick, J.M. | Sadhu, S. | Sikdar, Biplab K.

Article Type: Research Article

Abstract: This work proposes graceful application of cellular automata (CA) to address a well known design problem in civil engineering. A large number of design alternatives exists regarding the choice of bracing pattern and the placing of braces in a tall steel building frame. The target is to find a cost optimal steel structure through proper placing of braces. In the conventional design procedure, based on the principles of structural engineering, an extremely large number of design …alternatives exists, making it nearly impossible to arrive at an appropriate design of the bracing system that may lead to optimum design of the entire structure. The proposed design scheme, developed around the GF(2^{3} ) CA, offers better alternatives and an easier way to arrive at the near-optimum solution in zero time. The GF(2^{3} ) CA, defined in Galois extension field, suits the modeling of different braces that are conventionally considered for designing multi-storied steel building frames. A CA state on the other hand, corresponds to bracing pattern of a storey and can be tuned to achieve the desired solution. The exhaustive experimental results point to the fact that the proposed CA based approach is most effective, while considering the design of tall building frames, and can reuse a design for scalability. Show more

Keywords: Cellular Automata, steel building frame, bracing pattern

Citation: Fundamenta Informaticae, vol. 87, no. 2, pp. 227-245, 2008

Authors: Rongo, Rocco | Spataro, William | D'Ambrosio, Donato | Vittoria Avolio, Maria | Trunfio, Giuseppe A. | Di Gregorio, Salvatore

Article Type: Research Article

Abstract: A hybrid technique based on Cellular Automata and Genetic Algorithms has been used for modeling lava flows on Mt Etna volcano (Italy). In particular, a Parallel Master-Slave Genetic Algorithm has been applied to evolve a two dimensional Cellular Automatamodel for "aa"-type lava flows, typical of the considered study area. Specifically, the 2001 Etnean Nicolosi case study has been considered for model calibration, while a subsequent validation phase has been performed by considering …further events occurred in the same area. Results have confirmed both the goodness of the cellular automata simulation model and of the genetic algorithm employed for its calibration. An application concerning hazard evaluation has been subsequently performed on a vast area of the volcano, regarding different types of vulnerability assessments. Results have pointed out the validity of the methodology and its usefulness for Civil Defence purposes. Show more

Keywords: Cellular Automata, Lava flows, Simulation, Modeling, Genetic Algorithms, Parallel Computing

Citation: Fundamenta Informaticae, vol. 87, no. 2, pp. 247-267, 2008