{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:01:43Z","timestamp":1744156903481},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","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":[[2001]]},"DOI":"10.1007\/3-540-44683-4_15","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"159-172","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Analysis Problems for Sequential Dynamical Systems and Communicating State Machines"],"prefix":"10.1007","author":[{"given":"Chris","family":"Barrett","sequence":"first","affiliation":[]},{"suffix":"III","given":"Harry B.","family":"Hunt","sequence":"additional","affiliation":[]},{"given":"Madhav V.","family":"Marathe","sequence":"additional","affiliation":[]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[]},{"given":"Daniel J.","family":"Rosenkrantz","sequence":"additional","affiliation":[]},{"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"R. Alur, S. Kannan, and M. Yannakakis. Communicating hierarchical state machines. Proc. 26th International Colloquium on Automata, Languages and Programming (ICALP\u201999), Springer Verlag, 1999.","DOI":"10.1007\/3-540-48523-6_14"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, Y. Rabani and U. Vazirani. Simulating quadratic dynamical systems is PSPACE-complete. Proc. 26th Annual ACM Symposium on the Theory of Computing (STOC\u201994), Montreal, Canada, May 1994, pp. 459\u2013467.","DOI":"10.1145\/195058.195231"},{"key":"15_CR3","unstructured":"C. Barrett, B. Bush, S. Kopp, H. Mortveit and C. Reidys. Sequential Dynamical Systems and Applications to Simulations. Technical Report, Los Alamos National Laboratory, Sept. 1999."},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1109\/18.21239","volume":"34","author":"J. Bruck","year":"1988","unstructured":"J. Bruck and J. Goodman. A generalized convergence theorem for neural networks. IEEE Trans. on Information Theory, Vol. 34, 1988, pp. 1089\u20131092.","journal-title":"IEEE Trans. on Information Theory"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns and P. Tosic. Gardens of Eden and fixed points in sequential dynamical systems. To appear in Proc. of the International Conference on Discrete Models-Combinatorics, Computation and Geometry (DM-CCG), Paris, July 2001.","DOI":"10.46298\/dmtcs.2294"},{"key":"15_CR6","unstructured":"C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz and R. Stearns. Predecessor and permutation existence problems for sequential dynamical systems. Under preparation, May 2001."},{"key":"15_CR7","unstructured":"C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz and R. Stearns. Elements of a theory of computer simulation V: computational complexity and universality. Under preparation, May 2001."},{"key":"15_CR8","first-page":"121","volume":"107\/2-3","author":"C. Barrett","year":"1999","unstructured":"C. Barrett, H. Mortveit and C. Reidys. Elements of a theory of simulation II: sequential dynamical systems. Applied Mathematics and Computation, 1999, vol 107\/2-3, pp. 121\u2013136.","journal-title":"Applied Mathematics and Computation"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"C. Barrett, H. Mortveit and C. Reidys. Elements of a theory of computer simulation III: equivalence of SDS. to appear in Applied Mathematics and Computation, 2000.","DOI":"10.1016\/S0096-3003(00)00042-4"},{"issue":"5","key":"15_CR10","first-page":"525","volume":"1","author":"S. Buss","year":"1991","unstructured":"S. Buss, C. Papadimitriou and J. Tsitsiklis. On the predictability of coupled automata: an allegory about chaos. Complex Systems, 1(5), pp. 525\u2013539, 1991.","journal-title":"Complex Systems"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0096-3003(97)10166-7","volume":"98","author":"C. Barrett","year":"1999","unstructured":"C. Barrett and C. Reidys. Elements of a theory of computer simulation I: sequential CA over random graphs. Applied Mathematics and Computation, Vol. 98, pp. 241\u2013259, 1999.","journal-title":"Applied Mathematics and Computation"},{"key":"15_CR12","unstructured":"C. Barrett, M. Wolinsky and M. Olesen. Emergent local control properties in particle hopping traffic simulations. Proc. Traffic and Granular Flow, Julich, Germany, 1995."},{"key":"15_CR13","unstructured":"P. Flor\u00e9en and P. Orponen. Complexity issues in discrete Hopfield networks. The Computational and Learning Complexity of Neural Networks: Advanced Topics. Ian Parberry (Editor), 2000."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0166-218X(85)90029-0","volume":"12","author":"E. Goles","year":"1985","unstructured":"E. Goles F. Fogelman and D. Pellegrin. Decreasing energy functions as a tool for studying threshold networks. Discrete Applied Mathematics, vol. 12, 1985, pp. 261\u2013277.","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"15_CR15","first-page":"453","volume":"1","author":"F. Green","year":"1987","unstructured":"F. Green. NP-complete problems in cellular automata. Complex Systems, 1(3), pp. 453\u2013474, 1987.","journal-title":"Complex Systems"},{"key":"15_CR16","unstructured":"H. Gutowitz, Ed. Cellular Automata: Theory and Experiment. North Holland, 1989."},{"key":"15_CR17","volume-title":"Ph.D. Thesis","author":"H. Hunt III","year":"1973","unstructured":"H. Hunt III. On the Time and Tape Complexity of Languages. Ph.D. Thesis, Cornell University, Ithaca, NY, 1973."},{"key":"15_CR18","volume-title":"Switching and Finite Automata Theory","author":"Z. Kohavi","year":"1970","unstructured":"Z. Kohavi, Switching and Finite Automata Theory, McGraw-Hill Book Company, New York, 1970."},{"key":"15_CR19","unstructured":"R. Laubenbacher and B. Pareigis. Finite Dynamical Systems. Technical report, Department of Mathematical Sciences, New Mexico State University, Las Cruces."},{"issue":"20","key":"15_CR20","doi-asserted-by":"publisher","first-page":"2354","DOI":"10.1103\/PhysRevLett.64.2354","volume":"64","author":"C. Moore","year":"1990","unstructured":"C. Moore. Unpredictability and undecidability in dynamical systems. Physical Review Letters, 64(20), pp. 2354\u20132357, 1990.","journal-title":"Physical Review Letters"},{"key":"15_CR21","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1088\/0951-7715\/4\/2\/002","volume":"4","author":"C. Moore","year":"1991","unstructured":"C. Moore. Generalized shifts: unpredictability and undecidability in dynamical systems. Nonlinearity, 4, pp. 199\u2013230, 1991.","journal-title":"Nonlinearity"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"H. Mortveit and C. Reidys. Discrete sequential dynamical systems. Discrete Mathematics. Accepted for publication, 2000.","DOI":"10.1016\/S0012-365X(00)00115-1"},{"key":"15_CR23","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1007\/3-540-55719-9_115","volume-title":"International Colloquium on Automata Programming and languages (ICALP\u201992)","author":"A. Rabinovich","year":"1992","unstructured":"A. Rabinovich. Checking equivalences between concurrent systems of finite state processes. International Colloquium on Automata Programming and languages (ICALP\u201992), LNCS Vol. 623, Springer, 1992, pp. 696\u2013707."},{"key":"15_CR24","unstructured":"C. Reidys. On acyclic orientations and SDS. Advances in Applied Mathematics, to appear."},{"key":"15_CR25","unstructured":"C. Reidys. Sequential dynamical systems: phase space properties. Advances in Applied Mathematics, to appear."},{"issue":"3","key":"15_CR26","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1137\/0222042","volume":"22","author":"D. Rosenkrantz","year":"1993","unstructured":"D. Rosenkrantz and H. Hunt III. The complexity of processing hierarchical specifications. SI AM Journal on Computing, 22(3), pp. 627\u2013649, 1993.","journal-title":"SI AM Journal on Computing"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"S. Shukla, H. Hunt III, D. Rosenkrantz and R. Stearns. On the Complexity of Relational Problems for Finite State Processes. Proc. International Colloquium on Automata, Languages and Programming (ICALP\u201996), pp. 466\u2013477.","DOI":"10.1007\/3-540-61440-0_151"},{"issue":"1-3","key":"15_CR28","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/0167-2789(90)90196-V","volume":"45","author":"K. Sutner","year":"1989","unstructured":"K. Sutner. Classifying circular cellular automata. Physica D, 45(1-3), pp. 386\u2013395, 1989.","journal-title":"Physica D"},{"issue":"1","key":"15_CR29","first-page":"19","volume":"5","author":"K. Sutner","year":"1990","unstructured":"K. Sutner. De Bruijn graphs and linear cellular automata. Complex Systems, 5(1), pp. 19\u201330, 1990.","journal-title":"Complex Systems"},{"issue":"1","key":"15_CR30","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1006\/jcss.1995.1009","volume":"50","author":"K. Sutner","year":"1995","unstructured":"K. Sutner. On the computational complexity of finite cellular automata. Journal of Computer and System Sciences, 50(1), pp. 87\u201397, February 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR31","volume-title":"Technical Report CS-R9029","author":"R. Glabbeek van","year":"1990","unstructured":"R. van Glabbeek. The linear time-branching time spectrum. Technical Report CS-R9029, Computer Science Department, CWI, Centre for Mathematics and Computer Science, Netherlands, 1990."},{"key":"15_CR32","series-title":"Lect Notes Comput Sci","volume-title":"The linear time-branching time spectrum II (the semantics of sequential systems with silent moves)","author":"R. Glabbeek van","year":"1993","unstructured":"R. van Glabbeek. The linear time-branching time spectrum II (the semantics of sequential systems with silent moves). LNCS 715, 1993."},{"key":"15_CR33","unstructured":"S. Wolfram, Ed. Theory and applications of cellular automata. World Scientific, 1987."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,17]],"date-time":"2024-02-17T16:58:32Z","timestamp":1708189112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"5 September 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}