{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:00:21Z","timestamp":1742976021976,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319223599"},{"type":"electronic","value":"9783319223605"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-22360-5_3","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T08:24:42Z","timestamp":1437985482000},"page":"21-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems"],"prefix":"10.1007","author":[{"given":"Abhijin","family":"Adiga","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chris J.","family":"Kuhlman","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":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Abrahao, B., Chierichetti, F., Kleinberg, R., Panconesi, A.: Trace complexity of network inference. In: Proceedings of the 19th ACM SIGKDD, pp. 491\u2013499. ACM (2013)","DOI":"10.1145\/2487575.2487664"},{"key":"3_CR2","unstructured":"Adiga, A., Kuhlman, C.J., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: Complexity of inferring local transition functions of discrete dynamical systems. Technical report NDSSL-TR-15-048, NDSSL, Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, VA, June 2015"},{"issue":"8","key":"3_CR3","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1016\/j.jcss.2006.03.006","volume":"72","author":"CL Barrett","year":"2006","unstructured":"Barrett, C.L., Hunt III, H.B., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: Complexity of reachability problems for finite discrete dynamical systems. J. Comput. Syst. Sci. 72(8), 1317\u20131345 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"30","key":"3_CR4","doi-asserted-by":"publisher","first-page":"3932","DOI":"10.1016\/j.tcs.2011.02.027","volume":"412","author":"CL Barrett","year":"2011","unstructured":"Barrett, C.L., Hunt III, H.B., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems. Theo. Comput. Sci. 412(30), 3932\u20133946 (2011)","journal-title":"Theo. Comput. Sci."},{"issue":"1\u20132","key":"3_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2007.04.026","volume":"386","author":"CL Barrett","year":"2007","unstructured":"Barrett, C.L., Hunt III, H.B., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E., Thakur, M.: Predecessor existence problems for finite discrete dynamical systems. Theo. Comput. Sci. 386(1\u20132), 3\u201337 (2007)","journal-title":"Theo. Comput. Sci."},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"Barrett, C.L., Hunt III, H.B., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E., Tosic, P.T.: Gardens of Eden and fixed points in sequential dynamical systems. In: DM-CCG, pp. 95\u2013110 (2001)","DOI":"10.46298\/dmtcs.2294"},{"key":"3_CR7","volume-title":"Introduction to Algorithms","author":"T Cormen","year":"2009","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. MIT Press and McGraw-Hill, Cambridge (2009)"},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0304-3975(94)00293-R","volume":"148","author":"B Durand","year":"1995","unstructured":"Durand, B.: A random NP-complete problem for inversion of 2D cellular automata. Theor. Comput. Sci. 148(1), 19\u201332 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942","volume-title":"Networks, crowds and markets: reasoning about a highly connected world","author":"D Easley","year":"2010","unstructured":"Easley, D., Kleinberg, J.: Networks, crowds and markets: reasoning about a highly connected world. Cambridge University Press, New York (2010)"},{"key":"3_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Co., San Francisco (1979)"},{"key":"3_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-0529-0","volume-title":"Neural and automata networks","author":"E Goles","year":"1990","unstructured":"Goles, E., Mart\u00ednez, S.: Neural and automata networks. Kluwer, Dordrecht (1990)"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Gomez Rodriguez, M., Leskovec, J., Krause, A.: Inferring networks of diffusion and influence. In: Proceedings of the 16th ACM SIGKDD, pp. 1019\u20131028. ACM (2010)","DOI":"10.1145\/1835804.1835933"},{"key":"3_CR13","doi-asserted-by":"publisher","unstructured":"Gonzalez-Bailon, S., Borge-Holthoefer, J., Rivero, A., Moreno, Y.: The Dynamics of Protest Recruitment Through an Online Network. In: Nature Scientific Reports, pp. 1\u20137 (2011), doi:10.1038\/srep00197","DOI":"10.1038\/srep00197"},{"key":"3_CR14","volume-title":"Concrete Mathematics","author":"R Graham","year":"1994","unstructured":"Graham, R., Knuth, D., Patashnik, O.: Concrete Mathematics. Addison-Wesley, Reading (1994)"},{"issue":"6","key":"3_CR15","doi-asserted-by":"publisher","first-page":"1420","DOI":"10.1086\/226707","volume":"83","author":"M Granovetter","year":"1978","unstructured":"Granovetter, M.: Threshold models of collective behavior. Am. J. Sociol. 83(6), 1420\u20131443 (1978)","journal-title":"Am. J. Sociol."},{"issue":"3","key":"3_CR16","first-page":"453","volume":"1","author":"F Green","year":"1987","unstructured":"Green, F.: NP-complete problems in cellular automata. Complex Syst. 1(3), 453\u2013474 (1987)","journal-title":"Complex Syst."},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$. Acta Mathematica 182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"3_CR18","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"MJ Kearns","year":"1994","unstructured":"Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge (1994)"},{"key":"3_CR19","series-title":"ch. 24","volume-title":"Algorithmic Graph Theory","author":"J Kleinberg","year":"2008","unstructured":"Kleinberg, J.: Cascading behavior in networks: Algorithmic and economic issues. In: Nissan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Graph Theory. ch. 24. Cambridge University Press, New York (2008)"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Kosub, S., Homan, C.M.: Dichotomy results for fixed point counting in Boolean dynamical systems. In: Proceedings of the ICTCS, pp. 163\u2013174 (2007)","DOI":"10.1142\/9789812770998_0018"},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1146\/annurev.soc.28.110601.141117","volume":"28","author":"M Macy","year":"2002","unstructured":"Macy, M., Willer, R.: From factors to actors: Computational sociology and agent-based modeling. Ann. Rev. Sociol. 28, 143\u2013166 (2002)","journal-title":"Ann. Rev. Sociol."},{"key":"3_CR22","volume-title":"An Introduction to Sequential Dynamical Systems","author":"HS Mortveit","year":"2007","unstructured":"Mortveit, H.S., Reidys, C.M.: An Introduction to Sequential Dynamical Systems. Springer, Heidelberg (2007)"},{"key":"3_CR23","unstructured":"Murphy, K.P.: Passively learning finite automata. Technical report, Computer Science Department, UC Davis (1995)"},{"key":"3_CR24","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms","author":"R Neidermeier","year":"2006","unstructured":"Neidermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford University Press, New York (2006)"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Romero, D.M., Meeder, B., Kleinberg, J.: Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In: Proceedings of the 20th WWW, pp. 695\u2013704. ACM (2011)","DOI":"10.1145\/1963405.1963503"},{"issue":"8","key":"3_CR26","doi-asserted-by":"publisher","first-page":"5163","DOI":"10.1109\/TIT.2011.2158885","volume":"57","author":"D Shah","year":"2011","unstructured":"Shah, D., Zaman, T.: Rumors in a network: Who\u2019s the culprit? IEEE Trans. Inf. Theory 57(8), 5163\u20135181 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"3_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-642-13562-0_38","volume-title":"Theory and Applications of Models of Computation","author":"S Soundarajan","year":"2010","unstructured":"Soundarajan, S., Hopcroft, J.E.: Recovering social networks from contagion information. In: Kratochv\u00edl, J., Li, A., Fiala, J., Kolman, P. (eds.) TAMC 2010. LNCS, vol. 6108, pp. 419\u2013430. Springer, Heidelberg (2010)"},{"issue":"6","key":"3_CR28","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1080\/03081079.2012.695899","volume":"41","author":"K Sutner","year":"2012","unstructured":"Sutner, K.: Computational classification of cellular automata. Int. J. Gen. Syst. 41(6), 595\u2013607 (2012)","journal-title":"Int. J. Gen. Syst."},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1016\/j.ress.2005.11.031","volume":"91","author":"TG Trucano","year":"2006","unstructured":"Trucano, T.G., Swiler, L.P., Igusa, T., Oberkampf, W.L., Pilch, M.: Calibration, validation and sensitivity analysis: What is what. Reliab. Eng. Syst. Saf. 91, 1331\u20131357 (2006)","journal-title":"Reliab. Eng. Syst. Saf."},{"issue":"9","key":"3_CR30","doi-asserted-by":"publisher","first-page":"5962","DOI":"10.1073\/pnas.1116502109","volume":"109","author":"J Ugander","year":"2012","unstructured":"Ugander, J., Backstrom, L., Marlow, C., Kleinberg, J.: Structural diversity in social contagion. PNAS 109(9), 5962\u20135966 (2012)","journal-title":"PNAS"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-22360-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T13:46:41Z","timestamp":1676468801000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-22360-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319223599","9783319223605"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-22360-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}