Solutions And Algorithms For The Minimum All-Ones Problem

A cellular automaton is a discrete dynamical system that consists of an arrangement of basic components called cells together with a transition rule. In what follows we always assume that G = (V, E) is a finite connected simple undirected graph. Each vertex (cell) assumes one of the two states, viz. 0 or 1. An assignment of states to the vertices will be called a configuration. The behavior of the automaton is determined by a local transition rule. If X is a configuration at time t, Y is the configuration at time t+1 by the local transition rule on every cell (vertex), then Y is called the successor of X, and conversely, X is a predecessor of Y. One of the basic problem in the study of the evolution of configurations is to determine whether a given target configuration has a predecessor. This problem is referred as the predecessor existence problem (PEP) [25]. If given a bound β and the predecessor configuration is required to have cardinality at most β, this problem is called the bounded predecessor existence problem (BPEP). Given the interesting target configuration which is fixed to be 1, the vector with all components equal to 1, we study cellular automata based on two well-studied local transition rules σ~+-rule and σ-rule on graphs in this thesis.For the σ~+-rule, when the initial configuration is fixed to be 0 and the target configuration is fixed to be 1, the corresponding predecessor existence problem is also called σ~+ all-ones problem or all-ones problem [27] simply. An equivalent version of the all-ones problem was proposed by Peled in [22], where it was called the lamp lighting problem. Similarly, for the a-rule, when the initial configuration is fixed to be 0 and the target configuration is fixed to be 1, the corresponding predecessor existence problem is called σ all-ones problem. For the sake of convenience, a predecessor of the target configuration is also called a solution.The all-ones problem has been extensively studied recently, see Sutner [29, 31], Barua and Ramakrishnan [2] and Dodis and Winkler [11]. The existence of solutions of the all-ones problem for general graphs was solved already. Using linear algebra,...