Skip to main content
SpringerLink
Log in

Cellular Automata and Language Theory

  • Reference work entry
Encyclopedia of Complexity and Systems Science

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 3,499.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 549.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Abbreviations

Cellular automaton:

A (one‐dimensional) cellular automaton is a linear array of cells which are connected to both of their nearest neighbors. The total number of cells in the array is determined by the input data. They are exactly in one of a finite number of states, which is changed according to local rules depending on the current state of a cell itself and the current states of its neighbors. The state changes take place simultaneously at discrete time steps. The input mode for cellular automata is called parallel. One can suppose that all cells fetch their input symbol during a pre-initial step.

Iterative array:

Basically, iterative arrays are cellular automata whose leftmost cell is distinguished. This so-called communication cell is connected to the input supply and fetches the input sequentially. The cells are initially empty, that is, in a special quiescent state.

Formal language:

The data on which the devices operate are strings built from input symbols of a finite set or alphabet. A subset of strings over a given alphabet is a formal language .

Signal:

Signals are used to transmit and encode information in cellular automata. If a cell changes to the state of its neighbor after some k time steps, and if subsequently its neighbors and their neighbors do the same, then the basic signal moves with speed \( \frac{1}{k} \) through the array. With the help of auxiliary signals, rather complex signals can be established.

Closure property :

Closure properties of families of formal languages indicate their robustness under certain operations. A family of formal languages is closed under some operation, if any application of the operation on languages from the family yields again a language from the family.

Turing machine:

A Turing machine is the simplest form of a universal computer. It captures the idea of an effective procedure or algorithm. At any time the machine is in any one of a finite number of states. It is equipped with an infinite tape divided into cells and a read-write head scanning a single cell. Each cell may contain a symbol from a finite set or alphabet. Initially, the finite input is written in successive cells. All other cells are empty. Dependent on a list of instructions, which serve as the program for the machine, the action is determined completely by the current state and the symbol currently scanned by the head. The action comprises the symbol to be written on the current cell, the new state of the machine, and the information of whether the head should move left or right.

Decidability :

A formal problem with two alternatives is decidable, if there is an algorithm or a Turing machine that solves it and halts on all inputs. That is, given an encoding of some instance of the problem, the algorithm or Turing machine returns the correct answer yes or no. The problem is semidecidable, if the algorithm halts on all instances for which the answer is yes.

Bibliography

Primary Literature

  1. Achilles AC, Kutrib M, Worsch T (1996) On relations between arrays of processing elements of different dimensionality. In: Parallel processing by cellular automata and arrays (PARCELLA 1996). Mathematical Research 96. Akademie Verlag, Berlin, pp 13–20

    Google Scholar 

  2. Albert J, Čulik II K (1987) A simple universal cellular automaton and its one-way and totalistic version. Complex Systems 1:1–16

    Google Scholar 

  3. Amoroso S, Patt YN (1972) Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures. J Comput System Sci 6:448–464

    MathSciNet  Google Scholar 

  4. Baker BS, Book RV (1974) Reversal‐bounded multipushdown machines. J Comput System Sci 8:315–332

    MathSciNet  Google Scholar 

  5. Bleck B, Kröger H (1992) Cellular algorithms. In: Advances in parallel computing, vol 2. JAI Press, London, pp 115–143

    Google Scholar 

  6. Bucher W, Čulik II K (1984) On real time and linear time cellular automata. RAIRO Inform Théor 18:307–325

    Google Scholar 

  7. Buchholz T, Klein A, Kutrib M (1998) On time reduction and simulation in cellular spaces. Int J Comput Math 71:459–474

    MathSciNet  Google Scholar 

  8. Buchholz T, Klein A, Kutrib M (1999) Iterative arrays with a wee bit alternation. In: Fundamentals of Computation Theory (FCT 1999). LNCS, vol 1684. Springer, Berlin, pp 173–184

    Google Scholar 

  9. Buchholz T, Klein A, Kutrib M (2000) Iterative arrays with small time bounds. In: Mathematical Foundations of Computer Science (MFCS 1998). LNCS, vol 1893. Springer, Berlin, pp 243–252

    Google Scholar 

  10. Buchholz T, Klein A, Kutrib M (2000) Real-time language recognition by alternating cellular automata. In: Theoretical Computer Science (TCS 2000). LNCS, vol 1872. Springer, Berlin, pp 213–225

    Google Scholar 

  11. Buchholz T, Klein A, Kutrib M (2002) On interacting automata with limited nondeterminism. Fund Inform 52:15–38

    MathSciNet  Google Scholar 

  12. Buchholz T, Klein A, Kutrib M (2003) Iterative arrays with limited nondeterministic communication cell. In: Words, Languages and Combinatorics III (WLC 2000), World Scientific Publishing, Singapore, pp 73–87

    Google Scholar 

  13. Buchholz T, Kutrib M (1997) Some relations between massively parallel arrays. Parallel Comput 23(11):1643–1662

    MathSciNet  Google Scholar 

  14. Buchholz T, Kutrib M (1998) On time computability of functions in one-way cellular automata. Acta Inf 35:329–352

    MathSciNet  Google Scholar 

  15. Chang JH, Ibarra OH, Palis MA (1987) Parallel parsing on a one-way array of finite-state machines. IEEE Trans Comp C-36:64–75

    Google Scholar 

  16. Chang JH, Ibarra OH, Vergis A (1988) On the power of one-way communication. J ACM 35:697–726

    MathSciNet  Google Scholar 

  17. Choffrut C, Čulik II K (1984) On real-time cellular automata and trellis automata. Acta Inf 21:393–407

    Google Scholar 

  18. Cole SN (1966) Real-time computation by n-dimensional iterative arrays of finite-state machines. In: IEEE Symposium on Switching and Automata Theory (SWAT 1966). IEEE Press, New York, pp 53–77

    Google Scholar 

  19. Cole SN (1969) Real-time computation by n‑dimensional iterative arrays of finite-state machines. IEEE Trans Comp C‑18(4):349–365

    Google Scholar 

  20. Čulik II K, Fris I (1985) Topological transformations as a tool in the design of systolic networks. Theoret Comp Sci 37:183–216

    Google Scholar 

  21. Čulik II K, Gruska J, Salomaa A (1984) Systolic trellis automata I. Int J Comp Math 15:195–212

    Google Scholar 

  22. Čulik II K, Gruska J, Salomaa A (1986) Systolic trellis automata: Stability, decidability and complexity. Inf Control 71:218–230

    Google Scholar 

  23. Czeizler E, Kari J (2005) A tight linear bound on the neighborhood of inverse cellular automata. In: Automata, Languages and Programming (ICALP 2005). LNCS, vol 3580. Springer, Berlin, pp 410–420

    Google Scholar 

  24. Delorme M, Mazoyer J (2004) Real-time recognition of languages on an two‐dimensional archimedean thread. Theor Comp Sci 322:335–354

    MathSciNet  Google Scholar 

  25. Dubacq JC, Terrier V (2002) Signals for cellular automata in dimension 2 or higher. In: Theoretical Informatics (LATIN 2002). LNCS, vol 2286. Springer, Berlin, pp 451–464

    Google Scholar 

  26. Dyer CR (1980) One-way bounded cellular automata. Inf Control 44:261–281

    MathSciNet  Google Scholar 

  27. Fischer PC (1965) Generation of primes by a one‐dimensional real-time iterative array. J ACM 12:388–394

    Google Scholar 

  28. Fischer PC, Kintala CMR (1979) Real-time computations with restricted nondeterminism. Math. Syst Theory 12:219–231

    Google Scholar 

  29. Ginsburg S, Greibach SA, Harrison MA (1967) One-way stack automata. J ACM 14:389–418

    MathSciNet  Google Scholar 

  30. Hartmanis J (1967) Context-free languages and Turing machine computations. Proc Symp App Math 19:42–51

    MathSciNet  Google Scholar 

  31. Höllerer WO, Vollmar R (1975) On forgetful cellular automata. J Comp Syst Sci 11:237–251

    Google Scholar 

  32. Ibarra OH, Jiang T (1987) On one-way cellular arrays. SIAM J Comp 16:1135–1154

    MathSciNet  Google Scholar 

  33. Ibarra OH, Jiang T (1988) Relating the power of cellular arrays to their closure properties. Theor Comp Sci 57:225–238

    MathSciNet  Google Scholar 

  34. Ibarra OH, Kim SM, Moran S (1985) Sequential machine characterizations of trellis and cellular automata and applications. SIAM J Comp 14:426–447

    MathSciNet  Google Scholar 

  35. Ibarra OH, Kim SM (1984) Characterizations and computational complexity of systolic trellis automata. Theor Comp Sci 29:123–153

    MathSciNet  Google Scholar 

  36. Ibarra OH, Palis MA (1985) Some results concerning linear iterative (systolic) arrays. J Paral Distrib Comp 2:182–218

    Google Scholar 

  37. Ibarra OH, Palis MA (1988) Two‐dimensional iterative arrays: Characterizations and applications. Theor Comp Sci 57:47–86

    MathSciNet  Google Scholar 

  38. Ibarra OH, Palis MA, Kim SM (1985) Fast parallel language recognition by cellular automata. Theor Comp Sci 41(2–3):231–246

    MathSciNet  Google Scholar 

  39. Imai K, Morita K (1996) Firing squad synchronization problem in reversible cellular automata. Theor Comp Sci 165(2):475–482

    MathSciNet  Google Scholar 

  40. Iwamoto C, Hatsuyama T, Morita K, Imai K (2002) Constructible functions in cellular automata and their applications to hierarchy results. Theor Comp Sci 270:797–809

    MathSciNet  Google Scholar 

  41. Kari J (1994) Reversibility and surjectivity problems of cellular automata. J Comp Syst Sci 48(1):149–182

    MathSciNet  Google Scholar 

  42. Kasami T, Fuji M (1968) Some results on capabilities of one‐dimensional iterative logical networks. Elect Commun Japan 51‑C:167–176

    Google Scholar 

  43. Kim S, McCloskey R (1990) A characterization of constant-time cellular automata computation. Phys D 45:404–419

    MathSciNet  Google Scholar 

  44. Kintala CMR (1977) Computations with a Restricted Number of Nondeterministic Steps. Ph D thesis, Pennsylvania State University, University Park

    Google Scholar 

  45. Klein A, Kutrib M (2003) Fast one-way cellular automata. Theor Comp Sci 1–3:233–250

    MathSciNet  Google Scholar 

  46. Klein A, Kutrib M (2007) Cellular devices and unary languages. Fund Inf 78:343–368

    MathSciNet  Google Scholar 

  47. Kosaraju SR (1975) Speed of recognition of context-free languages by array automata. SIAM J Comp 4:331–340

    MathSciNet  Google Scholar 

  48. Krithivasan K, Mahajan M (1995) Nondeterministic, probabilistic and alternating computations on cellular array models. Theor Comp Sci 143:23–49

    MathSciNet  Google Scholar 

  49. Kutrib M (1999) Pushdown cellular automata. Theor Comp Sci 215(1–2):239–261

    MathSciNet  Google Scholar 

  50. Kutrib M (2001) Efficient universal pushdown cellular automata and their application to complexity. In: Machines, Computations, and Universality (MCU 2001). LNCS, vol 2055. Springer, Berlin, pp 252–263

    Google Scholar 

  51. Kutrib M, Löwe JT (2002) Massively parallel fault tolerant computations on syntactical patterns. Fut Gener Comp Syst 18:905–919

    Google Scholar 

  52. Kutrib M, Löwe JT (2003) Space- and time-bounded nondeterminism for cellular automata. Fund Inf 58(2003):273–293

    Google Scholar 

  53. Kutrib M, Malcher A (2006) Fast cellular automata with restricted inter-cell communication: Computational capacity. In: Theoretical Computer Science (IFIP TCS2006). IFIP 209. Springer, Berlin, pp 151–164

    Google Scholar 

  54. Kutrib M, Malcher A (2006) Fast iterative arrays with restricted inter-cell communication: Constructions and decidability. In: Mathematical Foundations of Computer Science (MFCS 2006). LNCS, vol 4162. Springer, Berlin, pp 634–645

    Google Scholar 

  55. Kutrib M, Malcher A (2008) Fast reversible language recognition using cellular automata. Inform Comput 206(9–10):1142–1151

    Google Scholar 

  56. Kutrib M, Malcher A (2007) Real-time reversible iterative arrays. In: Fundamentals of Computation Theory 2007 (FCT 2007). LNCS, vol 4693. Springer, Berlin, pp 376–387

    Google Scholar 

  57. Kutrib M, Worsch T (1994) Investigation of different input modes for cellular automata. In: Parallel Processing by Cellular Automata and Arrays (PARCELLA 1994). Mathematical Research 81, Akademie Verlag, Berlin, pp 141–150

    Google Scholar 

  58. Malcher A (2002) Descriptional complexity of cellular automata and decidability questions. J Autom Lang Comb 7:549–560

    MathSciNet  Google Scholar 

  59. Malcher A (2004) On the descriptional complexity of iterative arrays. IEICE Trans Inf Syst E87-D(3):721–725

    MathSciNet  Google Scholar 

  60. Martin B (1994) A universal cellular automaton in quasi-linear time and its S-m-n form. Theor Comp Sci 123(2):199–237

    Google Scholar 

  61. Matamala M (1997) Alternation on cellular automata. Theor Comp Sci 180:229–241

    MathSciNet  Google Scholar 

  62. Mazoyer J (1987) A six-state minimal time solution to the firing squad synchronization problem. Theor Comp Sci 50:183–238

    MathSciNet  Google Scholar 

  63. Mazoyer J, Terrier V (1999) Signals in one‐dimensional cellular automata. Theor Comp Sci 217:53–80

    MathSciNet  Google Scholar 

  64. Morita K (1992) Computation‐universality of one‐dimensional one-way reversible cellular automata. Inf Proc Lett 42:325–329

    Google Scholar 

  65. Morita K (1995) Reversible simulation of one‐dimensional irreversible cellular automata. Theor Comp Sci 148:157–163

    Google Scholar 

  66. Morita K, Harao M (1989) Computation universality of one dimensional reversible injective cellular automata. Trans IEICE E72 pp 758–762

    Google Scholar 

  67. Morita K, Ueno S (1994) Parallel generation and parsing of array languages using reversible cellular automata. Int J Pattern Recog Artif Int 8:543–561

    Google Scholar 

  68. Nakamura K (1999) Real-time language recognition by one-way and two-way cellular automata. In: Mathematical Foundations of Computer Science (MFCS 1999). LNCS, vol 1672. Springer, Berlin, pp 220–230

    Google Scholar 

  69. Rice HG (1953) Classes of recursively enumerable sets and their decision problems. Trans Amer Math Soc 89:25–59

    MathSciNet  Google Scholar 

  70. Rosenfeld A (1979) Picture Languages. Academic Press, New York

    Google Scholar 

  71. Rosenstiehl P, Fiksel JR, Holliger A (1972) Intelligent graphs: Networks of finite automata capable of solving graph problems. In: Graph Theory and Computing. Academic Press, New York, pp 219–265

    Google Scholar 

  72. Salomaa A (1973) Formal Languages. Academic Press, Orlando

    Google Scholar 

  73. Seidel SR (1979) Language recognition and the synchronization of cellular automata. Technical Report 79–02, Department of Computer Science, University of Iowa, Iowa City

    Google Scholar 

  74. Seiferas JI (1977) Iterative arrays with direct central control. Acta Inf 8:177–192

    MathSciNet  Google Scholar 

  75. Seiferas JI (1977) Linear-time computation by nondeterministic multidimensional iterative arrays. SIAM J Comp 6:487–504

    MathSciNet  Google Scholar 

  76. Smith III AR (1970) Cellular automata and formal languages. In: IEEE Symposium on Switching and Automata Theory (SWAT 1970). IEEE Press, New York, pp 216–224

    Google Scholar 

  77. Smith III AR (1971) Cellular automata complexity trade-offs. Inf Control 18:466–482

    Google Scholar 

  78. Smith III AR (1971) Simple computation–universal cellular spaces. J ACM 18:339–353

    Google Scholar 

  79. Smith III AR (1971) Two‐dimensional formal languages and pattern recognition by cellular automata. In: IEEE Symposium on Switching and Automata Theory (SWAT 1971). IEEE Press, New York, pp 144–152

    Google Scholar 

  80. Smith III AR (1972) Real-time language recognition by one‐dimensional cellular automata. J Comp Syst Sci 6:233–253

    Google Scholar 

  81. Smith III AR (1976) Introduction to and survey of polyautomata theory. In: Automata, Languages, Development. North-Holland, Amsterdam, pp 405–422

    Google Scholar 

  82. Sommerhalder R, van Westrhenen SC (1983) Parallel language recognition in constant time by cellular automata. Acta Inf 19:397–407

    Google Scholar 

  83. Terrier V (1994) Language recognizable in real time by cellular automata. Complex Syst 8:325–336

    MathSciNet  Google Scholar 

  84. Terrier V (1995) On real time one-way cellular array. Theor Comp Sci 141:331–335

    MathSciNet  Google Scholar 

  85. Terrier V (1996) Language not recognizable in real time by one-way cellular automata. Theor Comp Sci 156:281–287

    MathSciNet  Google Scholar 

  86. Terrier V (1999) Two‐dimensional cellular automata recognizer. Theor Comp Sci 218:325–346

    MathSciNet  Google Scholar 

  87. Terrier V (2003) Two‐dimensional cellular automata and deterministic on-line tesselation automata. Theor Comp Sci 301:167–187

    MathSciNet  Google Scholar 

  88. Terrier V (2004) Two‐dimensional cellular automata and their neighborhoods. Theor Comp Sci 312:203–222

    MathSciNet  Google Scholar 

  89. Terrier V (2006) Closure properties of cellular automata. Theor Comp Sci 352:97–107

    MathSciNet  Google Scholar 

  90. Terrier V (2006) Low complexity classes of multidimensional cellular automata. Theor Comp Sci 369:142–156

    MathSciNet  Google Scholar 

  91. Toffoli T (1977) Computation and construction universality of reversible cellular automata. J Comp Syst Sci 15:213–231

    MathSciNet  Google Scholar 

  92. Umeo H (2001) Linear-time recognition of connectivity of binary images on 1-bit inter-cell communication cellular automaton. Parallel Comp 27:587–599

    MathSciNet  Google Scholar 

  93. Umeo H, Kamikawa N (2002) A design of real-time non-regular sequence generation algorithms and their implementations on cellular automata with 1-bit inter-cell communications. Fund Inf 52:257–275

    MathSciNet  Google Scholar 

  94. Umeo H, Kamikawa N (2003) Real-time generation of primes by a 1-bit‐communication cellular automaton. Fund Inf 58:421–435

    MathSciNet  Google Scholar 

  95. Umeo H, Morita K, Sugata K (1982) Deterministic one-way simulation of two-way real-time cellular automata and its related problems. Inf Proc Lett 14:158–161

    MathSciNet  Google Scholar 

  96. Vollmar R (1981) On cellular automata with a finite number of state changes. Computing 3:181–191

    Google Scholar 

  97. von Neumann J (1966) Theory of Self‐Reproducing Automata. In: Burks AW (ed) University of Illinois Press, Champaign

    Google Scholar 

  98. Waksman A (1966) An optimum solution to the firing squad synchronization problem. Inf Control 9:66–78

    MathSciNet  Google Scholar 

  99. Worsch T (2000) Linear time language recognition on cellular automata with restricted communication. In: Theoretical Informatics (LATIN 2000). LNCS, vol 1776. Springer, Berlin, pp 417–426

    Google Scholar 

Books and Reviews

  1. Delorme M, Mazoyer J (eds) (1999) Cellular Automata – A Parallel Model. Kluwer, Dordrecht

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Universität Giessen, Giessen, Germany

    Martin Kutrib

Authors
  1. Martin Kutrib
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. RAMTECH LIMITED, 122 Escalle Lane, Larkspur, CA, 94939, USA

    Robert A. Meyers Ph. D. (Editor-in-Chief) (Editor-in-Chief)

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag

About this entry

Cite this entry

Kutrib, M. (2009). Cellular Automata and Language Theory. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY. https://doi.org/10.1007/978-0-387-30440-3_54

Download citation

Publish with us

Policies and ethics

Search

Navigation