Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGenerating Boolean Functions on Totalistic Automata Networks
146
0
0.0
(
0
)
Added by
Mart\\'in R\\'ios-Wilson
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 reversibility in a period. With existing methods, the time and space complexity of these two parts are still too expensive to be employed. So the process soon becomes totally incalculable with a slightly big size, which greatly limits its application. In this paper, we set out to solve these two problems using two efficient algorithms, which make it possible to solve reversible LCA of very large size. Furthermore, we provide an interesting perspective to conversely generate 1D LCA from a given period of reversibility. Due to our methods efficiency, we can calculate the reversible LCA with large size, which has much potential to enhance security in cryptography system.
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 Turing and circuit universality, we discuss construction methods for small intrinsically universal cellular automata before discussing techniques for proving non universality.
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 definition, we describe an analogue of the Fourier expansion and the Fourier levels of the Boolean hypercube for simplicial complexes. Our analogue is a decomposition into approximate eigenspaces of random walks associated with the simplicial complexes. We then use this decomposition to extend the Friedgut-Kalai-Naor theorem to high-dimensional expanders. Our results demonstrate that a high-dimensional expander can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing only $|X(k-1)|=O(n)$ points in contrast to $binom{n}{k}$ points in the $(k)$-slice (which consists of all $n$-bit strings with exactly $k$ ones). Our random-walk definition and the decomposition has the additional advantage that they extend to the more general setting of posets, which include both high-dimensional expanders and the Grassmann poset, which appears in recent works on the unique games conjecture.
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 elementary cellular automata and find that the overall number of complex patterns decreases under increasing neighborhood size in regular graphs. As exemplary applications, we apply the formalism to complex networks and compare the potential of scale-free graphs and metabolic networks to generate complex dynamics.
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$-equivalent where $n_1$, $i=1,2$, are the numbers of state in $mathcal{A}_i$ respectively, and $k=max{k_1,k_2}$. By applying a method, due to the author, used to deal with the equivalence problem of {it measure many one-way quantum finite automata}, we also show that a $k_1$-letter measure many quantum finite automaton $mathcal{A}_1$ and a $k_2$-letter measure many quantum finite automaton $mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|Sigma|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the numbers of state in $mathcal{A}_i$ respectively, and $k=max{k_1,k_2}$. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for $k$-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether $L_{geqlambda}(mathcal{A}_1)=L_{geqlambda}(mathcal{A}_2)$ where $0<lambdaleq 1$ and $mathcal{A}_i$ are $k_i$-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for $k$-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
