{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T23:09:39Z","timestamp":1719875379955},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":5945,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1997,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A Partial Combinatory Algebra is <jats:italic>completable<\/jats:italic> if it can be extended to a total one. In [1] it is asked (question 11, posed by D. Scott, H. Barendregt, and G. Mitschke) if every PCA can be completed. A negative answer to this question was given by Klop in [12, 11]; moreover he provided a sufficient condition for completability of a PCA (<jats:italic>M<\/jats:italic>, \u2022, <jats:italic>K,S<\/jats:italic>) in the form of ten axioms (inequalities) on terms of <jats:italic>M<\/jats:italic>. We prove that just one of these axiom (the so called Barendregt's axiom) is sufficient to guarantee (a slightly weaker notion of) completability.<\/jats:p>","DOI":"10.2307\/2275638","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T23:03:06Z","timestamp":1146956586000},"page":"1209-1214","source":"Crossref","is-referenced-by-count":2,"title":["A sufficient condition for completability of partial combinatory algebras"],"prefix":"10.1017","volume":"62","author":[{"given":"Andrea","family":"Asperti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Agata","family":"Ciabattoni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S002248120001570X_ref010","article-title":"Introduction to combinators and is\u03bb-calculus","volume":"1","author":"Hindley","year":"1990","journal-title":"London Mathematical Society Student Texts"},{"key":"S002248120001570X_ref009","article-title":"Completing partial combinatory algebras with unique head normal forms","volume":"R9544","author":"Bethke","year":"1995","journal-title":"CWI Internal Report"},{"key":"S002248120001570X_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60164-3_21"},{"key":"S002248120001570X_ref005","volume-title":"The lambda calculus","author":"Barendregt","year":"1984"},{"key":"S002248120001570X_ref001","volume-title":"Bulletin of the EATCS","year":"1980"},{"key":"S002248120001570X_ref008","article-title":"Collapsing partial combinatory algebras","volume":"R9520","author":"Bethke","year":"1995","journal-title":"CWI Internal Report"},{"key":"S002248120001570X_ref004","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029531"},{"key":"S002248120001570X_ref007","first-page":"819","volume":"52","author":"Bethke","year":"1987","journal-title":"On the existence of extensional partial combinatory algebras"},{"key":"S002248120001570X_ref012","first-page":"472","article-title":"Extending partial combinatory algebras","volume":"16","author":"Klop","year":"1982","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"S002248120001570X_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68952-9"},{"key":"S002248120001570X_ref011","unstructured":"Klop J. W. , personal communication."},{"key":"S002248120001570X_ref003","volume-title":"Proceedings of the Italian Conference on Theoretical Computer Science, Ravello, Italy","author":"Asperti","year":"1995"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002248120001570X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T19:55:05Z","timestamp":1557604505000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S002248120001570X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,12]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,12]]}},"alternative-id":["S002248120001570X"],"URL":"https:\/\/doi.org\/10.2307\/2275638","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,12]]}}}