ﻻ يوجد ملخص باللغة العربية
We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two states 0 (passive) and 1 (active). The states of the nodes are updated in parallel following a local totalistic rule, i.e., depending only on the sum of active states. Four families of totalistic rules are considered: linear or matrix defined rules (a node takes state 1 if each of its neighbours is in state 1), threshold rules (a node takes state 1 if the sum of its neighbours exceed a threshold), isolated rules (a node takes state 1 if the sum of its neighbours equals to some single number) and interval rule (a node takes state 1 if the sum of its neighbours belong to some discrete interval). We focus in studying the simulation capabilities of the dynamics of each of the latter classes. In particular, we show that totalistic automata networks governed by matrix defined rules can only implement constant functions and other matrix defined functions. In addition, we show that t by threshold rules can generate any monotone Boolean functions. Finally, we show that networks driven by isolated and the interval rules exhibit a very rich spectrum of boolean functions as they can, in fact, implement any arbitrary Boolean functions. We complement this results by studying experimentally the set of different Boolean functions generated by totalistic rules on random graphs.
In this paper, we study reversibility of one-dimensional(1D) linear cellular automata(LCA) under null boundary condition, whose core problems have been divided into two main parts: calculating the period of reversibility and verifying the reversibili
This talk advocates intrinsic universality as a notion to identify simple cellular automata with complex computational behavior. After an historical introduction and proper definitions of intrinsic universality, which is discussed with respect to Tur
We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high dimensional expansion, which coincides with the earlier definition in terms of two-sided link expanders. Using this defin
We present an intuitive formalism for implementing cellular automata on arbitrary topologies. By that means, we identify a symmetry operation in the class of elementary cellular automata. Moreover, we determine the subset of topologically sensitive e
We first show that given a $k_1$-letter quantum finite automata $mathcal{A}_1$ and a $k_2$-letter quantum finite automata $mathcal{A}_2$ over the same input alphabet $Sigma$, they are equivalent if and only if they are $(n_1^2+n_2^2-1)|Sigma|^{k-1}+k