{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T08:05:37Z","timestamp":1792051537052,"version":"4.4.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359043","type":"print"},{"value":"9783540359050","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_13","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T10:46:45Z","timestamp":1151491605000},"page":"132-143","source":"Crossref","is-referenced-by-count":73,"title":["P-completeness of Cellular Automaton Rule 110"],"prefix":"10.1007","author":[{"given":"Turlough","family":"Neary","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Damien","family":"Woods","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1103\/RevModPhys.55.601","volume":"55","author":"S. Wolfram","year":"1983","unstructured":"Wolfram, S.: Statistical mechanics of cellular automata. Reviews of Modern Physics\u00a055, 601\u2013644 (1983)","journal-title":"Reviews of Modern Physics"},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.25088\/ComplexSystems.15.1.1","volume":"15","author":"M. Cook","year":"2004","unstructured":"Cook, M.: Universality in elementary cellular automata. Complex Systems\u00a015, 1\u201340 (2004)","journal-title":"Complex Systems"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/321203.321206","volume":"11","author":"J. Cocke","year":"1964","unstructured":"Cocke, J., Minsky, M.: Universality of tag systems with P = 2. Journal of the ACM\u00a011, 15\u201320 (1964)","journal-title":"Journal of the ACM"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0304-3975(96)00077-1","volume":"168","author":"Y. Rogozhin","year":"1996","unstructured":"Rogozhin, Y.: Small universal Turing machines. TCS\u00a0168, 215\u2013240 (1996)","journal-title":"TCS"},{"key":"13_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45132-3_1","volume-title":"Machines, Computations, and Universality","author":"C. Baiocchi","year":"2001","unstructured":"Baiocchi, C.: Three small universal Turing machines. In: Margenstern, M., Rogozhin, Y. (eds.) MCU 2001. LNCS, vol.\u00a02055, pp. 1\u201310. Springer, Heidelberg (2001)"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/3-540-46011-X_27","volume-title":"Developments in Language Theory","author":"M. Kudlek","year":"2002","unstructured":"Kudlek, M., Rogozhin, Y.: A universal Turing machine with 3 states and 9 symbols. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol.\u00a02295, pp. 311\u2013318. Springer, Heidelberg (2002)"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Minsky, M.: Size and structure of universal Turing machines using tag systems. In: Recursive Function Theory, Symp. in Pure Math., vol.\u00a05, pp. 229\u2013238. AMS (1962)","DOI":"10.1090\/pspum\/005\/0142452"},{"key":"13_CR8","unstructured":"Neary, T., Woods, D.: A small fast universal Turing machine. Technical Report NUIM-CS-TR-2005-12, Dept. of Computer Science, NUI Maynooth (2005)"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Neary, T., Woods, D.: Small fast universal Turing machines. TCS (to appear)","DOI":"10.1016\/j.tcs.2006.06.002"},{"key":"13_CR10","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to parallel computation: P-completeness theory","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P-completeness theory. Oxford University Press, Oxford (1995)"},{"key":"13_CR11","first-page":"299","volume":"4","author":"K. Lindgren","year":"1990","unstructured":"Lindgren, K., Nordahl, M.G.: Universal computation in simple one-dimensional cellular automata. Complex Systems\u00a04, 299\u2013318 (1990)","journal-title":"Complex Systems"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/3-540-45465-9_28","volume-title":"Automata, Languages and Programming","author":"N. Ollinger","year":"2002","unstructured":"Ollinger, N.: The quest for small universal cellular automata. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 318\u2013329. Springer, Heidelberg (2002)"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1023\/B:JOSS.0000015172.31951.7b","volume":"88","author":"C. Moore","year":"1997","unstructured":"Moore, C.: Majority-vote cellular automata, Ising dynamics and P-completeness. Journal of Statistical Physics\u00a088, 795\u2013805 (1997)","journal-title":"Journal of Statistical Physics"},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0167-2789(96)00255-2","volume":"103","author":"C. Moore","year":"1997","unstructured":"Moore, C.: Quasi-linear cellular automata. Physica D\u00a0103, 100\u2013132 (1997)","journal-title":"Physica D"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0167-2789(97)80003-6","volume":"111","author":"C. Moore","year":"1998","unstructured":"Moore, C.: Predicting non-linear cellular automata quickly by decomposing them into linear ones. Physica D\u00a0111, 27\u201341 (1998)","journal-title":"Physica D"},{"key":"13_CR16","doi-asserted-by":"crossref","first-page":"410","DOI":"10.26421\/QIC2.5-7","volume":"2","author":"S. Aaronson","year":"2002","unstructured":"Aaronson, S.: Book review: A new kind of science. Quantum Information and Computation\u00a02, 410\u2013423 (2002)","journal-title":"Quantum Information and Computation"},{"key":"13_CR17","volume-title":"Introduction to automata theory, languages, and computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley, Reading (1979)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T16:14:59Z","timestamp":1736439299000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11786986_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}