{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T04:18:05Z","timestamp":1751948285135,"version":"3.41.2"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030003883"},{"type":"electronic","value":"9783030003890"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-00389-0_10","type":"book-chapter","created":{"date-parts":[[2018,9,19]],"date-time":"2018-09-19T19:12:43Z","timestamp":1537384363000},"page":"167-189","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Monoidal Computer III: A Coalgebraic View of Computability and Complexity (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Dusko","family":"Pavlovic","sequence":"first","affiliation":[]},{"given":"Muzamil","family":"Yahia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,20]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Altenkirch, T., Chapman, J., Uustalu, T.: Monads need not be endofunctors. Log. Methods Comput. Sci. 11(1) (2015)","DOI":"10.2168\/LMCS-11(1:3)2015"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Asperti, A.: The intensional content of Rice\u2019s Theorem. In: Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, pp. 113\u2013119. ACM, New York (2008)","DOI":"10.1145\/1328438.1328455"},{"key":"10_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-14535-8","volume-title":"Code Biology: A New Science of Life","author":"M Barbieri","year":"2015","unstructured":"Barbieri, M.: Code Biology: A New Science of Life. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-14535-8"},{"key":"10_CR4","unstructured":"Barendregt, H.P.: The Lambda Calculus: Its Syntax and Semantics. vol. 103, North Holland (1984)"},{"issue":"2","key":"10_CR5","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1017\/S0960129512000096","volume":"23","author":"M Bartha","year":"2013","unstructured":"Bartha, M.: The monoidal structure of turing machines. Math. Struct. Comput. Sci. 23(2), 204\u2013246 (2013)","journal-title":"Math. Struct. Comput. Sci."},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pp. 11\u201320. ACM (1993)","DOI":"10.1145\/167088.167097"},{"issue":"2","key":"10_CR7","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M Blum","year":"1967","unstructured":"Blum, M.: A machine-independent theory of the complexity of recursive functions. J. ACM 14(2), 322\u2013336 (1967)","journal-title":"J. ACM"},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-540-78499-9_17","volume-title":"Foundations of Software Science and Computational Structures","author":"MM Bonsangue","year":"2008","unstructured":"Bonsangue, M.M., Rutten, J., Silva, A.: Coalgebraic logic and synthesis of mealy machines. In: Amadio, R. (ed.) FoSSaCS 2008. LNCS, vol. 4962, pp. 231\u2013245. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78499-9_17"},{"key":"10_CR9","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42900-7","volume-title":"Models of Computation","author":"R Bruni","year":"2017","unstructured":"Bruni, R., Montanari, U.: Models of Computation. Texts in Theoretical Computer Science. An EATCS Series. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-42900-7"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"345","DOI":"10.2307\/2371045","volume":"58","author":"A Church","year":"1936","unstructured":"Church, A.: An unsolvable problem of elementary number theory. Am. J. Math. 58, 345\u2013363 (1936)","journal-title":"Am. J. Math."},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.entcs.2012.08.009","volume":"286","author":"J Robin","year":"2012","unstructured":"Robin, J., Cockett, B., D\u00edaz-Bo\u00efls, J., Gallagher, J., Hrubes, P.: Timed sets, functional complexity, and computability. Electr. Notes Theor. Comput. Sci. 286, 117\u2013137 (2012)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"issue":"2\u20133","key":"10_CR12","first-page":"183","volume":"156","author":"J Robin","year":"2008","unstructured":"Robin, J., Cockett, B., Hofstra, P.J.W.: Introduction to turing categories. Ann. Pure Appl. Logic 156(2\u20133), 183\u2013209 (2008)","journal-title":"Ann. Pure Appl. Logic"},{"key":"10_CR13","unstructured":"Eilenberg, S., Elgot, C.C.: Recursiveness. ACM Monograph. Academic Press (1970)"},{"issue":"1","key":"10_CR14","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.entcs.2006.06.003","volume":"164","author":"HH Hansen","year":"2006","unstructured":"Hansen, H.H., Costa, D., Rutten, J.J.M.M.: Synthesis of mealy machines using derivatives. Electr. Notes Theor. Comput. Sci. 164(1), 27\u201345 (2006)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(85)90062-3","volume":"41","author":"S Hayashi","year":"1985","unstructured":"Hayashi, S.: Adjunction of semifunctors: categorical structures in nonextensional lambda calculus. Theor. Comput. Sci. 41, 95\u2013104 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"10","key":"10_CR16","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1016\/j.apal.2013.05.002","volume":"164","author":"PJW Hofstra","year":"2013","unstructured":"Hofstra, P.J.W., Warren, M.A.: Combinatorial realizability models of type theory. Ann. Pure Appl. Logic 164(10), 957\u2013988 (2013)","journal-title":"Ann. Pure Appl. Logic"},{"key":"10_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511525889","volume-title":"Algebraic Automata Theory. Cambridge Studies in Advanced Mathematics","author":"WML Holcombe","year":"1982","unstructured":"Holcombe, W.M.L.: Algebraic Automata Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (1982)"},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0304-3975(95)00140-9","volume":"166","author":"R Hoofman","year":"1996","unstructured":"Hoofman, R.: Comparing models of the intensional typed $$\\lambda $$-calculus. Theor. Comput. Sci. 166(1), 83\u201399 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Hyland, M.: The effective topos. In: Troelstra, A.S., van Dalen, D. (eds.) L. E. J. Brouwer Centenary Symposium, Studies in Logic and the Foundations of Mathematics, vol. 110, pp. 165\u2013216. North-Holland (1982)","DOI":"10.1016\/S0049-237X(09)70129-6"},{"key":"10_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316823187","volume-title":"Introduction to Coalgebra: Towards Mathematics of States and Observation. Cambridge Tracts in Theoretical Computer Science","author":"B Jacobs","year":"2016","unstructured":"Jacobs, B.: Introduction to Coalgebra: Towards Mathematics of States and Observation. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge (2016)"},{"key":"10_CR21","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2003.001.0001","volume-title":"Computability and Complexity: From a Programming Perspective. Foundations of Computing","author":"ND Jones","year":"1997","unstructured":"Jones, N.D.: Computability and Complexity: From a Programming Perspective. Foundations of Computing. The MIT Press, Cambridge (1997)"},{"issue":"4","key":"10_CR22","doi-asserted-by":"publisher","first-page":"150","DOI":"10.2307\/2267778","volume":"3","author":"SC Kleene","year":"1938","unstructured":"Kleene, S.C.: On notation for ordinal numbers. J. Symb. Log. 3(4), 150\u2013155 (1938)","journal-title":"J. Symb. Log."},{"issue":"38","key":"10_CR23","doi-asserted-by":"publisher","first-page":"5043","DOI":"10.1016\/j.tcs.2011.03.023","volume":"412","author":"B Klin","year":"2011","unstructured":"Klin, B.: Bialgebras for structural operational semantics. Theor. Comput. Sci. 412(38), 5043\u20135069 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR24","series-title":"Cambridge Studies in Advanced Mathematics","volume-title":"Introduction to Higher Order Categorical Logic","author":"J Lambek","year":"1986","unstructured":"Lambek, J., Scott, P.: Introduction to Higher Order Categorical Logic. Cambridge Studies in Advanced Mathematics, vol. 7. Cambridge University Press, Cambridge (1986)"},{"key":"10_CR25","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-9839-7","volume-title":"Categories for the Working Mathematician","author":"S Mac Lane","year":"1971","unstructured":"Mac Lane, S.: Categories for the Working Mathematician. Graduate Texts in Mathematics, vol. 5. Springer, New York (1971)"},{"key":"10_CR26","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0890-5401(91)90052-4","volume":"93","author":"E Moggi","year":"1991","unstructured":"Moggi, E.: Notions of computation and monads. Inf. Comput. 93, 55\u201392 (1991)","journal-title":"Inf. Comput."},{"issue":"2","key":"10_CR27","doi-asserted-by":"publisher","first-page":"189","DOI":"10.2178\/bsl\/1286889124","volume":"16","author":"YN Moschovakis","year":"2010","unstructured":"Moschovakis, Y.N.: Kleene\u2019s amazing second recursion theorem. Bull. Symb. Log. 16(2), 189\u2013239 (2010)","journal-title":"Bull. Symb. Log."},{"key":"10_CR28","volume-title":"Theory of Self-Reproducing Automata","author":"J von Neumann","year":"1966","unstructured":"von Neumann, J., Burks, A.W.: Theory of Self-Reproducing Automata. University of Illinois Press, Champaign (1966)"},{"key":"10_CR29","unstructured":"Odifreddi, P.: Classical Recursion Theory : The Theory of Functions and Sets of Natural Numbers. Studies in Logic and the Foundations of Mathematics, vol. 125. North-Holland, Amsterdam, New-York, Oxford, Tokyo (1989)"},{"key":"10_CR30","unstructured":"van Oosten, J.: Realizability: An Introduction to its Categorical Side. Studies in Logic and the Foundations of Mathematics. vol. 152. Elsevier Science (2008)"},{"issue":"3","key":"10_CR31","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1017\/S0022481200029649","volume":"52","author":"RA Di Paola","year":"1987","unstructured":"Di Paola, R.A., Heller, A.: Dominical categories: recursion theory without elements. J. Symb. Log. 52(3), 594\u2013635 (1987)","journal-title":"J. Symb. Log."},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1017\/S0960129597002296","volume":"7","author":"D Pavlovic","year":"1997","unstructured":"Pavlovic, D.: Categorical logic of names and abstraction in action calculus. Math. Struct. Comput. Sci. 7, 619\u2013637 (1997)","journal-title":"Math. Struct. Comput. Sci."},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Pavlovic, D.: Quantum and classical structures in nondeterministic computation. In: Bruza, P., Sofge, D., van Rijsbergen, K. (eds.) Proceedings of Quantum Interaction 2009. Lecture Notes in Artificial Intelligence, vol. 5494, pp. 143\u2013158. Springer Verlag (2009). arxiv.org:0812.2266","DOI":"10.1007\/978-3-642-00834-4_13"},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"Pavlovic, D.: Gaming security by obscurity. In: Gates, C., Hearley, C. (eds.) Proceedings of NSPW 2011, pp. 125\u2013140. ACM, New York (2011). arxiv:1109.5542","DOI":"10.1145\/2073276.2073289"},{"key":"10_CR35","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1090\/psapm\/071\/607","volume":"71","author":"D Pavlovic","year":"2012","unstructured":"Pavlovic, D.: Geometry of abstraction in quantum computation. Proc. Symp. Appl. Math. 71, 233\u2013267 (2012). arxiv.org:1006.1010","journal-title":"Proc. Symp. Appl. Math."},{"key":"10_CR36","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.ic.2013.03.007","volume":"226","author":"D Pavlovic","year":"2013","unstructured":"Pavlovic, D.: Monoidal computer I: basic computability by string diagrams. Inf. Comput. 226, 94\u2013116 (2013). arxiv:1208.5205","journal-title":"Inf. Comput."},{"key":"10_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-642-54789-8_19","volume-title":"Categories and Types in Logic, Language, and Physics","author":"D Pavlovic","year":"2014","unstructured":"Pavlovic, D.: Chasing diagrams in cryptography. In: Casadio, C., Coecke, B., Moortgat, M., Scott, P. (eds.) Categories and Types in Logic, Language, and Physics. LNCS, vol. 8222, pp. 353\u2013367. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54789-8_19"},{"key":"10_CR38","unstructured":"Pavlovic, D.: Monoidal computer II: Normal complexity by string diagrams. Technical report, ASECOLab (2014). arxiv:1402.5687"},{"key":"10_CR39","unstructured":"Pavlovic, D., Fauser, B.: Smooth coalgebra: testing vector analysis. Math. Struct. Comput. Sci. 26, 1\u201341, 2 (2016). arxiv:1402.4414"},{"key":"10_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/11784180_24","volume-title":"Algebraic Methodology and Software Technology","author":"D Pavlovic","year":"2006","unstructured":"Pavlovic, D., Mislove, M., Worrell, J.B.: Testing semantics: connecting processes and process logics. In: Johnson, M., Vene, V. (eds.) AMAST 2006. LNCS, vol. 4019, pp. 308\u2013322. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11784180_24"},{"key":"10_CR41","unstructured":"Pavlovic, D., Yahia, M.: Basic Concepts of Computer Science (with Pictures), December 2018. Draft textbook; chapters available as lecture notes at http:\/\/www.asecolab.org\/courses\/ics-222\/"},{"key":"10_CR42","doi-asserted-by":"crossref","unstructured":"Pavlovi\u0107, D., Escard\u00f3, M.: Calculus in coinductive form. In: Pratt, V. (eds.), Proceedings. Thirteenth Annual IEEE Symposium on Logic in Computer Science, pp. 408\u2013417. IEEE Computer Society (1998)","DOI":"10.1109\/LICS.1998.705675"},{"key":"10_CR43","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H Rogers Jr","year":"1987","unstructured":"Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987)"},{"issue":"1","key":"10_CR44","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(00)00056-6","volume":"249","author":"JJMM Rutten","year":"2000","unstructured":"Rutten, J.J.M.M.: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249(1), 3\u201380 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR45","doi-asserted-by":"crossref","unstructured":"Turi, D., Plotkin, G.D.: Towards a mathematical operational semantics. In: Proceedings of the Twelfth Annual IEEE Symposium on Logic in Computer Science (LICS 1997), pp. 280\u2013291. IEEE Computer Society Press, June 1997","DOI":"10.1109\/LICS.1997.614955"},{"key":"10_CR46","first-page":"230","volume":"42","author":"AM Turing","year":"1936","unstructured":"Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. Second Ser. 42, 230\u2013265 (1936)","journal-title":"Proc. Lond. Math. Soc. Second Ser."},{"issue":"641","key":"10_CR47","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1098\/rstb.1952.0012","volume":"237","author":"AM Turing","year":"1952","unstructured":"Turing, A.M.: The chemical basis of morphogenesis. Philos. Trans. R. Soc. Lond. Seri. B, Biol. Sci. B 237(641), 37\u201372 (1952)","journal-title":"Philos. Trans. R. Soc. Lond. Seri. B, Biol. Sci. B"},{"key":"10_CR48","series-title":"Foundations of Computing","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3054.001.0001","volume-title":"The Formal Semantics of Programming Languages: An Introduction","author":"G Winskel","year":"1993","unstructured":"Winskel, G.: The Formal Semantics of Programming Languages: An Introduction. Foundations of Computing. Zone Books, U.S. (1993)"}],"container-title":["Lecture Notes in Computer Science","Coalgebraic Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-00389-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T22:29:26Z","timestamp":1751927366000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-00389-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030003883","9783030003890"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-00389-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"20 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CMCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Coalgebraic Methods in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Thessaloniki","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cmcs2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.coalg.org\/cmcs18\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}