home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 510 < prev    next >
Encoding:
Text File  |  1992-11-10  |  3.2 KB  |  102 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!decwrl!spool.mu.edu!umn.edu!news.cs.indiana.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!levine
  3. From: levine@symcom.math.uiuc.edu (Lenore Levine)
  4. Subject: Gacs Rule -- Summary of Related Papers
  5. Message-ID: <BxIsCq.FL5@news.cso.uiuc.edu>
  6. Sender: usenet@news.cso.uiuc.edu (Net Noise owner)
  7. Organization: University of Illinois at Urbana
  8. Date: Tue, 10 Nov 1992 21:43:32 GMT
  9. Lines: 91
  10.  
  11.  
  12. The first paper on the Gacs rule was published in Problems of
  13. Transmission of Information, in 1978. The Russian journal has been
  14. translated into English. There are two co-authors, Kurdyumov and Levin.
  15.  
  16. Here are two or three later papers that are probably related:
  17.  
  18. 1983       STOC         Gacs, Reliable Computation with Cellular Automata
  19. 1986   32  JCSS         Gacs, Reliable Computation with Cellular Automata
  20. 1989    5  ADVCR        Gacs, Self-Correcting Two-Dimensional Arrays
  21. 1985       STOC         Gacs & Reif, A Simple Three-Dimensional Real-Time Reliable Cellular Array
  22. 1988   36  JCSS         Gacs & Reif, A Simple Three-Dimensional Real-Time Reliable Cellular Array
  23.  
  24.  One piece of further work is this:
  25.  @ARTICLE{DeSaMaes92
  26.   ,AUTHOR = {de S\'a, Paula Gonzaga and Maes, Christian}
  27.   ,TITLE  = "The {G}\'acs-{K}urdyumov-{L}evin {A}utomaton Revisited"
  28.   ,JOURNAL = "Journal of Statistical Physics"
  29.   ,VOLUME = 67
  30.   ,NUMBER = {3/4}
  31.   ,PAGES = "607-622"
  32.   ,YEAR = 1992
  33.   ,Month = May
  34.  
  35. Some related papers:
  36.  
  37. This is Gray's proof of ergodicity for continuous-time monotonic
  38. nearest-neighbor rules.
  39.  
  40.  @ARTICLE{Gray82
  41.   ,AUTHOR = {Gray, Lawrence F.}
  42.   ,TITLE  = {The Positive Rates Problem for Attractive Nearest
  43. Neighbor Spin Systems on {\bf Z}}
  44.   ,JOURNAL = {Z.\ Wahrscheinlichkeitstheorie verw.\ Gebiete}
  45.   ,VOLUME = 61
  46.   ,PAGES = {389-404}
  47.   ,YEAR = 1982
  48.  }
  49.  
  50. This is Gray's proof for discrete time.
  51.  
  52.  @inproceedings{Gray87
  53.    ,author = "Gray, Lawrence F."
  54.    ,title = "The Behavior of Processes with Statistical Mechanical Properties"
  55.    ,booktitle = "Percolation Theory and Ergodic Theory of Infinite
  56. Particle Systems"
  57.    ,year = "1987"
  58.    ,pages = "131--167"
  59.    ,publisher= {Springer-Verlag}
  60.    }
  61.  
  62.  This is a relatively simple proof of Toom's rule.
  63.  
  64. @inproceedings{BermSim88,
  65.    author = "Berman, Piotr and Simon, Janos",
  66.    title = "Investigations of Fault-Tolerant Networks of Computers",
  67.    booktitle = "Proc. of the 20-th Annual ACM Symp. on the Theory of
  68. Computing",
  69.    year = "1988",
  70.    pages = "66 -- 77"
  71.    }
  72.  
  73.   This is my Gacs' 1 dimensional construction.
  74.  
  75.  @ARTICLE{g1dim86
  76.   ,AUTHOR = {G\'acs, Peter}
  77.   ,TITLE  = {Reliable computation with cellular automata}
  78.   ,JOURNAL = {Journal of Computer System Science}
  79.   ,VOLUME = 32
  80.   ,NUMBER = {1}
  81.   ,MONTH = {February}
  82.   ,PAGES = {15-78}
  83.   ,YEAR = 1986
  84.  }
  85.  
  86.  This is a 2-dimensional construction which may help understanding the
  87. difficult 1-dimensional paper and has a little more general
  88. discussion.
  89.  
  90.  @INCOLLECTION{g2dim89
  91.  ,AUTHOR = {G\'acs, Peter}
  92.  ,TITLE = {Self-correcting Two-dimensional Arrays}
  93.  ,BOOKTITLE= {Randomness in Computation}
  94.  ,SERIES = {Advances in Computing Research (a scientific annual)}
  95.  ,VOLUME = 5
  96.  ,EDITOR = {Silvio Micali}
  97.  ,PUBLISHER = {JAI Press}
  98.  ,ADDRESS = {Greenwich, Conn.}
  99.  ,YEAR = {1989}
  100.  ,PAGES = {223-326}
  101.  }
  102.