{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T18:51:42Z","timestamp":1676055102803},"reference-count":29,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1991,7,1]],"date-time":"1991-07-01T00:00:00Z","timestamp":678326400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8052,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1991,7]]},"DOI":"10.1016\/0166-218x(91)90094-d","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:43:01Z","timestamp":1027640581000},"page":"85-101","source":"Crossref","is-referenced-by-count":11,"title":["Cellular automata, \u03c9\u03c9-regular sets, and sofic systems"],"prefix":"10.1016","volume":"32","author":[{"suffix":"II","given":"Karel","family":"Culik","sequence":"first","affiliation":[]},{"given":"Sheng","family":"Yu","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0166-218X(91)90094-D_BIB1","first-page":"1","article-title":"A simple universal cellular automaton and its one-way and totalistic version","volume":"1","author":"Albert","year":"1987","journal-title":"Complex Systems"},{"key":"10.1016\/0166-218X(91)90094-D_BIB2","series-title":"Automata on Infinite Words","first-page":"28","article-title":"Ensembles reconnaissables de mots bi-infinis limite et d\u00e9terminisme","volume":"192","author":"Beauquier","year":"1984"},{"key":"10.1016\/0166-218X(91)90094-D_BIB3","article-title":"The undecidability of the domino problem","volume":"66","author":"Berger","year":"1966","journal-title":"Mem. Amer. Math. Soc."},{"key":"10.1016\/0166-218X(91)90094-D_BIB4","series-title":"Transductions and Context-Free Languages","author":"Berstel","year":"1979"},{"key":"10.1016\/0166-218X(91)90094-D_BIB5","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0022-0000(80)90010-0","article-title":"Adherences of languages","volume":"20","author":"Boasson","year":"1980","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0166-218X(91)90094-D_BIB6","series-title":"Ergodic Theory and Topological Dynamics","author":"Brown","year":"1976"},{"key":"10.1016\/0166-218X(91)90094-D_BIB7","first-page":"1","article-title":"Decision theories II\u2014the monadic second-order theory of \u03c91","volume":"328","author":"B\u00fcchi","year":"1973"},{"key":"10.1016\/0166-218X(91)90094-D_BIB8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0022-0000(74)80051-6","article-title":"Theories of automata on \u03c9-tapes: a simplified approach","volume":"8","author":"Choueka","year":"1974","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0166-218X(91)90094-D_BIB9","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/S0019-9958(81)90444-7","article-title":"Equivalence problems for mappings on infinite string","volume":"49","author":"Culik","year":"1981","journal-title":"Inform. and Control"},{"key":"10.1016\/0166-218X(91)90094-D_BIB10","doi-asserted-by":"crossref","unstructured":"K. Culik II, J. Pachl and S. Yu, On the limit sets of cellular automata, SIAM J. Comput., to appear.","DOI":"10.1137\/0218057"},{"key":"10.1016\/0166-218X(91)90094-D_BIB11","series-title":"Introduction to Formal Language Theorem","author":"Harrison","year":"1978"},{"key":"10.1016\/0166-218X(91)90094-D_BIB12","series-title":"Automata on Infinite Words","first-page":"147","article-title":"The adherences of languages as topological spaces","volume":"192","author":"Head","year":"1984"},{"key":"10.1016\/0166-218X(91)90094-D_BIB13","series-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft","year":"1979"},{"key":"10.1016\/0166-218X(91)90094-D_BIB14","first-page":"69","article-title":"Formal language characterizations of cellular automaton limit sets","volume":"1","author":"Hurd","year":"1987","journal-title":"Complex Systems"},{"key":"10.1016\/0166-218X(91)90094-D_BIB15","series-title":"Ph.D. Dissertation","article-title":"The application of formal language theorem to the dynamical behavior of cellular automata","author":"Hurd","year":"1988"},{"key":"10.1016\/0166-218X(91)90094-D_BIB16","series-title":"General Topology","author":"Kelley","year":"1955"},{"key":"10.1016\/0166-218X(91)90094-D_BIB17","volume":"Vol. I","author":"Knuth","year":"1973"},{"key":"10.1016\/0166-218X(91)90094-D_BIB18","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","article-title":"Testing and generating infinite sequences by a finite automaton","volume":"9","author":"McNaughton","year":"1966","journal-title":"Inform. and Control"},{"key":"10.1016\/0166-218X(91)90094-D_BIB19_1","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/800070.802176","article-title":"Ensembles reconnaissables de mots biinfinis","author":"Nivat","year":"1982","journal-title":"Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing"},{"key":"10.1016\/0166-218X(91)90094-D_BIB19_2","doi-asserted-by":"crossref","first-page":"513","DOI":"10.4153\/CJM-1986-025-6","volume":"38","author":"Nivat","year":"1986","journal-title":"Canad. J. Math."},{"key":"10.1016\/0166-218X(91)90094-D_BIB20","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(86)90136-2","article-title":"On the complementation of B\u00fcchi automata","volume":"47","author":"Pecuchet","year":"1986","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0166-218X(91)90094-D_BIB21","series-title":"Research Report","article-title":"Finitely generated sofic systems","author":"Restivo","year":"1986"},{"key":"10.1016\/0166-218X(91)90094-D_BIB22","article-title":"Decidable theories I\u2014B\u00fcchis monadic second-order successor arithmetics","volume":"120","author":"Siefkes","year":"1970"},{"key":"10.1016\/0166-218X(91)90094-D_BIB23","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(87)90008-9","article-title":"The complementation problem for B\u00fcchi automata with application to temporal logic","volume":"49","author":"Sistla","year":"1987","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0166-218X(91)90094-D_BIB24","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1007\/BF01295322","article-title":"Subshifts of finite type and sofic systems","volume":"77","author":"Weiss","year":"1973","journal-title":"Monatsh. Math."},{"issue":"3","key":"10.1016\/0166-218X(91)90094-D_BIB25","doi-asserted-by":"crossref","DOI":"10.1090\/S0002-9939-1986-0857950-4","article-title":"A sofic system with infinitely many minimal covers","volume":"98","author":"Williams","year":"1986","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/0166-218X(91)90094-D_BIB26","first-page":"1","article-title":"Universality and complexity in cellular automata","volume":"10D","author":"Wolfram","year":"1984","journal-title":"Phys."},{"key":"10.1016\/0166-218X(91)90094-D_BIB27","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF01217347","article-title":"Computation theory of cellular automata","volume":"96","author":"Wolfram","year":"1984","journal-title":"Comm. Math. Phys."},{"key":"10.1016\/0166-218X(91)90094-D_BIB28","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1088\/0031-8949\/1985\/T9\/029","article-title":"Twenty problems in the theory of cellular automata","volume":"T9","author":"Wolfram","year":"1985","journal-title":"Phys. Scripta"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X9190094D?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X9190094D?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T02:20:30Z","timestamp":1555122030000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0166218X9190094D"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,7]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,7]]}},"alternative-id":["0166218X9190094D"],"URL":"https:\/\/doi.org\/10.1016\/0166-218x(91)90094-d","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1991,7]]}}}