Non-deterministic cellular automata and languages

References

• Book , R.V. and Greibach , S.A. 1970 . Quasi-Realtime Languages . Mathematical Systems Theory , 4 : 97 – 111 .
   Google Scholar
• Bucher , W. and Čulik , K. II . 1984 . On Real Time and Linear Time Cellular Automata . RAIRO-Informatique Théorique , 18 : 307 – 325 .
   Web of Science ®Google Scholar
• Buchholz , T. , Klein , A. and Kutrib , M. 1998 . “ One Guess One-Way Cellular Arrays ” . In Mathematical Foundations of Computer Science (MFCS 1998) , (Vol. 1450) , 807 – 815 . Berlin : Springer . LNCS
   Google Scholar
• Buchholz , T. , Klein , A. and Kutrib , M. 2002 . On Interacting Automata with Limited Nondeterminism . Fundamenta Informaticae , 52 : 15 – 38 .
   Web of Science ®Google Scholar
• Buchholz , T. and Kutrib , M. 1997a . “ On the Power of One-Way Bounded Cellular Time Computers ” . In Developments in Language Theory (DLT 1997) , 365 – 375 . Greece : Aristotle University of Thessaloniki .
   Google Scholar
• Buchholz , T. and Kutrib , M. 1997b . Some Relations Between Massively Parallel Arrays . Parallel Computing , 23 : 1643 – 1662 .
   Web of Science ®Google Scholar
• Buchholz , T. and Kutrib , M. 1998 . On Time Computability of Functions in One-Way Cellular Automata . Acta Informatica , 35 : 329 – 352 .
   Web of Science ®Google Scholar
• Chang , J.H. , Ibarra , O.H. and Vergis , A. 1988 . On the Power of One-Way Communication . Journal of the ACM , 35 : 697 – 726 .
   Web of Science ®Google Scholar
• Choffrut , C. and Čulik , K. II . 1984 . On Real-Time Cellular Automata and Trellis Automata . Acta Informatica , 21 : 393 – 407 .
   Web of Science ®Google Scholar
• Cole , S.N. 1966 . “ Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines ” . In Symposium on Switching and Automata Theory (SWAT 1966) , 53 – 77 . Los Alamitos : IEEE .
   Google Scholar
• Cole , S.N. 1969 . Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines . IEEE Transactions on Computers , C-18 : 349 – 365 .
   Web of Science ®Google Scholar
• Čulik , K. II and Yu , S. 1984 . Iterative Tree Automata . Theoretical Computer Science , 32 : 227 – 247 .
   Web of Science ®Google Scholar
• Dyer , C.R. 1980 . One-Way Bounded Cellular Automata . Information and Control , 44 : 261 – 281 .
   Google Scholar
• Fischer , P.C. and Kintala , C.M.R. 1979 . Real-Time Computations with Restricted Nondeterminism . Mathematical Systems Theory , 12 : 219 – 231 .
   Google Scholar
• Ibarra , O.H. and Jiang , T. 1987 . On One-Way Cellular Arrays . SIAM Journal on Computing , 16 : 1135 – 1154 .
   Web of Science ®Google Scholar
• Ibarra , O.H. and Jiang , T. 1988 . Relating the Power of Cellular Arrays to their Closure Properties . Theoretical Computer Science , 57 : 225 – 238 .
   Web of Science ®Google Scholar
• Ibarra , O.H. and Kim , S.M. 1984 . Characterizations and Computational Complexity of Systolic Trellis Automata . Theoretical Computer Science , 29 : 123 – 153 .
   Web of Science ®Google Scholar
• Ibarra , O.H. , Kim , S.M. and Moran , S. 1985 . Sequential Machine Characterizations of Trellis and Cellular Automata and Applications . SIAM Journal on Computing , 14 : 426 – 447 .
   Web of Science ®Google Scholar
• Ibarra , O.H. and Palis , M.A. 1985 . Some Results Concerning Linear Iterative (Systolic) Arrays . Journal of Parallel and Distributed Computing , 2 : 182 – 218 .
   Web of Science ®Google Scholar
• Kintala, C.M.R. (1977), ‘Computations with a Restricted Number of Nondeterministic Steps,’ Thesis (PhD), Pennsylvania State University
   Google Scholar
• Krithivasan , K. and Mahajan , M. 1995 . Nondeterministic, Probabilistic and Alternating Computations on Cellular Array Models . Theoretical Computer Science , 143 : 23 – 49 .
   Web of Science ®Google Scholar
• Kutrib , M. 2009 . “ Cellular Automata and Language Theory ” . In Encyclopedia of Complexity and System Science , 800 – 823 . Berlin : Springer .
   Google Scholar
• Kutrib , M. and Löwe , J.T. 2003 . Space- and Time-Bounded Nondeterminism for Cellular Automata . Fundamenta Informaticae , 58 ( 2003 ) : 273 – 293 .
   Google Scholar
• Mahajan , M. and Krithivasan , K. 1992 . Some Results on Time-Varying and Relativised Cellular Automata . International Journal of Computer Mathematics , 43 : 21 – 38 .
   Web of Science ®Google Scholar
• Matamala , M. 1997 . Alternation on Cellular Automata . Theoretical Computer Science , 180 : 229 – 241 .
   Web of Science ®Google Scholar
• Mazoyer , J. and Terrier , V. 1999 . Signals in One-Dimensional Cellular Automata . Theoretical Computer Science , 217 : 53 – 80 .
   Web of Science ®Google Scholar
• Ozhigov , Y. 1999 . Computations on Nondeterministic Cellular Automata . Information and Computation , 148 : 181 – 201 .
   Web of Science ®Google Scholar
• Savitch , W.J. 1970 . Relationships Between Nondeterministic and Deterministic Tape Complexities . Journal of Computer and System Sciences , 4 : 177 – 192 .
   Google Scholar
• Seidel, S.R. (1979), ‘Language Recognition and the Synchronization of Cellular Automata,’ Technical report 79-02, Department of Computer Science, University of Iowa, Iowa City
   Google Scholar
• Smith III , A.R. 1970 . “ Cellular Automata and Formal Languages ” . In Symposium on Switching and Automata Theory (SWAT 1970) , 216 – 224 . Los Alamitos : IEEE .
   Google Scholar
• Smith , A.R. III . 1971 . Simple Computation-Universal Cellular Spaces . Journal of the ACM , 18 : 339 – 353 .
   Web of Science ®Google Scholar
• Smith , A.R. III . 1972 . Real-Time Language Recognition by One-Dimensional Cellular Automata . Journal of Computer and System Sciences , 6 : 233 – 253 .
   Google Scholar
• Terrier , V. 1995 . On Real Time One-Way Cellular Array . Theoretical Computer Science , 141 : 331 – 335 .
   Web of Science ®Google Scholar
• Umeo , H. , Morita , K. and Sugata , K. 1982 . Deterministic One-Way Simulation of Two-Way Real-Time Cellular Automata and Its Related Problems . Information Processing Letters , 14 : 158 – 161 .
   Web of Science ®Google Scholar
• Yamada , H. and Amoroso , S. 1969 . Tesselation Automata . Information and Control , 14 : 299 – 317 .
   Google Scholar