{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:29:20Z","timestamp":1743024560409,"version":"3.40.3"},"publisher-location":"Cham","reference-count":47,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031643088"},{"type":"electronic","value":"9783031643095"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-64309-5_21","type":"book-chapter","created":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T22:01:49Z","timestamp":1719871309000},"page":"265-276","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computable Structure Theory of\u00a0Partial Combinatory Algebras"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4598-458X","authenticated-orcid":false,"given":"Ekaterina B.","family":"Fokina","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1464-6908","authenticated-orcid":false,"given":"Sebastiaan A.","family":"Terwijn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,2]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Andrews, U., Belin, D., San Mauro, L.: On the structure of computable reducibility on equivalence relations of natural numbers. J. Symb. Log. 88(3), 1038\u201363 (2023)","DOI":"10.1017\/jsl.2022.28"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Ash, C.J.: Isomorphic recursive structures. In: Ershov et al. (eds.), Handbook of Recursive Mathematics, vol. 1, Studies in Logic, vol. 138, pp. 167\u2013181. Elsevier (1998)","DOI":"10.1016\/S0049-237X(98)80004-9"},{"issue":"4","key":"21_CR3","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.2307\/2275638","volume":"64","author":"A Asperti","year":"1997","unstructured":"Asperti, A., Ciabattoni, A.: A sufficient condition for completability of partial combinatory algebras. J. Symb. Log. 64(4), 1209\u20131214 (1997)","journal-title":"J. Symb. Log."},{"key":"21_CR4","unstructured":"Barendregt, H.P.: The lambda calculus. In: Studies in Logic and the Foundations of Mathematics, vol. 103, 2nd edn. North-Holland, Amsterdam (1984)"},{"key":"21_CR5","doi-asserted-by":"publisher","unstructured":"Beeson, M.J.: Foundations of Constructive Mathematics. Springer-Verlag, Berlin, Heidelberg (1985). https:\/\/doi.org\/10.1007\/978-3-642-68952-9","DOI":"10.1007\/978-3-642-68952-9"},{"issue":"3","key":"21_CR6","doi-asserted-by":"publisher","first-page":"529","DOI":"10.2307\/2273443","volume":"48","author":"C Bernardi","year":"1983","unstructured":"Bernardi, C., Sorbi, A.: Classifying positive equivalence relations. J. Symb. Log. 48(3), 529\u2013538 (1983)","journal-title":"J. Symb. Log."},{"key":"21_CR7","unstructured":"Bethke, I.: Notes on Partial Combinatory Algebras, PhD thesis, Universiteit van Amsterdam, 1988"},{"key":"21_CR8","unstructured":"Bethke, I., Klop, J.W., de Vrijer, R.: Completing partial combinatory algebras with unique head-normal forms, Technical report CS-R9544, Centrum Wiskunde & Informatica (CWI) (1995)"},{"issue":"2","key":"21_CR9","doi-asserted-by":"publisher","first-page":"207","DOI":"10.2307\/1970103","volume":"70","author":"WW Boone","year":"1959","unstructured":"Boone, W.W.: The word problem. Ann. Math. 70(2), 207\u2013265 (1959)","journal-title":"Ann. Math."},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/j.apal.2011.01.002","volume":"162","author":"D Cenzer","year":"2011","unstructured":"Cenzer, D., Harizanov, V., Remmel, J.: $$\\Sigma ^0_1$$ and $$\\Pi ^0_1$$ equivalence structures. Ann. Pure Appl. Log. 162, 490\u2013503 (2011)","journal-title":"Ann. Pure Appl. Log."},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s10469-014-9270-0","volume":"53","author":"D Cenzer","year":"2014","unstructured":"Cenzer, D., Harizanov, V., Remmel, J.: Computability-theoretic properties of injection structures. Algebra Log. 53, 39\u201369 (2014)","journal-title":"Algebra Log."},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Delle Rose, V., San Mauro, L., Sorbi, A.: Word problems and ceers. Math. Log. Q. 66(3), 341\u2013354 (2020)","DOI":"10.1002\/malq.202000021"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Delle Rose, V., San Mauro, L., Sorbi, A.: Classifying word problems of finitely generated algebras via computable reducibility. Int. J. Algebra Comput. 33(4), 751\u2013768 (2023)","DOI":"10.1142\/S0218196723500339"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/malq.19730191901","volume":"19","author":"Yu Ershov","year":"1973","unstructured":"Ershov, Yu.: Theorie der Numerierungen I. Z. Math. Logik Grundlag. Math. 19, 289\u2013388 (1973)","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"21_CR15","doi-asserted-by":"publisher","unstructured":"Feferman, S.: A language and axioms for explicit mathematics. In: Crossley, J.N. (ed.) Algebra and Logic. LNM, vol. 450, pp. 87\u2013139. Springer, Berlin, Heidelberg (1975). https:\/\/doi.org\/10.1007\/BFb0062852","DOI":"10.1007\/BFb0062852"},{"issue":"1","key":"21_CR16","doi-asserted-by":"publisher","first-page":"122","DOI":"10.2178\/jsl\/1327068695","volume":"77","author":"E Fokina","year":"2012","unstructured":"Fokina, E., Friedman, S.D., Harizanov, V., Knight, J.F., McCoy, C., Montalb\u00e1n, A.: Isomorphism relations on computable structures. J. Symb. Log. 77(1), 122\u2013132 (2012)","journal-title":"J. Symb. Log."},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Fokina, E., Harizanov, V., Melnikov, A.: Computable model theory. In: Downey, R. (ed.) Turing\u2019s Legacy: Developments from Turing\u2019s Ideas in Logic, Lect. Notes Log., vol. 42, pp. 124\u2013194 (2014)","DOI":"10.1017\/CBO9781107338579.006"},{"issue":"2","key":"21_CR18","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1093\/logcom\/exaa087","volume":"31","author":"E Frittaion","year":"2021","unstructured":"Frittaion, E., Rathjen, M.: Extensional realizability for intuitionistic set theory. J. Log. Comput. 31(2), 630\u2013653 (2021)","journal-title":"J. Log. Comput."},{"key":"21_CR19","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1023\/A:1010521410739","volume":"67","author":"S Gao","year":"2001","unstructured":"Gao, S., Gerdes, P.: Computably enumerable equivalence relations. Stud. Log. 67, 27\u201359 (2001)","journal-title":"Stud. Log."},{"issue":"1","key":"21_CR20","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1215\/00294527-2023-0002","volume":"64","author":"A Golov","year":"2023","unstructured":"Golov, A., Terwijn, S.A.: Embeddings between partial combinatory algebras. Notre Dame J. Form. Log. 64(1), 129\u2013158 (2023)","journal-title":"Notre Dame J. Form. Log."},{"issue":"6","key":"21_CR21","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1023\/A:1021758312697","volume":"41","author":"SS Goncharov","year":"2002","unstructured":"Goncharov, S.S., Knight, J.F.: Computable structure and non-structure theorems. Algebra Log. 41(6), 351\u2013373 (2002)","journal-title":"Algebra Log."},{"issue":"2","key":"21_CR22","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1090\/S0002-9947-1968-0244049-7","volume":"131","author":"J Harrison","year":"1968","unstructured":"Harrison, J.: Recursive pseudo well-orderings. Trans. Am. Math. Soc. 131(2), 526\u2013543 (1968)","journal-title":"Trans. Am. Math. Soc."},{"key":"21_CR23","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1017\/S0305004102006424","volume":"134","author":"PJW Hofstra","year":"2003","unstructured":"Hofstra, P.J.W., van Oosten, J.: Ordered partial combinatory algebras. Math. Proc. Camb. Philos. Soc. 134, 445\u2013463 (2003)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"21_CR24","unstructured":"Kasymov, N.K., Khoussainov, B.M.: Finitely generated enumerable and absolutely locally finite algebras. Vychisl. Sistemy (116, Prikladn, Logika) 162, 3\u201315 (1986)"},{"key":"21_CR25","doi-asserted-by":"publisher","unstructured":"Kechris, A.S.: Classical Descriptive Set Theory. Springer-Verlag, New York (1995). https:\/\/doi.org\/10.1007\/978-1-4612-4190-4","DOI":"10.1007\/978-1-4612-4190-4"},{"issue":"4\u20135","key":"21_CR26","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1142\/S0218196795000227","volume":"5","author":"O Kharlampovich","year":"1995","unstructured":"Kharlampovich, O., Sapir, M.: Algorithmic problems in varieties. Int. J. Algebra Comput. 5(4\u20135), 379\u2013602 (1995)","journal-title":"Int. J. Algebra Comput."},{"key":"21_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-94418-0_1","volume-title":"Sailing Routes in the World of Computation","author":"B Khoussainov","year":"2018","unstructured":"Khoussainov, B.: A journey to computably enumerable structures (tutorial lectures). In: Manea, F., Miller, R.G., Nowotka, D. (eds.) CiE 2018. LNCS, vol. 10936, pp. 1\u201319. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94418-0_1"},{"issue":"3","key":"21_CR28","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1090\/S0002-9947-2013-05898-9","volume":"366","author":"B Khoussainov","year":"2014","unstructured":"Khoussainov, B., Miasnikov, A.: Finitely presented expansions of groups, semigroups. Trans. Am. Math. Soc. 366(3), 1455\u20131474 (2014)","journal-title":"Trans. Am. Math. Soc."},{"key":"21_CR29","unstructured":"Kleene, S.C., Vesley, R.E.: The foundations of intuitionistic mathematics, North-Holland, 1965"},{"key":"21_CR30","unstructured":"Longley, J.: Realizability Toposes and Language Semantics, PhD thesis, University of Edinburgh, 1994"},{"key":"21_CR31","doi-asserted-by":"publisher","unstructured":"Longley, J., Normann, D.: Higher-Order Computability. Springer, Berlin, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47992-6","DOI":"10.1007\/978-3-662-47992-6"},{"issue":"2","key":"21_CR32","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0168-0072(86)90050-3","volume":"32","author":"DC McCarty","year":"1986","unstructured":"McCarty, D.C.: Realizability and recursive set theory. Ann. Pure Appl. Log. 32(2), 153\u2013183 (1986)","journal-title":"Ann. Pure Appl. Log."},{"key":"21_CR33","unstructured":"Moschovakis, Y.N.: Descriptive set theory, North-Holland, 1980"},{"issue":"3","key":"21_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0960129516000335","volume":"28","author":"A Nies","year":"2018","unstructured":"Nies, A., Sorbi, A.: Calibrating word problems of groups via the complexity of equivalence relations. Math. Struct. Comput. Sci. 28(3), 1\u201315 (2018)","journal-title":"Math. Struct. Comput. Sci."},{"key":"21_CR35","first-page":"143","volume":"44","author":"PS Novikov","year":"1955","unstructured":"Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov. 44, 143 (1955)","journal-title":"Trudy Mat. Inst. Steklov."},{"key":"21_CR36","unstructured":"Odifreddi, P.G.: Classical recursion theory, vol.\u00a01. In: Studies in Logic and the Foundations of Mathematics, vol.\u00a0125, North-Holland (1989)"},{"key":"21_CR37","unstructured":"Odifreddi, P.G.: Classical recursion theory, vol. 2. In: Studies in Logic and the Foundations of Mathematics, vol. 143, North-Holland, Amsterdam (1999)"},{"key":"21_CR38","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0168-0072(96)00050-4","volume":"84","author":"J van Oosten","year":"1997","unstructured":"van Oosten, J.: Extensional realizability. Ann. Pure Appl. Log. 84, 317\u2013349 (1997)","journal-title":"Ann. Pure Appl. Log."},{"key":"21_CR39","doi-asserted-by":"crossref","unstructured":"van Oosten, J.: A combinatory algebra for sequential functionals of finite type. In: Cooper, S.B., Truss, J.K. (eds.), Models and Computability, Cambridge University Press, pp. 389\u2013406 (1999)","DOI":"10.1017\/CBO9780511565670.019"},{"key":"21_CR40","unstructured":"van Oosten, J.: Realizability: an introduction to its categorical side. In: Studies in Logic and the Foundations of Mathematics, vol. 152. Elsevier (2008)"},{"key":"21_CR41","doi-asserted-by":"crossref","unstructured":"Sacks, G.E.: Higher recursion theory. Springer-Verlag (1990)","DOI":"10.1007\/978-3-662-12013-2"},{"key":"21_CR42","doi-asserted-by":"crossref","unstructured":"Scott, D.: Lambda calculus and recursion theory (preliminary version). In: Kanger, S. (ed.), Proceedings of the Third Scandinavian Logic Symposium, Studies in Logic and the Foundations of Mathematics, vol. 82, pp. 154\u2013193 (1975)","DOI":"10.1016\/S0049-237X(08)70730-4"},{"key":"21_CR43","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-1-4615-0755-0_14","volume-title":"Computability and Models","author":"V Selivanov","year":"2003","unstructured":"Selivanov, V.: Positive structures. In: Cooper, S.B., Goncharov, S.S. (eds.) Computability and Models, pp. 321\u2013350. Springer, New York (2003). https:\/\/doi.org\/10.1007\/978-1-4615-0755-0_14"},{"issue":"3","key":"21_CR44","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1017\/jsl.2021.50","volume":"86","author":"P Shafer","year":"2021","unstructured":"Shafer, P., Terwijn, S.A.: Ordinal analysis of partial combinatory algebras. J. Symb. Log. 86(3), 1154\u20131188 (2021)","journal-title":"J. Symb. Log."},{"key":"21_CR45","doi-asserted-by":"crossref","unstructured":"Soare, R.I.: Recursively enumerable sets and degrees, Springer-Verlag (1987)","DOI":"10.1007\/978-3-662-02460-7"},{"key":"21_CR46","unstructured":"Troelstra, A.S., van Dalen, D.: Constructivism in mathematics, vol.\u00a02. In: Studies in Logic and the Foundations of Mathematics, vol. 123, North-Holland (1988)"},{"key":"21_CR47","unstructured":"Zoethout, J.: Computability models and realizability toposes, PhD thesis, Utrecht University (2022)"}],"container-title":["Lecture Notes in Computer Science","Twenty Years of Theoretical and Practical Synergies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-64309-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T22:03:54Z","timestamp":1719871434000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-64309-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031643088","9783031643095"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-64309-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"2 July 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}