{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:54Z","timestamp":1725663774889},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578116"},{"type":"electronic","value":"9783540483373"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57811-0_8","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:24:53Z","timestamp":1330262693000},"page":"73-90","source":"Crossref","is-referenced-by-count":0,"title":["Graph theory and interactive protocols for Reachability Problems on finite Cellular automata"],"prefix":"10.1007","author":[{"given":"A.","family":"Clementi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Impagliazzo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Babai L.: Trading group theory for randomness. Proc. of STOC, 421-(1985).","DOI":"10.1145\/22145.22192"},{"key":"8_CR2","first-page":"254","volume":"36","author":"Moran S. S. Babai L","year":"1985","unstructured":"Babai L., Moran S.: Arthur-Merlin games: a randomized proof system and a hierarchy of complexity classes. J. of Computer and System Sciences, 36, 254\u2013276 (1985).","journal-title":"J. of Computer and System Sciences"},{"issue":"2","key":"8_CR3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"Ravi B. Boppana","year":"1987","unstructured":"Boppana R.B., Hastad J. and Zachos S.: Does Co-NP have short interactive proofs? Information Processing Letter, 127\u2013132 (1987).","journal-title":"Information Processing Letters"},{"key":"8_CR4","unstructured":"Bovet D.P., Crescenzi P. (1993), Introduction to the theory of computational complexity, Prenctice Hall."},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Buss S., Papadimitriou C.H., Tsitsiklis J.N.: On the predictability of coupled automata: an allegory about chaos. Proc. of FOCS, 788\u2013793 (1990).","DOI":"10.1109\/FSCS.1990.89601"},{"key":"8_CR6","unstructured":"Clementi A.: On the Complexity of Cellular Automata, Ph.D. Thesis, in preparation."},{"key":"8_CR7","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1016\/0167-2789(90)90197-W","volume":"45","author":"K. Culik","year":"1990","unstructured":"Culik K., Hurd P. and Yu S.: Formal languages and global cellular automata behaviour. Physica D, 45, 396\u2013403 (1990).","journal-title":"Physica D"},{"key":"8_CR8","first-page":"367","volume":"45","author":"K. Culik","year":"1990","unstructured":"Culik K., Hurd P. and Yu S.: Computation theoretical aspects of cellular automata. Physica D, 45, 367\u2013378 (1990).","journal-title":"Physica D"},{"issue":"2","key":"8_CR9","first-page":"177","volume":"2","author":"K. Culik II","year":"1988","unstructured":"Culik II K., Yu S.: Undecidability of CA classification scheme. Complex Systems, 2 (2), 177\u2013190 (1988).","journal-title":"Complex Systems"},{"key":"8_CR10","first-page":"51","volume":"1","author":"P. Guan","year":"1987","unstructured":"Guan P.: Cellular automata public key cryptosystem, Complex Systems, 1, 51\u201357 (1987).","journal-title":"Complex Systems"},{"key":"8_CR11","first-page":"136","volume":"D 45","author":"H. A. Gutowitz","year":"1990","unstructured":"Gutowitz H.A.: A hierarchycal classification of cellular automata. Physica D 45, 136\u2013156 (1990).","journal-title":"Physica"},{"key":"8_CR12","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01020648","volume":"43","author":"P. Guan","year":"1986","unstructured":"Guan P., He Y.: Exact results for deterministic cellular automata with additive rules. J. of Stat. Physics, 43, 463\u2013478 (1986).","journal-title":"J. of Stat. Physics"},{"key":"8_CR13","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1987","unstructured":"Goldwasser S., Micali M. and Rackoff T.: The knowledge complexity of interactive proof systems. SIAM J. of Computing, 18, 186\u2013208 (1987).","journal-title":"SIAM J. of Computing"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Goldwasser S., Sipser M.: Public coins vs private coins in interactive proofs systems. Proc. of STOC, 59\u201368 (1986).","DOI":"10.1145\/12130.12137"},{"key":"8_CR15","unstructured":"Hardy G.H., Wright E.M.: An introduction to the theory of numbers. Oxford University Press (1968)."},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0167-2789(90)90195-U","volume":"45","author":"J. Kari","year":"1990","unstructured":"Kari J.: Reversibility of 2D cellular automata is undecidable. Physica D, 45, 379\u2013385, (1990).","journal-title":"Physica D"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Koebler J., Shoening U., Turan J.: The Graph Isomorphism Problem \u2014 Its structural complexity. Birkhauser ed, (1993).","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"8_CR18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01223745","volume":"93","author":"O. Martin","year":"1984","unstructured":"Martin O., Odlyzko A.M. and Wolfram S.: Algebraic properties of cellular automata. Comm. Math. Physics, 93, 219-(1984).","journal-title":"Comm. Math. Physics"},{"key":"8_CR19","volume-title":"The theory of error correcting codes","author":"Williams F. F. J. J. Mac","year":"1977","unstructured":"Mac Williams F.J., Sloane N.J.: The theory of error correcting codes. North-Holland, Amsterdam (1977)."},{"key":"8_CR20","unstructured":"Odlyzko A.M.: Discrete Logarithms in finite fields and their cryptographic significance. Bell Laboratories Internal Technical Memorandum, September, 27. (1983) (also in the Proceedings of CRYPTO 1985)."},{"key":"8_CR21","unstructured":"Sutner K.: Computational complexity of finite cellular automata. Internal Note of the Stevens Institute of Technology, Hoboken, NJ 07030 USA (1989). (It will appear in Complex Systems)."},{"issue":"1","key":"8_CR22","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF01217347","volume":"96","author":"S. Wolfram","year":"1984","unstructured":"Wolfram S.: Computation theory of cellular automata. Comm. Math. Phys., 96 (1), 15\u201357 (1984).","journal-title":"Comm. Math. Phys."},{"key":"8_CR23","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1088\/0031-8949\/1985\/T9\/029","volume":"T9","author":"S. Wolfram","year":"1985","unstructured":"Wolfram S.: Twenty problems in the theory of cellular automata. Physica Scrypta, T9,170\u2013183 (1985).","journal-title":"Physica Scrypta"},{"key":"8_CR24","unstructured":"Wolfram S.: Cryptography with cellular automata. Proc. of CRYPTO '85, Springer-Verlag (1985)."},{"key":"8_CR25","unstructured":"Wolfram S.: Theory and application of cellular automata. World Scientific (1986)."},{"key":"8_CR26","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0196-8858(86)90028-X","volume":"7","author":"S. Wolfram","year":"1986","unstructured":"Wolfram S.: Random sequence generation by cellular automata. Advances in Appl. Math., 7, 123\u2013169 (1986).","journal-title":"Advances in Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57811-0_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:14:16Z","timestamp":1605647656000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57811-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578116","9783540483373"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-57811-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}