-------------------------------------------------------------------------------
                                       
                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
			  C O L L O Q U I U M
                                       
		       Wednesday January 31, 1996
                                       
			        3:00pm 
		       (Coffee served at 2:45pm)

                                       
			 Seminar Room / MCS 135
                                       

-------------------------------------------------------------------------------

	Information Loss in Simple One-Dimensional Cellular Automata

			      Kihong Park
			   Boston University

   In this talk, I will present some recent work on the ``forgetfulness''
   of simple, one-dimensional cellular automata. Cellular automata are one
   of the simplest models of distributed computing, and an interesting
   question concerns the ability of a cellular automaton to perform useful
   computation (in one extreme, preserving a single bit of information)
   when subject to transient faults.
   
   One- and two-dimensional cellular automata known to be fault-tolerant
   are very complex; on the other hand, only very simple cellular automata
   have actually been proven to lack fault-tolerance (i.e., to be
   mixing). The latter either require large error probability or belong to
   the small family of two-state nearest-neighbor monotonic rules (e.g.,
   local majority voting).
   
   For a certain simple automaton called the soldiers rule, this problem
   has intrigued researchers for the last two decades due to its superior
   deterministic robustness vis-a-vis local majority voting. That is, in
   the absence of errors, it eliminates any finite island of disturbance
   from an initial configuration of otherwise all 0's or all 1's.
   
   We will show that a variant of the soldiers rule called two-line voting,
   which also possesses the robustness property, loses all information
   about its initial state (mixing property) when subject to small,
   strongly biased noise.  Moreover, we give bounds on the rate of
   information loss (relaxation time) which show that indeed the robustness
   property enables information to be retained longer than local majority
   voting.
   
(Joint work with Peter Gacs.)
-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
   For more information contact Prof. Mark Crovella <crovella@bu.edu>
-------------------------------------------------------------------------------