Abstract: We study a cellular automaton (CA) model of information dynamics on a single hypha of a fungal mycelium. Such a filament is divided in compartments (here also called cells) by septa. These septa are invaginations of the cell wall and their pores allow for the flow of cytoplasm between compartments and hyphae. The septal pores of the fungal phylum of the Ascomycota can be closed by organelles called Woronin bodies. Septal closure is increased when the septa become older and when exposed to stress conditions. Thus, Woronin bodies act as informational flow valves. The one-dimensional fungal automaton is a binary-state ternary neighborhood CA, where every compartment follows one of the elementary cellular automaton (ECA) rules if its pores are open and either remains in state 0 (first species of fungal automata) or its previous state (second species of fungal automata) if its pores are closed. The Woronin bodies closing the pores are also governed by ECA rules. We analyze a structure of the composition space of cell-state transition and pore-state transition rules and the complexity of fungal automata with just a few Woronin bodies, and exemplify several important local events in the automaton dynamics.

Abstract: We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a non-zero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the two-dimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NP-Complete.

Abstract: In the last twenty years an important effort in brain sciences, especially in cognitive science, has been the development of mathematical tool that can deal with the complexity of extensive recordings corresponding to the neuronal activity obtained from hundreds of neurons. We discuss here along with some historical issues, advantages and limitations of Artificial Neural Networks (ANN) that can help to understand how simple brain circuits work and whether ANN can be helpful to understand brain neural complexity.

Abstract: Given an elementary cellular automaton and a cell v, we define the stability decision problem as the determination of whether or not the state of cell v will ever change, at least once, during the time evolution of the rule, over a finite input configuration. Here, we perform the study of the entire elementary cellular automata rule space, for the two possible decision cases of the problem, namely, changes in v from state 0 to 1 (0 -> 1), and the other way round (1 -> 0). Out of the 256 elementary cellular automata, we show that for all of them, at least one of the two decision problems is in the NC complexity class.

Abstract: The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most cases. In this article, we introduce necessary conditions for a cellular automaton to be “universal”, according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of space-time rescaling and it is intrinsic to the model of cellular automata. intrinsic universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed us to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, were not intrinsically universal. (C) 2010 Elsevier B.V. All rights reserved.

Abstract: Consider an elementary cellular automaton (ECA) under periodic boundary conditions. Given an arbitrary partition of the set of vertices we consider the block updating, i.e. the automaton's local function is applied from the first to the last set of the partition such that vertices belonging to the same set are updated synchronously. The automaton is said block-invariant if the set of periodic configurations is independent of the choice of the block updating. When the sets of the partition are singletons we have the sequential updating: vertices are updated one by one following a permutation pi. In [5] the authors analyzed the pi-invariance of the 2(8) = 256 possible ECA rules (or the 88 non-redundant rules subset). Their main result was that for all n > 3, exactly 41 of these non-redundant rules are pi-invariant. In this paper we determine the subset of these 41 rules that are block invariant. More precisely, for all n > 3, exactly 15 of these rules are block invariant. Moreover, we deduce that block invariance also implies that the attractor structure itself is independent of the choice of the block update.

Abstract: In this paper we introduce automata networks to model some features of the emergence of a vocabulary related with the naming game model. We study the dynamical behaviour (attractors and convergence) of extremal and majority local functions.

Abstract: Cellular automata are locally defined, homogeneous dynamical systems, discrete in space, time and state variables. Within the context of one-dimensional, binary, cellular automata operating on cyclic configurations of odd length, we consider the general decision problem: if the initial configuration satisfies a given property, the lattice should converge to the fixed-point of all 1s ((1) over right arrow), or to (0) over right arrow, otherwise. Two problems in this category have been widely studied in the literature, the parity problem [1] and the density classification task [4]. We are interested in determining all cellular automata rules with neighborhood sizes of 2, 3, 4 and 5 cells (i.e., radius r of 0.5, 1, 1.5 and 2.5) that solve decision problems of the previous type. We have demonstrated a theorem that, for any given rule in those spaces, ensures the non existence of fixed points other than (0) over right arrow and (1) over right arrow for configurations of size larger than 2(2r), provided that the rule does not support different fixed points for any configuration with size smaller than or equal to 2(2r). In addition, we have a proposition that ensures the convergence to only (0) over right arrow or (1) over right arrow of any initial configuration, if the rule complies with given conditions. By means of theoretical and computational approaches, we determined that: for the rule spaces defined by radius 0.5 and r = 1, only 1 and 2 rules, respectively, converge to (1) over right arrow or (0) over right arrow, to any initial configuration, and both recognize the same language, and for the rule space defined by radius r = 1.5, 40 rules satisfy this condition and recognize 4 different languages. Finally, for the radius 2 space, out of the 4,294,967,296 different rules, we were able to significantly filter it out, down to 40,941 candidate rules. We hope such an extensive mining should unveil new decision problems of the type widely studied in the literature.

Abstract: Decision problems addressed by cellular automata have been historically expressed either as determining whether initial configurations would belong to a given language, or as classifying the initial configurations according to a property in them. Unlike traditional approaches in language recognition, classification problems have typically relied upon cyclic configurations and fully paralell (two-way) update of the cells, which render the action of the cellular automaton relatively less controllable and difficult to analyse. Although the notion of cyclic languages have been studied in the wider realm of formal languages, only recently a more systematic attempt has come into play in respect to cellular automata with fully parallel update. With the goal of contributing to this effort, we propose a unified definition of classification problem for one-dimensional, binary cellular automata, from which various known problems are couched in and novel ones are defined, and analyse the solvability of the new problems. Such a unified perspective aims at increasing existing knowledge about classification problems by cellular automata over cyclic configurations and parallel update.

Abstract: Cellular automata are locally-defined, synchronous, homogeneous, fully discrete dynamical systems. In spite of their typically simple local behaviour, many are capable of showing complex emergent behaviour. When looking at their time-evolution, one may be interested in studying their qualitative dynamical behaviour. One way to group rules that display the same qualitative behaviour is by defining symmetries that map rules to others, the simplest way being by means of permutations in the set of state variables and reflections in their neighbourhood definitions, therefore defining equivalence classes. Here, we introduce the notion of shift-equivalence as another kind of symmetry, now relative to the concept of translation. After defining the notion and showing it indeed defines an equivalence relation, we extend the usual characterisation of dynamical equivalence and use it to partition some specific binary cellular automata rule spaces. Finally, we give a characterisation of the class of shift-equivalent rules in terms of the local transition functions of the cellular automata in the class, by providing an algorithm to compute the members of the class, for any k-ary, one-dimensional rule. (C) 2018 Elsevier B.V. All rights reserved.