{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T11:00:05Z","timestamp":1780743605500,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":51,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540929093","type":"print"},{"value":"9783540929109","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-540-92910-9_4","type":"book-chapter","created":{"date-parts":[[2012,8,25]],"date-time":"2012-08-25T14:54:06Z","timestamp":1345906446000},"page":"123-158","source":"Crossref","is-referenced-by-count":8,"title":["Language Recognition by Cellular Automata"],"prefix":"10.1007","author":[{"given":"V\u00e9ronique","family":"Terrier","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR00041","unstructured":"Beyer WT (1969) Recognition of topological invariants by iterative arrays. Technical Report AITR-229, MIT Artificial Intelligence Laboratory, October 1, 1969"},{"key":"4_CR00042","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1051\/ita\/1984180403071","volume":"81","author":"W Bucher","year":"1984","unstructured":"Bucher W, \u010culik K II (1984) On real time and linear time cellular automata. RAIRO Theor Inf Appl 81:307\u2013325","journal-title":"RAIRO Theor Inf Appl"},{"issue":"4","key":"4_CR00044","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s002360050123","volume":"35","author":"T Buchholz","year":"1998","unstructured":"Buchholz T, Kutrib M (1998) On time computability of functions in one-way cellular automata. Acta Inf 35(4):329\u2013352","journal-title":"Acta Inf"},{"key":"4_CR00043","first-page":"243","volume-title":"MFCS, Lecture notes in computer science","author":"T Buchholz","year":"2000","unstructured":"Buchholz T, Klein A, Kutrib M (2000) Iterative arrays with small time bounds. In: Nielsen M, Rovan B (eds) MFCS, Lecture notes in computer science, vol 1893. Springer, Berlin, Heidelberg, pp 243\u2013252"},{"key":"4_CR00045","doi-asserted-by":"crossref","unstructured":"Cervelle J, Formenti E (2009) Algorithmic complexity and cellular automata. In: Meyers RA (ed) Encyclopedia of complexity and system science. Springer, New York","DOI":"10.1007\/978-0-387-30440-3_17"},{"issue":"1","key":"4_CR00046","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1109\/TC.1987.5009449","volume":"C-36","author":"JH Chang","year":"1987","unstructured":"Chang JH, Ibarra OH, Palis MA (1987) Parallel parsing on a one-way array of finite state machines. IEEE Trans Comput C-36(1):64\u201375","journal-title":"IEEE Trans Comput"},{"issue":"3","key":"4_CR00048","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1145\/44483.44493","volume":"35","author":"JH Chang","year":"1988","unstructured":"Chang JH, Ibarra OH, Vergis A (1988) On the power of one-way communication. J ACM 35(3):697\u2013726","journal-title":"J ACM"},{"issue":"1","key":"4_CR00047","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0304-3975(89)90116-3","volume":"68","author":"JH Chang","year":"1989","unstructured":"Chang JH, Ibarra OH, Palis MA (1989) Efficient simulations of simple models of parallel computation by time-bounded ATMs and space-bounded TMs. Theor Comput Sci 68(1):19\u201336","journal-title":"Theore Comput Sci"},{"issue":"4","key":"4_CR00049","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/BF00264617","volume":"21","author":"C Choffrut","year":"1984","unstructured":"Choffrut C, Culik K II (1984) On real-time cellular automata and trellis automata. Acta Inf 21(4):393\u2013407","journal-title":"Acta Inf"},{"key":"4_CR000410","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1109\/T-C.1969.222663","volume":"18","author":"SN Cole","year":"1969","unstructured":"Cole SN (1969) Real-time computation by n-dimensional iterative arrays of finite-state machine. IEEE Trans Comput 18:349\u2013365","journal-title":"IEEE Trans Comput"},{"issue":"3","key":"4_CR000411","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(89)90134-8","volume":"30","author":"K Culik II","year":"1989","unstructured":"Culik K II (1989) Variations of the firing squad problem and applications. Inf Process Lett 30(3):153\u2013157","journal-title":"Inf Process Lett"},{"issue":"3\u20134","key":"4_CR000413","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1080\/00207168408803410","volume":"15","author":"K Culik II","year":"1984","unstructured":"Culik K II, Gruska J, Salomaa A (1984) Systolic trellis automata. I. Int J Comput Math 15(3\u20134):195\u2013212","journal-title":"Int J Comput Math"},{"key":"4_CR000414","doi-asserted-by":"crossref","unstructured":"Delacourt M, Poupet V (2007) Real time language recognition on 2D cellular automata: Dealing with non-convex neighborhoods. In: Kucera L, Kucera A (eds) Mathematical foundations of computer science 2007, vol 4708 of Lecture Notes in Computer Science, pp 298\u2013309","DOI":"10.1007\/978-3-540-74456-6_28"},{"key":"4_CR000415","unstructured":"Delorme M, Mazoyer J (1994) Reconnaisance de langages sur automates cellulaires. Research Report 94\u201346, LIP, ENS Lyon, France"},{"issue":"1\u20132","key":"4_CR000416","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0304-3975(02)00016-6","volume":"281","author":"M Delorme","year":"2002","unstructured":"Delorme M, Mazoyer J (2002) Reconnaissance parall\u00e8le des langages rationnels sur automates cellulaires plans. [Parallel recognition of rational languages on plane cellular automata] Selected papers in honour of Maurice Nivat. Theor Comput Sci 281(1\u20132):251\u2013289","journal-title":"Theor Comput Sci"},{"issue":"2","key":"4_CR000417","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.tcs.2004.03.016","volume":"322","author":"M Delorme","year":"2004","unstructured":"Delorme M, Mazoyer J (2004) Real-time recognition of languages on an two-dimensional Archimedean thread. Theor Comput Sci 322(2):335\u2013354","journal-title":"Theor Comput Sci"},{"issue":"3","key":"4_CR000418","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0019-9958(80)90164-3","volume":"44","author":"CR Dyer","year":"1980","unstructured":"Dyer CR (1980) One-way bounded cellular automata. Inf Control 44(3):261\u2013281","journal-title":"Inf Control"},{"key":"4_CR000419","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1145\/321281.321290","volume":"12","author":"PC Fischer","year":"1965","unstructured":"Fischer PC (1965) Generation of primes by one-dimensional real-time iterative array. J ACM 12:388\u2013394","journal-title":"J ACM"},{"key":"4_CR000420","doi-asserted-by":"crossref","unstructured":"Giammarresi D, Restivo A (1997) Two-dimensional languages. In: Rozenberg G, Salomaa A (eds) Handbook of Formal Languages, vol 3. Springer, New York, pp 215\u2013267","DOI":"10.1007\/978-3-642-59126-6_4"},{"issue":"4","key":"4_CR000421","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"LM Goldschlager","year":"1982","unstructured":"Goldschlager LM (1982) A universal interconnection pattern for parallel computers. J ACM 29(4):1073\u20131086","journal-title":"J ACM"},{"key":"4_CR000422","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J Hartmanis","year":"1965","unstructured":"Hartmanis J, Stearns RE (1965) On the computational complexity of algorithms. Trans Am Math Soc (AMS) 117:285\u2013306","journal-title":"Trans Am Math Soc (AMS)"},{"issue":"6","key":"4_CR000423","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1137\/0216072","volume":"16","author":"OH Ibarra","year":"1987","unstructured":"Ibarra OH, Jiang T (1987) On one-way cellular arrays. SIAM J Comput 16(6):1135\u20131154","journal-title":"SIAM J Comput"},{"issue":"2\u20133","key":"4_CR000426","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(88)90040-0","volume":"57","author":"OH Ibarra","year":"1988","unstructured":"Ibarra OH, Jiang T (1988) Relating the power of cellular arrays to their closure properties. Theor Comput Sci 57(2\u20133):225\u2013238","journal-title":"Theor Comput Sci"},{"issue":"1\u20132","key":"4_CR000427","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0304-3975(84)90015-X","volume":"29","author":"OH Ibarra","year":"1984","unstructured":"Ibarra OH, Kim SM (1984) Characterizations and computational complexity of systolic trellis automata. Theor Comput Sci 29(1\u20132):123\u2013153","journal-title":"Theor Comput Sci"},{"issue":"2","key":"4_CR000425","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1137\/0216027","volume":"16","author":"OH Ibarra","year":"1987","unstructured":"Ibarra OH, Palis MA (1987) On efficient simulations of systolic arrays of random-access machines. SIAM J Comput 16(2):367\u2013377","journal-title":"SIAM J Comput"},{"issue":"1","key":"4_CR000429","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0304-3975(88)90163-6","volume":"57","author":"OH Ibarra","year":"1988","unstructured":"Ibarra OH, Palis MA (1988) Two-dimensional iterative arrays: characterizations and applications. Theor Comput Sci 57(1):47\u201386","journal-title":"Theor Comput Sci"},{"issue":"2","key":"4_CR000428","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1137\/0214033","volume":"14","author":"OH Ibarra","year":"1985","unstructured":"Ibarra OH, Kim SM, Moran S (1985a) Sequential machine characterizations of trellis and cellular automata and applications. SIAM J Comput 14(2):426\u2013447","journal-title":"SIAM J Comput"},{"issue":"2","key":"4_CR000424","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0743-7315(85)90034-6","volume":"2","author":"OH Ibarra","year":"1985","unstructured":"Ibarra OH, Palis MA, Kim SM (1985b) Some results concerning linear iterative (systolic) arrays. J Parallel Distrib Comput 2(2):182\u2013218","journal-title":"J Parallel Distrib Comput"},{"issue":"3","key":"4_CR000430","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0304-3975(89)90154-0","volume":"66","author":"A Ito","year":"1989","unstructured":"Ito A, Inoue K, Takanami I (1989) Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\u2218 rotation. Theor Comput Sci 66(3):273\u2013287","journal-title":"Theor Comput Sci"},{"issue":"6","key":"4_CR000431","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/0020-0190(87)90221-3","volume":"25","author":"Y Kobuchi","year":"1987","unstructured":"Kobuchi Y (1987) A note on symmetrical cellular spaces. Inf Process Lett 25(6):413\u2013415","journal-title":"Inf Process Lett"},{"key":"4_CR000432","doi-asserted-by":"crossref","unstructured":"Kosaraju SR (1979) Fast parallel processing array algorithms for some graph problems (preliminary version). In ACM conference record of the eleventh annual ACM symposium on theory of computing: papers presented at the symposium, Atlanta, Georgia, ACM Press, New York, 30 April\u20132 May 1979, pp 231\u2013236","DOI":"10.1145\/800135.804417"},{"issue":"1\u20133","key":"4_CR000433","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0304-3975(02)00406-1","volume":"295","author":"A Klein","year":"2003","unstructured":"Klein A, Kutrib M (2003) Fast one-way cellular automata. Theor Comput Sci 295(1\u20133):233\u2013250","journal-title":"Theor Comput Sci"},{"key":"4_CR000434","doi-asserted-by":"crossref","unstructured":"Kutrib M (2001) Automata arrays and context-free languages. In Where mathematics, computer science, linguistics and biology meet, Kluwer, Dordrecht, The Netherlands, pp 139\u2013148","DOI":"10.1007\/978-94-015-9634-3_12"},{"issue":"1","key":"4_CR000435","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/361237.361240","volume":"15","author":"S Levialdi","year":"1972","unstructured":"Levialdi S (1972) On shrinking binary picture patterns. Commun ACM 15(1):7\u201310","journal-title":"Commun ACM"},{"issue":"1","key":"4_CR000436","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0304-3975(92)90150-E","volume":"101","author":"J Mazoyer","year":"1992","unstructured":"Mazoyer J, Reimen N (1992) A linear speed-up theorem for cellular automata. Theor Comput Sci 101(1):59\u201398","journal-title":"Theor Comput Sci"},{"key":"4_CR000437","doi-asserted-by":"crossref","unstructured":"Okhotin A (2002) Automaton representation of linear conjunctive languages. In International conference on developments in language theory (DLT), LNCS, vol 6. Kyoto, Japan","DOI":"10.1007\/3-540-45005-X_35"},{"key":"4_CR000438","doi-asserted-by":"crossref","unstructured":"Poupet V (2005) Cellular automata: real-time equivalence between one-dimensional neighborhoods. In Diekert V, Durand B (eds) STACS 2005, 22nd annual symposium on theoretical aspects of computer science, Stuttgart, Germany, February 24\u201326, 2005, Proceedings, vol 3404 of Lecture Notes in Computer Science. Springer, pp 133\u2013144","DOI":"10.1007\/978-3-540-31856-9_11"},{"key":"4_CR000439","doi-asserted-by":"crossref","unstructured":"Poupet V (2007) A padding technique on cellular automata to transfer inclusions of complexity classes. In Diekert V, Volkov MV, Voronkov A (eds) Second international symposium on computer science in Russia, vol 4649 of Lecture Notes in Computer Science. Springer, pp 337\u2013348","DOI":"10.1007\/978-3-540-74510-5_34"},{"issue":"4","key":"4_CR000440","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1145\/321420.321423","volume":"14","author":"AL Rosenberg","year":"1967","unstructured":"Rosenberg AL (1967) Real-time definable languages. J ACM 14(4):645\u2013662","journal-title":"J ACM"},{"issue":"5","key":"4_CR000441","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0020-0190(88)90083-X","volume":"27","author":"C Savage","year":"1988","unstructured":"Savage C (1988) Recognizing majority on a one-way mesh. Inf Process Lett 27(5):221\u2013225","journal-title":"Inf Process Lett"},{"issue":"3","key":"4_CR000443","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1145\/321650.321652","volume":"18","author":"AR Smith III","year":"1971","unstructured":"Smith AR III (1971) Simple computation-universal cellular spaces. J ACM 18(3):339\u2013353","journal-title":"J ACM"},{"key":"4_CR000442","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0022-0000(72)80004-7","volume":"6","author":"AR Smith III","year":"1972","unstructured":"Smith AR III (1972) Real-time language recognition by one-dimensional cellular automata. J Comput Syst Sci 6:233\u2013253","journal-title":"J Comput Syst Sci"},{"issue":"1\u20133","key":"4_CR000444","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/S0019-9958(85)80033-4","volume":"67","author":"H Szwerinski","year":"1985","unstructured":"Szwerinski H (1985) Symmetrical one-dimensional cellular spaces. Inf Control 67(1\u20133):163\u2013172","journal-title":"Inf Control"},{"issue":"1\u20132","key":"4_CR000445","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/0304-3975(94)00212-2","volume":"141","author":"V Terrier","year":"1995","unstructured":"Terrier V (1995) On real time one-way cellular array. Theor Comput Sci 141(1\u20132):331\u2013335","journal-title":"Theor Comput Sci"},{"issue":"1\u20132","key":"4_CR000446","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0304-3975(95)00111-5","volume":"156","author":"V Terrier","year":"1996","unstructured":"Terrier V (1996) Language not recognizable in real time by one-way cellular automata. Theor Comput Sci 156(1\u20132):281\u2013285","journal-title":"Theor Comput Sci"},{"issue":"2","key":"4_CR000447","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0304-3975(98)00329-6","volume":"218","author":"V Terrier","year":"1999","unstructured":"Terrier V (1999) Two-dimensional cellular automata recognizer. Theor Comput Sci 218(2):325\u2013346","journal-title":"Theor Comput Sci"},{"issue":"3","key":"4_CR000448","doi-asserted-by":"publisher","first-page":"2075","DOI":"10.1016\/S0304-3975(02)00489-9","volume":"290","author":"V Terrier","year":"2003","unstructured":"Terrier V (2003a) Characterization of real time iterative array by alternating device. Theor Comput Sci 290(3):2075\u20132084","journal-title":"Theor Comput Sci"},{"issue":"1\u20133","key":"4_CR000449","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0304-3975(02)00575-3","volume":"301","author":"V Terrier","year":"2003","unstructured":"Terrier V (2003b) Two-dimensional cellular automata and deterministic on-line tessalation automata. Theor Comput Sci 301(1\u20133):167\u2013186","journal-title":"Theor Comput Sci"},{"issue":"2\u20133","key":"4_CR000450","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.tcs.2003.08.011","volume":"312","author":"V Terrier","year":"2004","unstructured":"Terrier V (2004) Two-dimensional cellular automata and their neighborhoods. Theor Comput Sci 312(2\u20133): 203\u2013222","journal-title":"Theor Comput Sci"},{"issue":"1\u20133","key":"4_CR000451","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.tcs.2005.10.039","volume":"352","author":"V Terrier","year":"2006","unstructured":"Terrier V (2006a) Closure properties of cellular automata. Theor Comput Sci 352(1\u20133):97\u2013107","journal-title":"Theor Comput Sci"},{"issue":"1\u20133","key":"4_CR000452","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.tcs.2006.07.061","volume":"369","author":"V Terrier","year":"2006","unstructured":"Terrier V (2006b) Low complexity classes of multidimensional cellular automata. Theor Comput Sci 369(1\u20133):142\u2013156","journal-title":"Theor Comput Sci"}],"container-title":["Handbook of Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92910-9_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T12:17:06Z","timestamp":1619525826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92910-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783540929093","9783540929109"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92910-9_4","relation":{},"subject":[],"published":{"date-parts":[[2012]]}}}