{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T03:42:53Z","timestamp":1742960573069,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319986531"},{"type":"electronic","value":"9783319986548"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-99813-8_31","type":"book-chapter","created":{"date-parts":[[2018,8,25]],"date-time":"2018-08-25T00:43:50Z","timestamp":1535157830000},"page":"340-351","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Self-verifying Cellular Automata"],"prefix":"10.1007","author":[{"given":"Martin","family":"Kutrib","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Worsch","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,26]]},"reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1051\/ita\/1984180403071","volume":"18","author":"W Bucher","year":"1984","unstructured":"Bucher, W., \u010culik II, K.: On real time and linear time cellular automata. RAIRO Inform. Th\u00e9or. 18, 307\u2013325 (1984)","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"31_CR2","first-page":"15","volume":"52","author":"T Buchholz","year":"2002","unstructured":"Buchholz, T., Klein, A., Kutrib, M.: On interacting automata with limited nondeterminism. Fundam. Inform. 52, 15\u201338 (2002)","journal-title":"Fundam. Inform."},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s002360050123","volume":"35","author":"T Buchholz","year":"1998","unstructured":"Buchholz, T., Kutrib, M.: On time computability of functions in one-way cellular automata. Acta Inform. 35, 329\u2013352 (1998)","journal-title":"Acta Inform."},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/BF00264617","volume":"21","author":"C Choffrut","year":"1984","unstructured":"Choffrut, C., \u010culik II, K.: On real-time cellular automata and trellis automata. Acta Inform. 21, 393\u2013407 (1984)","journal-title":"Acta Inform."},{"key":"31_CR5","unstructured":"Chomsky, N.: Context-free grammars and pushdown storage. Tech report, QPR 65, Massachusetts Institute of Technology (1962)"},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BFb0023453","volume-title":"STACS 1997","author":"P Duri\u0161","year":"1997","unstructured":"Duri\u0161, P., Hromkovi\u010d, J., Rolim, J.D.P., Schnitger, G.: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 117\u2013128. Springer, Heidelberg (1997). \n                      https:\/\/doi.org\/10.1007\/BFb0023453"},{"key":"31_CR7","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0019-9958(80)90164-3","volume":"44","author":"CR Dyer","year":"1980","unstructured":"Dyer, C.R.: One-way bounded cellular automata. Inf. Control 44, 261\u2013281 (1980)","journal-title":"Inf. Control"},{"key":"31_CR8","unstructured":"Fernau, H., Kutrib, M., Wendlandt, M.: Self-verifying pushdown automata. In: Freund, R., Mr\u00e1z, F., Pr\u016f\u0161a, D. (eds.) Non-Classical Models of Automata and Applications (NCMA 2017), vol. 329, pp. 103\u2013117. Austrian Computer Society, Vienna (2017). books@ocg.at"},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01776575","volume":"12","author":"PC Fischer","year":"1979","unstructured":"Fischer, P.C., Kintala, C.M.R.: Real-time computations with restricted nondeterminism. Math. Syst. Theory 12, 219\u2013231 (1979)","journal-title":"Math. Syst. Theory"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1145\/321386.321403","volume":"14","author":"S Ginsburg","year":"1967","unstructured":"Ginsburg, S., Greibach, S.A., Harrison, M.A.: One-way stack automata. J. ACM 14, 389\u2013418 (1967)","journal-title":"J. ACM"},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1006\/inco.2001.3040","volume":"169","author":"J Hromkovic","year":"2001","unstructured":"Hromkovic, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inf. Comput. 169, 284\u2013296 (2001)","journal-title":"Inf. Comput."},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1137\/S0097539702414622","volume":"33","author":"J Hromkovic","year":"2003","unstructured":"Hromkovic, J., Schnitger, G.: Nondeterministic communication with a limited number of advice bits. SIAM J. Comput. 33, 43\u201368 (2003)","journal-title":"SIAM J. Comput."},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1137\/0214033","volume":"14","author":"OH Ibarra","year":"1985","unstructured":"Ibarra, O.H., Kim, S.M., Moran, S.: Sequential machine characterizations of trellis and cellular automata and applications. SIAM J. Comput. 14, 426\u2013447 (1985)","journal-title":"SIAM J. Comput."},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1016\/j.ic.2010.11.017","volume":"209","author":"G Jir\u00e1skov\u00e1","year":"2011","unstructured":"Jir\u00e1skov\u00e1, G., Pighizzini, G.: Optimal simulation of self-verifying automata by deterministic automata. Inf. Comput. 209, 528\u2013535 (2011)","journal-title":"Inf. Comput."},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1007\/978-0-387-30440-3","volume-title":"Encyclopedia of Complexity and System Science","author":"M Kutrib","year":"2009","unstructured":"Kutrib, M.: Cellular automata and language theory. In: Meyers, R. (ed.) Encyclopedia of Complexity and System Science, pp. 800\u2013823. Springer, Heidelberg (2009). \n                      https:\/\/doi.org\/10.1007\/978-0-387-30440-3"},{"key":"31_CR16","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1080\/03081079.2012.695896","volume":"41","author":"M Kutrib","year":"2012","unstructured":"Kutrib, M.: Non-deterministic cellular automata and languages. Int. J. Gen. Syst. 41, 555\u2013568 (2012)","journal-title":"Int. J. Gen. Syst."},{"key":"31_CR17","unstructured":"Kutrib, M., Worsch, Th.: Self-verifying cellular automata. Technical report, 1803, Universit\u00e4t Gie\u00dfen (2018). \n                      http:\/\/www.informatik.uni-giessen.de\/reports\/Report1803.pdf"},{"key":"31_CR18","first-page":"549","volume":"7","author":"A Malcher","year":"2002","unstructured":"Malcher, A.: Descriptional complexity of cellular automata and decidability questions. J. Autom. Lang. Comb. 7, 549\u2013560 (2002)","journal-title":"J. Autom. Lang. Comb."},{"key":"31_CR19","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 III, A.R.: Real-time language recognition by one-dimensional cellular automata. J. Comput. Syst. Sci. 6, 233\u2013253 (1972)","journal-title":"J. Comput. Syst. Sci."},{"key":"31_CR20","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/0020-0190(82)90028-X","volume":"14","author":"H Umeo","year":"1982","unstructured":"Umeo, H., Morita, K., Sugata, K.: Deterministic one-way simulation of two-way real-time cellular automata and its related problems. Inf. Process. Lett. 14, 158\u2013161 (1982)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-99813-8_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,9,2]],"date-time":"2018-09-02T20:52:51Z","timestamp":1535921571000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-99813-8_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319986531","9783319986548"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-99813-8_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}