{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T19:23:33Z","timestamp":1769282613884,"version":"3.49.0"},"reference-count":37,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2003,2,1]],"date-time":"2003-02-01T00:00:00Z","timestamp":1044057600000},"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":3819,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,2]]},"DOI":"10.1016\/s0304-3975(02)00395-x","type":"journal-article","created":{"date-parts":[[2003,2,28]],"date-time":"2003-02-28T19:20:13Z","timestamp":1046460013000},"page":"41-64","source":"Crossref","is-referenced-by-count":35,"title":["Reachability problems for sequential dynamical systems with threshold functions"],"prefix":"10.1016","volume":"295","author":[{"given":"Chris","family":"Barrett","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harry B.","family":"Hunt III","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhav V.","family":"Marathe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.S.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel J.","family":"Rosenkrantz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(02)00395-X_BIB1","doi-asserted-by":"crossref","unstructured":"R. Alur, S. Kannan, M. Yannakakis, Communicating hierarchical state machines, Proc. 26th Internat. Colloq. on Automata, Languages, and Programming (ICALP), Springer, Berlin, 1999, pp. 169\u2013178.","DOI":"10.1007\/3-540-48523-6_14"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB2","doi-asserted-by":"crossref","unstructured":"E. Asarin, O. Maler, On some relations between dynamical systems and transition systems, Proc. 21st Internat. Colloq. on Automata, Languages and Programming (ICALP), Jerusalem, Israel, Lecture Notes in Computer Science, Vol. 820, Springer, Berlin, July 1994, pp. 59\u201372.","DOI":"10.1007\/3-540-58201-0_58"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB3","doi-asserted-by":"crossref","unstructured":"C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, Analysis problems for sequential dynamical systems and communicating state machines, in: Proc. Internat. Symp. on Mathematical Foundations of Computer Science (MFCS\u201901), Marianske Lazne, Czech Republic, August 2001, Lecture Notes in Computer Science, Vol. 2136, Springer, Berlin, pp. 159\u2013172.","DOI":"10.1007\/3-540-44683-4_15"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB4","unstructured":"C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, Further analysis of sequential dynamical systems with restricted local transition functions, February 2002, in preparation."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB5","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/S0096-3003(00)00042-4","article-title":"Elements of a theory of computer simulation III","volume":"122","author":"Barrett","year":"2001","journal-title":"Appl. Math. Comput."},{"issue":"2","key":"10.1016\/S0304-3975(02)00395-X_BIB6","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1145\/322374.322380","article-title":"On communicating finite-state machines","volume":"30","author":"Brand","year":"1983","journal-title":"J. Assoc. Comput. Mach."},{"issue":"5","key":"10.1016\/S0304-3975(02)00395-X_BIB7","first-page":"525","article-title":"On the predictability of coupled automata","volume":"1","author":"Buss","year":"1991","journal-title":"Complex Systems"},{"issue":"2","key":"10.1016\/S0304-3975(02)00395-X_BIB8","first-page":"177","article-title":"Undecidability of CA classification schemes","volume":"2","author":"Cullik","year":"1988","journal-title":"Complex Systems"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB9","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0166-218X(83)90105-1","article-title":"Transient length in sequential iterations of threshold functions","volume":"6","author":"Flor\u00e9en","year":"1983","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB10","unstructured":"P. Flore\u00e9n, P. Orponen, Complexity issues in discrete Hopfield networks, in: I. Parberry (Ed.), Computational and Learning Complexity of Neural Networks: Advanced Topics, forthcoming."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB11","unstructured":"P. Gacs, Deterministic computations whose history is independent of the order of asynchronous updating, Technical Report, Computer Science Department, Boston University, 1997."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB12","series-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB13","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0304-3975(85)90057-X","article-title":"On dynamics of positive automata networks","volume":"41","author":"Goles","year":"1985","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"10.1016\/S0304-3975(02)00395-X_BIB14","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1145\/5001.5002","article-title":"Proving liveness for networks of communicating finite state machines","volume":"8","author":"Gouda","year":"1986","journal-title":"ACM Trans. Programming Languages Systems (TOPLAS)"},{"issue":"3","key":"10.1016\/S0304-3975(02)00395-X_BIB15","first-page":"453","article-title":"NP-complete problems in cellular automata","volume":"1","author":"Green","year":"1987","journal-title":"Complex Systems"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB16","series-title":"Cellular Automata","year":"1989"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB17","doi-asserted-by":"crossref","unstructured":"D. Harel, O. Kupferman, M.Y. Vardi, On the complexity of verifying concurrent transition systems, Proc. 8th Internat. Conf. on Concurrency Theory (CONCUR\u201997), Warsaw, Poland, July 1997, Lecture Notes in Computer Science, Vol. 1243, 1997, pp. 258\u2013272.","DOI":"10.1007\/3-540-63141-0_18"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB18","series-title":"Communicating Sequential Processes","author":"Hoare","year":"1984"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB19","doi-asserted-by":"crossref","first-page":"3088","DOI":"10.1073\/pnas.81.10.3088","article-title":"Neural networks and physical systems with emergent collective computational abilities","volume":"81","author":"Hopfield","year":"1982","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB20","doi-asserted-by":"crossref","first-page":"7716","DOI":"10.1073\/pnas.90.16.7716","article-title":"Evolutionary games and computer simulations","volume":"90","author":"Huberman","year":"1993","journal-title":"Proc. Nat. Acad. Sci."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB21","series-title":"Switching and Finite Automata Theory","author":"Kohavi","year":"1970"},{"key":"10.1016\/S0304-3975(02)00395-X_BIB22","unstructured":"R. Laubenbacher, B. Pareigis, Finite dynamical systems, Technical Report, Department of Mathematical Sciences, New Mexico State University, Las Cruces."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB23","unstructured":"B. Martin, A geometrical hierarchy of graph via cellular automata, in: Th. Worsch, R. Wolmar (Eds.), Proc. Mathematical Foundations of Computer Science (MFCS\u201998): Satellite Workshop on Graph Automata, Universit\u00e4t Karlsruhe, 1998."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB24","series-title":"Communicating and Mobile systems","author":"Milner","year":"1999"},{"issue":"20","key":"10.1016\/S0304-3975(02)00395-X_BIB25","doi-asserted-by":"crossref","first-page":"2354","DOI":"10.1103\/PhysRevLett.64.2354","article-title":"Unpredictability and undecidability in dynamical systems","volume":"64","author":"Moore","year":"1990","journal-title":"Phys. Rev. Lett."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB26","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0012-365X(00)00115-1","article-title":"Discrete sequential dynamical systems","volume":"226","author":"Mortveit","year":"2001","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB27","unstructured":"C. Nicthiu, E. Remila, Simulations of graph automaton, in: Th. Worsch, R. Wolmar (Eds.), Proc. Mathematical Foundations of Computer Science (MFCS\u201998), Satellite Workshop on Graph Automata, Universit\u00e4t Karlsruhe, 1998, pp. 69\u201378."},{"issue":"3","key":"10.1016\/S0304-3975(02)00395-X_BIB28","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1023\/A:1013640918785","article-title":"Deadlock detection in communicating finite state machines by even reachability analysis","volume":"2","author":"Peng","year":"1997","journal-title":"Mobile Networks (MONET)"},{"issue":"1\u20132","key":"10.1016\/S0304-3975(02)00395-X_BIB29","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0304-3975(94)90232-1","article-title":"Asynchronous automata versus asynchronous cellular automata","volume":"132","author":"Pighizzini","year":"1994","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10.1016\/S0304-3975(02)00395-X_BIB30","first-page":"164","article-title":"Complexity of equivalence problems for concurrent systems of finite agents","volume":"127","author":"Rabinovich","year":"1997","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB31","unstructured":"C. Reidys, Sequential dynamical systems: phase space properties, Adv. Appl. Math., to appear."},{"issue":"1\u20132","key":"10.1016\/S0304-3975(02)00395-X_BIB32","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0304-3975(94)90236-4","article-title":"One-way cellular automata on Cayley graphs","volume":"132","author":"Roka","year":"1994","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"10.1016\/S0304-3975(02)00395-X_BIB33","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0020-0190(97)00110-5","article-title":"Finite automata-models for the investigation of dynamical systems","volume":"63","author":"Schittenkopf","year":"1997","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB34","doi-asserted-by":"crossref","unstructured":"S.K. Shukla, H.B. Hunt III, D.J. Rosenkrantz, R.E. Stearns, On the complexity of relational problems for finite state processes, Internat. Colloq. on Automata Programming and Languages (ICALP), 1996, pp. 466\u2013477.","DOI":"10.1007\/3-540-61440-0_151"},{"issue":"1","key":"10.1016\/S0304-3975(02)00395-X_BIB35","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1006\/jcss.1995.1009","article-title":"On the computational complexity of finite cellular automata","volume":"50","author":"Sutner","year":"1995","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB36","unstructured":"M. Vardi, P. Wolper, An automata-theoretic approach to automatic program verification, Proc. 1st IEEE Symp. on Logic in Computer Science, 1986, pp. 332\u2013344."},{"key":"10.1016\/S0304-3975(02)00395-X_BIB37","series-title":"Theory and Applications of Cellular Automata","year":"1987"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750200395X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750200395X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,17]],"date-time":"2020-03-17T19:01:25Z","timestamp":1584471685000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439750200395X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,2]]},"references-count":37,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2003,2]]}},"alternative-id":["S030439750200395X"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(02)00395-x","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,2]]}}}