Fundamenta Informaticae - Volume 171, issue 1-4

Authors: Dennunzio, Alberto | Păun, Gheorghe | Rozenberg, Grzegorz | Zandron, Claudio

Article Type: Other

DOI: 10.3233/FI-2020-1868

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. v-vi, 2020

Authors: Anselmo, Marcella | Giammarresi, Dora | Madonia, Maria

Article Type: Research Article

Abstract: We introduce the two-dimensional rational automata (RA) to recognize languages of pictures, as an extension of the finite automata for strings. A RA processes a picture column by column changing its state. The states are columns of symbols, too. The transition function is realized by a transducer. We prove that RA recognize the family REC of languages recognized by tiling systems. Moreover, RA provide a uniform setting for a lot of important notions, techniques and results presented in the last decades for recognizable two-dimensional languages. The model is also very flexible. In fact, there can be imposed restrictions …or added features to easily interesting new classes and examples or to capture known families of languages. Show more

DOI: 10.3233/FI-2020-1869

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 1-17, 2020

Authors: Bandini, Stefania | Crociani, Luca | Gorrini, Andrea | Nishinari, Katsuhiro | Vizzari, Giuseppe

Article Type: Research Article

Abstract: Models for the automated analysis and simulation of the complex phenomena observable in built environment crowded by pedestrians have been studied for over thirty years. Nonetheless, one of the commonly agreed upon rules guiding regulation of distance among pedestrian, i.e. proxemics, was defined and discussed in static settings, whereas scenarios of interest generally deal with individual and collective movements in crowds. The present paper presents a systemic perspective on the research aimed at defining a dynamic form of proxemics. The paper firstly reports the results of an experiment focused on proxemics and pedestrians personal space, as the hidden dimension of …human spatial behavior in crowded environments. We propose a representation of personal space through discrete potentials and an innovative crowding estimation method (i.e. Cumulative Mean Crowding ), going beyond simple perceived density evaluation. The experimental setting is introduced and applied to appraise the potential impact of this novel pedestrian perception mechanism on innovative simulation models. Show more

Keywords: Modeling and Simulations, Cellular Automata, Pedestrian Crowds, Crowding

DOI: 10.3233/FI-2020-1870

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 19-38, 2020

Authors: Bernardinello, Luca | Ferigato, Carlo | Pomello, Lucia

Article Type: Research Article

Abstract: An orthogonality space is a set endowed with a symmetric and irreflexive binary relation (an orthogonality relation). In a partially ordered set modelling a concurrent process, two such binary relations can be defined: a causal dependence relation and a concurrency relation, and two distinct orthogonality spaces are consequently obtained. When the condition of N-density holds on both these orthogonality spaces, we study the orthomodular poset formed by closed sets defined according to Dacey. We show that the condition originally imposed by Dacey on the orthogonality spaces for obtaining an orthomodular poset from his closed sets is in fact …equivalent to N-density. The requirement of N-density was as well fundamental in a previous work on orthogonality spaces with the concurrency relation. Starting from a partially ordered set modelling a concurrent process, we obtain dual results for orthogonality spaces with the causal dependence relation in respect to orthogonality spaces with the concurrency relation. Show more

DOI: 10.3233/FI-2020-1871

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 39-56, 2020

Authors: Besozzi, Daniela | Manzoni, Luca | Nobile, Marco S. | Spolaor, Simone | Castelli, Mauro | Vanneschi, Leonardo | Cazzaniga, Paolo | Ruberto, Stefano | Rundo, Leonardo | Tangherloni, Andrea

Article Type: Research Article

Abstract: Computational Intelligence (CI) is a computer science discipline encompassing the theory, design, development and application of biologically and linguistically derived computational paradigms. Traditionally, the main elements of CI are Evolutionary Computation, Swarm Intelligence, Fuzzy Logic, and Neural Networks. CI aims at proposing new algorithms able to solve complex computational problems by taking inspiration from natural phenomena. In an intriguing turn of events, these nature-inspired methods have been widely adopted to investigate a plethora of problems related to nature itself. In this paper we present a variety of CI methods applied to three problems in life sciences, highlighting their effectiveness: we …describe how protein folding can be faced by exploiting Genetic Programming, the inference of haplotypes can be tackled using Genetic Algorithms, and the estimation of biochemical kinetic parameters can be performed by means of Swarm Intelligence. We show that CI methods can generate very high quality solutions, providing a sound methodology to solve complex optimization problems in life sciences. Show more

Keywords: Computational Intelligence, Evolutionary Computation, Swarm Intelligence, Genetic Programming, Genetic Algorithm, Particle Swarm Optimization, Protein Folding, Haplotype Assembly, Parameter Estimation

DOI: 10.3233/FI-2020-1872

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 57-80, 2020

Authors: Bonizzoni, Paola | De Felice, Clelia | Zaccagnino, Rocco | Zizza, Rosalba

Article Type: Research Article

Abstract: Circular splicing systems are a mathematical model, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A , an initial set I of circular words, and a set R of rules. A circular splicing language is a language generated by a circular splicing system. An open problem is to characterize regular circular splicing languages and the corresponding circular splicing systems. In this framework an important role is played by unavoidable sets . These sets have been considered in several contexts. In particular, Ehrenfeucht, Haussler and Rozenberg (1983) proved the following …generalization of a famous Higman’s theorem: the quasi-order induced by insertions of words from a fixed finite set is a well-quasi-order if and only if the finite set is unavoidable . In this paper we survey the known relations between unavoidable sets and regular circular languages. Motivated by these connections we give an alternative and simpler proof of the Ehrenfeucht, Haussler and Rozenberg result. Our proof is strongly based on a known characterization of unavoidable sets in terms of graphs associated with them. Show more

Keywords: Formal languages, Regular languages, Unavoidable sets, Circular splicing languages

DOI: 10.3233/FI-2020-1873

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 81-95, 2020

Authors: Castiglione, Giuseppa | Mantaci, Sabrina | Restivo, Antonio

Article Type: Research Article

Abstract: In this paper we investigate similarity measures based on minimal absent words, introduced by Chairungsee and Crochemore in [1]. They make use of a length-weighted index on a sample set corresponding to the symmetric difference M (x )ΔM (y ) of the minimal absent words M (x ) and M (y ) of two sequences x and y , respectively. We first propose a variant of this measure by choosing as a sample set a proper subset 𝒟(x , y ) of M (x )ΔM (y ), which appears to be more appropriate for distinguishing x and y …. From the algebraic point of view, we prove that 𝒟(x , y ) is the base of the ideal generated by M (x )ΔM (y ). We then remark that such measures are able to recognize whether the sequences x and y share a common structure, but they are not able to detect the difference on the number of occurrences of such a structure in the two sequences. In order to take into account such a multiplicity, we introduce the notion of multifactor, and define a new measure that uses both absent words and multifactors. Surprisingly, we prove that this similarity measure coincides with a distance on sequences introduced by Ehrenfeucht and Haussler in [2], in the context of block-moves strategies. In this way, our result creates a non trivial bridge between similarity measures based on absent words and those based on the block-moves approach. Show more

Keywords: Minimal absent words, similarity measures, sequence comparison

DOI: 10.3233/FI-2020-1874

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 97-112, 2020

Authors: Cruz, Daniel A. | Ferrari, Margherita Maria | Jonoska, Nataša | Nabergall, Lukas | Saito, Masahico

Article Type: Research Article

Abstract: A double occurrence word (DOW) is a word in which every symbol appears exactly twice; two DOWs are equivalent if one is a symbol-to-symbol image of the other. We consider the so called repeat pattern (αα ) and the return pattern (αα R ), with gaps allowed between the α ’s. These patterns generalize square and palindromic factors of DOWs, respectively. We introduce a notion of inserting repeat/return words into DOWs and study how two distinct insertions into the same word can produce equivalent DOWs. Given a DOW w , we characterize the structure of w which allows …two distinct insertions to yield equivalent DOWs. This characterization depends on the locations of the insertions and on the length of the inserted repeat/return words and implies that when one inserted word is a repeat word and the other is a return word, then both words must be trivial (i.e., have only one symbol). The characterization also introduces a method to generate families of words recursively. Show more

DOI: 10.3233/FI-2020-1875

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 113-132, 2020

Authors: Csuhaj-Varjú, Erzsébet | Vaszil, György

Article Type: Research Article

Abstract: P automata are accepting computing devices combining features of classical automata and membrane systems. In this paper we introduce P n -stack-automata, a restricted class of P automata that mimics the behaviour of n -stack automata. We show that for n = 1 these constructs describe the context-free language class and for n = 3 the class of quasi-realtime languages.

DOI: 10.3233/FI-2020-1876

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 133-149, 2020

Authors: Enaganti, Srujan Kumar | Kari, Lila | Ng, Timothy | Wang, Zihao

Article Type: Research Article

Abstract: In this paper we define and investigate a binary word operation that formalizes an experimentally observed outcome of DNA computations, performed to generate a small gene library, and implemented using a DNA recombination technique called Cross-pairing Polymerase Chain Reaction (XPCR). The word blending between two words αwγ 1 and γ 2 wβ that share a non-empty overlap w , results in αwβ . Interestingly, this phenomenon has been observed independently in linguistics, under the name “blend word” or “portmanteau”, and is responsible for the creation of words in the English language such as smog (smo ke + …fog ), labradoodle (labrador + poodle ), and Brangelina (Bra d + Angelina ). Technically, word blending is related to the binary word operation Latin product, the crossover operation, and simple splicing. We study closure properties of the families in the Chomsky hierarchy under word blending, language equations involving this operation, and its descriptional state complexity when applied to regular languages. We also define iterated word blending and show that, for a given alphabet, there are finitely many languages that can be obtained from an initial language by iterated word blending. Show more

DOI: 10.3233/FI-2020-1877

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 151-173, 2020

Authors: Ferretti, Claudio | Leporati, Alberto | Manzoni, Luca | Porreca, Antonio E.

Article Type: Research Article

Abstract: Reaction systems are a computational model inspired by the bio-chemical reactions that happen inside biological cells. They have been and currently are studied for their many nice theoretical properties. They are also a useful modeling tool for biochemical systems, but in order to be able to employ them effectively in the field the presence of efficient and widely available simulators is essential. Here we explore three different algorithms and implementations of the simulation, comparing them to the current state of the art. We also show that we can obtain performances comparable to GPU-based simulations on real-world systems by using a …carefully tuned CPU-based simulator. Show more

Keywords: Reaction Systems, Simulation of Biochemical Systems

DOI: 10.3233/FI-2020-1878

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 175-188, 2020

Authors: Formenti, Enrico | Perrot, Kévin

Article Type: Research Article

Abstract: Since their introduction in the 80s, sandpile models have raised interest for their simple definition and their surprising dynamical properties. In this survey we focus on the computational complexity of the prediction problem, namely, the complexity of knowing, given a finite configuration c and a cell x in c , if cell x will eventually become unstable. This is an attempt to formalize the intuitive notion of “behavioral complexity” that one easily observes in simulations. However, despite many efforts and nice results, the original question remains open: how hard is it to predict the two-dimensional sandpile model …of Bak, Tang and Wiesenfeld? Show more

DOI: 10.3233/FI-2020-1879

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 189-219, 2020

Authors: Gianola, Alessandro | Kasangian, Stefano | Manicardi, Desiree | Sabadini, Nicoletta | Schiavio, Filippo | Tini, Simone

Article Type: Research Article

Abstract: In this paper, we recall the basic features of the CospanSpan(Graph) algebra for the compositional description of reconfigurable hierarchical networks. In particular, we focus on compositionality and on the possibility of describing the interactions among physical/biological systems, using a parallel with communication operation not considered in the usual Kleene’s algebra. As a novel application, we give a complete compositional description in Span(Graph) of a simplified version of the heart system.

Keywords: Automata, Categories, Composition, Biological Systems

DOI: 10.3233/FI-2020-1880

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 221-237, 2020

Authors: Jalonen, Joonatan | Kari, Jarkko

Article Type: Research Article

Abstract: Ultimate expansivity extends concepts of expansivity and positive expansivity. We consider one-sided variants of ultimate expansivity and pseudo-orbit tracing property (also known as the shadowing property) for surjective one-dimensional cellular automata. We show that ultimately right (or left) expansive surjective cellular automata are chain-transitive; this improves a result by Boyle that expansive reversible cellular automata are chain-transitive. We then use this to show that left-sided pseudo-orbit tracing property and right-sided ultimate expansivity together imply pseudo-orbit tracing property for surjective cellular automata. This reproves some known results, most notably some of Nasu’s. Our result improves Nasu’s result by dropping an assumption …of chain-recurrence, however, we remark that this improvement can also be achieved using the Poincaré recurrence theorem. The pseudo-orbit tracing property implies that the trace subshifts of the cellular automaton are sofic shifts. We end by mentioning that among reversible cellular automata over full shifts we have examples of right expansive cellular automata with non-sofic traces, as well as examples of cellular automata with left pseudo-orbit tracing property but non-sofic traces, illustrating that neither assumption can be dropped from the theorem mentioned above. This paper is a generalized and improved version of a conference paper presented in AUTOMATA 2018. Show more

Keywords: cellular automata, expansivity, pseudo-orbit tracing property

DOI: 10.3233/FI-2020-1881

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 239-259, 2020

Authors: Kleijn, Jetty | Koutny, Maciej | Mikulski, Łukasz

Article Type: Research Article

Abstract: Reaction systems were introduced in order to provide an abstract model for the study of the biochemical processes that take place in the living cell. Processes of this kind are the result of the interactions between reactions and may be influenced by the environment. Thus, reaction systems can be considered as a model of (interactive) computation. In previous works, various equivalences defined directly on reaction systems and processes had been proposed and compared. These equivalences were all based on functional equivalence that compares a system’s behaviour at every stage of its execution. In this paper, in contrast, we investigate enabling …equivalence which focuses on the system behaviour only in specific stages of its evolution, namely those where all of its reactions are active. We discuss the effect of such an approach and, in particular, its relationship to a transition system representation of the system’s behaviour. Show more

Keywords: Reaction system, living cell, model of computation, functional equivalence, interactive process, context-independent process, transition system, enabling equivalence

DOI: 10.3233/FI-2020-1882

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 261-277, 2020

Authors: Maspero, Davide | Damiani, Chiara | Antoniotti, Marco | Graudenzi, Alex | Di Filippo, Marzia | Vanoni, Marco | Caravagna, Giulio | Colombo, Riccardo | Ramazzotti, Daniele | Pescini, Dario

Article Type: Research Article

Abstract: The metabolic processes related to the synthesis of the molecules needed for a new round of cell division underlie the complex behaviour of cell populations in multi-cellular systems, such as tissues and organs, whereas their deregulation can lead to pathological states, such as cancer. Even within genetically homogeneous populations, complex dynamics, such as population oscillations or the emergence of specific metabolic and/or proliferative patterns, may arise, and this aspect is highly amplified in systems characterized by extreme heterogeneity. To investigate the conditions and mechanisms that link metabolic processes to cell population dynamics, we here employ a previously introduced multi-scale …model of multi-cellular system, named FBCA (Flux Balance Analysis with Cellular Automata), which couples biomass accumulation, simulated via Flux Balance Analysis of a metabolic network, with the simulation of population and spatial dynamics via Cellular Potts Models. In this work, we investigate the influence that different modes of nutrients diffusion within the system may have on the emerging behaviour of cell populations. In our model, metabolic communication among cells is allowed by letting secreted metabolites to diffuse over the lattice, in addition to diffusion of nutrients from given sources. The inclusion of the diffusion processes in the model proved its effectiveness in characterizing plausible biological scenarios. Show more

Keywords: Multi-scale modeling, Cellular Potts Model, Flux Balance Analysis, Diffusion, Cancer development

DOI: 10.3233/FI-2020-1883

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 279-295, 2020

Authors: Orellana-Martín, David | Valencia-Cabrera, Luis | Riscos-Núñez, Agustín | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: Biological membranes play an active role in the evolution of cells over time. In the framework of Membrane Computing, P systems with active membranes capture this idea, and the possibility to increase the number of membranes during a computation. Classically, it has been considered, by using division rules, inspired in the mitosis process. Initially, the membranes in these models are supposed to have an electrical polarization (positive, negative or neutral) and the semantics is minimalist , in the sense that rules are applied in parallel, but in one transition step, each membrane can be the subject of at most one …rule of types communication, dissolution or division. This paper focuses on polarizationless P systems with active membranes in which membrane creation rules are considered instead of membrane division rules as a mechanism to construct an exponential workspace, expressed both in terms of number of objects and membranes, in linear time. Moreover, the minimalist semantics is considered and some complexity results are provided in this framework, allowing to tackle the P versus NP problem from a new perspective. An original frontier of the efficiency in this context is unveiled in this paper: allowing membrane creation rules to be applicable in any membrane of the system, instead of restricting them to only elementary membranes, yields a significant boost on the computational power. More precisely, only problems in P can be efficiently solved in the restricted case, while in the non-restricted case an efficient and uniform solution to a PSPACE -complete problem is provided. Show more

DOI: 10.3233/FI-2020-1884

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 297-311, 2020

Authors: Pan, Linqiang | Song, Bosheng

Article Type: Research Article

Abstract: P systems are a class of parallel computational models inspired by the structure and functioning of living cells, where all the evolution rules used in a system are initially set up and keep unchanged during a computation. In this work, inspired by the fact that chemical reactions in a cell can be affected by both the contents of the cell and the environmental conditions, we introduce a variant of P systems, called P systems with rule production and removal (abbreviated as RPR P systems), where rules in a system are dynamically changed during a computation, that is, at any computation …step new rules can be produced and some existing rules can be removed. The computational power of RPR P systems and catalytic RPR P systems is investigated. Specifically, it is proved that catalytic RPR P systems with one catalyst and one membrane are Turing universal; for purely catalytic RPR P systems, one membrane and two catalysts are enough for reaching Turing universality. Moreover, a uniform solution to the SAT problem is provided by using RPR P systems with membrane division. It is known that standard catalytic P systems with one catalyst and one membrane are not Turing universal. These results imply that rule production and removal is a powerful feature for the computational power of P systems. Show more

Keywords: Bio-inspired Computing, Membrane Computing, Catalytic P System, Universality, SAT Problem

DOI: 10.3233/FI-2020-1885

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 313-329, 2020

Authors: Petre, Luigia | Sanwal, Usman | Shah, Gohar | Panchal, Charmi | Tyagi, Dwitiya | Petre, Ion

Article Type: Research Article

Abstract: How robust is a healthcare system? How does a patient navigate the system and what is the cost (e.g., number of medical services required or number of times the medical provider had to be changed to get access to the required medical services) incurred from the first symptoms to getting cured? How will it fare in the wake to a sudden epidemic or a disaster? How are all of these affected by administrative decisions such as allocating/diminishing resources in various areas or centralising services? These are the questions motivating our study on a formal prototype model for a healthcare system. …We propose that a healthcare system can be understood as a distributed system with independent nodes (healthcare providers) computing according to their own resources and constraints, with tasks (patient needs) being allocated between the nodes. The questions about the healthcare system become in this context questions about resource availability and distribution between the nodes. We construct in this paper an Event-B model capturing the basic functionality of a simplified healthcare system: patients with different types of medical needs being allocated to suitable medical providers, and navigating between different providers for their turn for multi-step treatments. Show more

DOI: 10.3233/FI-2020-1886

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 331-343, 2020

Authors: Rundo, Leonardo | Militello, Carmelo | Vitabile, Salvatore | Russo, Giorgio | Sala, Evis | Gilardi, Maria Carla

Article Type: Research Article

Abstract: Natural phenomena and mechanisms have always intrigued humans, inspiring the design of effective solutions for real-world problems. Indeed, fascinating processes occur in nature, giving rise to an ever-increasing scientific interest. In everyday life, the amount of heterogeneous biomedical data is increasing more and more thanks to the advances in image acquisition modalities and high-throughput technologies. The automated analysis of these large-scale datasets creates new compelling challenges for data-driven and model-based computational methods. The application of intelligent algorithms, which mimic natural phenomena, is emerging as an effective paradigm for tackling complex problems, by considering the unique challenges and opportunities pertaining to …biomedical images. Therefore, the principal contribution of computer science research in life sciences concerns the proper combination of diverse and heterogeneous datasets—i.e., medical imaging modalities (considering also radiomics approaches), Electronic Health Record engines, multi-omics studies, and real-time monitoring—to provide a comprehensive clinical knowledge. In this paper, the state-of-the-art of nature-inspired medical image analysis methods is surveyed, aiming at establishing a common platform for beneficial exchanges among computer scientists and clinicians. In particular, this review focuses on the main natureinspired computational techniques applied to medical image analysis tasks, namely: physical processes, bio-inspired mathematical models, Evolutionary Computation, Swarm Intelligence, and neural computation. These frameworks, tightly coupled with Clinical Decision Support Systems, can be suitably applied to every phase of the clinical workflow. We show that the proper combination of quantitative imaging and healthcare informatics enables an in-depth understanding of molecular processes that can guide towards personalised patient care. Show more

Keywords: Nature-inspired computing, artificial intelligence, medical image analysis, biomedical data integration

DOI: 10.3233/FI-2020-1887

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 345-365, 2020

Authors: Simone, Pernice | Laura, Follia | Gianfranco, Balbo | Luciano, Milanesi | Giulia, Sartini | Niccoló, Totis | Pietro, Lió | Ivan, Merelli | Francesca, Cordero | Marco, Beccuti

Article Type: Research Article

Abstract: Computational Biology is a fast-growing field that is enriched by different data-driven methodological approaches and by findings and applications in a broad range of biological areas. Fundamental to these approaches are the mathematical and computational models used to describe the different states at microscopic (for example a biochemical reaction), mesoscopic (the signalling effects at tissue level), and macroscopic levels (physiological and pathological effects) of biological processes. In this paper we address the problem of combining two powerful classes of methodologies: Flux Balance Analysis (FBA) methods which are now producing a revolution in biotechnology and medicine, and Petri Nets (PNs) which …allow system generalisation and are central to various mathematical treatments, for example Ordinary Differential Equation (ODE) specification of the biosystem under study. While the former is limited to modelling metabolic networks, i.e. does not account for intermittent dynamical signalling events, the latter is hampered by the need for a large amount of metabolic data. A first result presented in this paper is the identification of three types of cross-talks between PNs and FBA methods and their dependencies on available data. We exemplify our insights with the analysis of a pancreatic cancer model. We discuss how our reasoning framework provides a biologically and mathematically grounded decision making setting for the integration of regulatory, signalling, and metabolic networks and greatly increases model interpretability and reusability. We discuss how the parameters of PN and FBA models can be tuned and combined together so to highlight the computational effort needed to perform this task. We conclude with speculations and suggestions on this new promising research direction. Show more

Keywords: Computational biology, Petri Nets and Flux Balance Analysis

DOI: 10.3233/FI-2020-1888

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 367-392, 2020

Authors: Umeo, Hiroshi

Article Type: Research Article

Abstract: The synchronization in cellular automata has been known as the firing squad synchronization problem (FSSP) since its development, in which it was originally proposed by Myhill and reported by Moore in 1964 to synchronize all/some parts of self-reproducing cellular automata. The problem has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed not only for one-dimensional (1D) arrays but also for multi-dimensional arrays. In the present paper, we construct a survey on the study of FSSP algorithms, focusing on recent developments.

Keywords: Cellular automaton, Firing squad synchronization problem, FSSP

DOI: 10.3233/FI-2020-1889

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 393-419, 2020