{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T21:40:21Z","timestamp":1737322821836,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_46","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"511-520","source":"Crossref","is-referenced-by-count":1,"title":["A Time Hierarchy Theorem for Nondeterministic Cellular Automata"],"prefix":"10.1007","author":[{"given":"Chuzo","family":"Iwamoto","sequence":"first","affiliation":[]},{"given":"Harumasa","family":"Yoneda","sequence":"additional","affiliation":[]},{"given":"Kenichi","family":"Morita","sequence":"additional","affiliation":[]},{"given":"Katsunobu","family":"Imai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"46_CR1","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"Cook, S.A.: A hierarchy for nondeterministic time complexity. J. Comput. System Sci.\u00a07, 343\u2013353 (1973)","journal-title":"J. Comput. System Sci."},{"key":"46_CR2","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"Cook, S.A., Reckhow, R.A.: Time bounded random access machines. J. Comput. System Sci.\u00a07, 354\u2013375 (1973)","journal-title":"J. Comput. System Sci."},{"doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M.: The tight deterministic time hierarchy. In: Proc. ACM Symp. on Theory of Computing, pp. 8\u201316 (1982)","key":"46_CR3","DOI":"10.1145\/800070.802172"},{"key":"46_CR4","doi-asserted-by":"publisher","first-page":"285","DOI":"10.2307\/1994208","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Trans. Amer. Math. Soc.\u00a0117, 285\u2013306 (1965)","journal-title":"Trans. Amer. Math. Soc."},{"key":"46_CR5","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"F.C. Hennie","year":"1965","unstructured":"Hennie, F.C.: One-tape off-line Turing machine computations. Inform. Contr.\u00a08, 553\u2013578 (1965)","journal-title":"Inform. Contr."},{"key":"46_CR6","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1145\/321724.321727","volume":"19","author":"O.H. Ibarra","year":"1972","unstructured":"Ibarra, O.H.: A note concerning nondeterministic tape complexity. J. Assoc. Comput. Mach.\u00a019, 608\u2013612 (1972)","journal-title":"J. Assoc. Comput. Mach."},{"doi-asserted-by":"crossref","unstructured":"Iwama, K., Iwamoto, C.: Parallel complexity hierarchies based on PRAMs and DLOGTIME-uniform circuits. In: Proc. 11th IEEE Conf. on Computational Complexity, pp. 24\u201332 (1996)","key":"46_CR7","DOI":"10.1109\/CCC.1996.507665"},{"key":"46_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/BFb0055808","volume-title":"Mathematical Foundations of Computer Science 1998","author":"K. Iwama","year":"1998","unstructured":"Iwama, K., Iwamoto, C.: Improved time and space hierarchies of one-tape off-line TMs. In: Brim, L., Gruska, J., Zlatu\u0161ka, J. (eds.) MFCS 1998. LNCS, vol.\u00a01450, pp. 580\u2013588. Springer, Heidelberg (1998)"},{"key":"46_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/3-540-45687-2_30","volume-title":"Mathematical Foundations of Computer Science 2002","author":"C. Iwamoto","year":"2002","unstructured":"Iwamoto, C., et al.: Computational complexity in the hyperbolic plane. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 365\u2013374. Springer, Heidelberg (2002)"},{"key":"46_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-540-31834-7_17","volume-title":"Machines, Computations, and Universality","author":"C. Iwamoto","year":"2005","unstructured":"Iwamoto, C., et al.: Hierarchies of DLOGTIME-uniform circuits. In: Margenstern, M. (ed.) MCU 2004. LNCS, vol.\u00a03354, pp. 211\u2013222. Springer, Heidelberg (2005)"},{"key":"46_CR11","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1016\/S0304-3975(01)00112-8","volume":"270","author":"C. Iwamoto","year":"2002","unstructured":"Iwamoto, C., et al.: Constructible functions in cellular automata and their applications to hierarchy results. Theoret. Comput. Sci.\u00a0270, 797\u2013809 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"46_CR12","first-page":"700","volume":"E87-D","author":"C. Iwamoto","year":"2004","unstructured":"Iwamoto, C., Margenstern, M.: Time and space complexity classes of hyperbolic cellular automata. IEICE Trans. on Information and Systems\u00a0E87-D(3), 700\u2013707 (2004)","journal-title":"IEICE Trans. on Information and Systems"},{"key":"46_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/11537311_13","volume-title":"Fundamentals of Computation Theory","author":"C. Iwamoto","year":"2005","unstructured":"Iwamoto, C., et al.: Translational lemmas for alternating TMs and PRAMs. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 126\u2013137. Springer, Heidelberg (2005)"},{"key":"46_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/3-540-55210-3_194","volume-title":"STACS 92","author":"K. Lory\u015b","year":"1992","unstructured":"Lory\u015b, K.: New time hierarchy results for deterministic TMs. In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol.\u00a0577, pp. 329\u2013336. Springer, Heidelberg (1992)"},{"key":"46_CR15","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(87)90124-1","volume":"50","author":"J. Mazoyer","year":"1987","unstructured":"Mazoyer, J.: A 6-state minimal time solution to the firing squad synchronization problem. Theoret. Comput. Sci.\u00a050, 183\u2013238 (1987)","journal-title":"Theoret. Comput. Sci."},{"key":"46_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(79)90028-X","volume":"19","author":"W.J. Paul","year":"1979","unstructured":"Paul, W.J.: On time hierarchies. J. Comput. System Sci.\u00a019, 197\u2013202 (1979)","journal-title":"J. Comput. System Sci."},{"key":"46_CR17","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF00264255","volume":"14","author":"W.J. Paul","year":"1980","unstructured":"Paul, W.J., Prau\u00df, E.J., Reischuk, R.: On alternation. Acta Inform.\u00a014, 243\u2013255 (1980)","journal-title":"Acta Inform."},{"key":"46_CR18","volume-title":"Theory of recursive functions and effective computability","author":"H. Rogers Jr.","year":"1967","unstructured":"Rogers Jr., H.: Theory of recursive functions and effective computability. McGraw-Hill, New York (1967)"},{"unstructured":"Seiferas, J.I.: Nondeterministic time and space complexity classes. MIT-LCS-TR-137, Proj.\u00a0MAC, MIT, Cambridge, Mass. (Sept. 1974)","key":"46_CR19"},{"issue":"1","key":"46_CR20","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J.I. Seiferas","year":"1978","unstructured":"Seiferas, J.I., Fischer, M.J., Meyer, A.R.: Separating nondeterministic time complexity classes. J. Assoc. Comput. Mach.\u00a025(1), 146\u2013167 (1978)","journal-title":"J. Assoc. Comput. Mach."},{"key":"46_CR21","volume-title":"Introduction to the theory of computation","author":"M. Sipser","year":"1997","unstructured":"Sipser, M.: Introduction to the theory of computation. PWS Publishing, Boston (1997)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_46.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T21:27:01Z","timestamp":1737322021000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_46","relation":{},"subject":[]}}