{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T16:30:18Z","timestamp":1673973018279},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2017,1,17]],"date-time":"2017-01-17T00:00:00Z","timestamp":1484611200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,6,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this article we define pure intuitionistic Ancestral Logic ( iAL ), extending pure intuitionistic First-Order Logic ( iFOL ). This logic is a dependently typed abstract programming language with computational functionality beyond iFOL given by its realizer for the transitive closure, TC . We derive this operator from the natural type theoretic definition of TC using intersection. We show that provable formulas in iAL are uniformly realizable, thus iAL is sound with respect to constructive type theory. We further show that iAL subsumes Kleene Algebras with tests and thus serves as a natural programming logic for proving properties of program schemes. We also extract schemes from proofs that iAL specifications are solvable.<\/jats:p>","DOI":"10.1093\/logcom\/exv073","type":"journal-article","created":{"date-parts":[[2015,10,11]],"date-time":"2015-10-11T01:19:56Z","timestamp":1444526396000},"page":"469-486","source":"Crossref","is-referenced-by-count":2,"title":["Intuitionistic ancestral logic"],"prefix":"10.1093","volume":"29","author":[{"given":"Liron","family":"Cohen","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert L","family":"Constable","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY 14850, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,7,8]]},"reference":[{"key":"2019070814353911200_B1","first-page":"55","article-title":"The type theoretic interpretation of constructive set theory","volume-title":"Logic Colloquium '77, Vol. 96 of Studies in Logic and the Foundations of Mathematics","author":"Aczel","year":"1978"},{"key":"2019070814353911200_B2","first-page":"17","article-title":"The type theoretic interpretation of constructive set theory: inductive definition","volume-title":"Logic, Methodology and Philosophy of Science VII","author":"Aczel","year":"1986"},{"key":"2019070814353911200_B3","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1016\/j.jal.2005.10.005","article-title":"Innovations in computational type theory using nuprl","volume":"4","author":"Allen","year":"2006","journal-title":"Journal of Applied Logic"},{"key":"2019070814353911200_B4","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/978-94-017-0253-9_7","article-title":"Transitive closure and the mechanization of mathematics","volume-title":"Thirty Five Years of Automating Mathematics","author":"Avron","year":"2003"},{"key":"2019070814353911200_B5","first-page":"29","article-title":"Sets in coq, coq in sets","volume":"3","author":"Barras","year":"2010","journal-title":"Journal of Formalized Reasoning"},{"key":"2019070814353911200_B6","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1145\/2363.2528","article-title":"Proofs as programs","volume":"7","author":"Bates","year":"1985","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"2019070814353911200_B7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07964-5","volume-title":"Interactive Theorem Proving and Program Development: Coq'Art: the Calculus of Inductive Constructions","author":"Bertot","year":"2004"},{"key":"2019070814353911200_B8","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/978-3-642-03359-9_6","article-title":"A brief overview of agda\u2013a functional language with dependent types","volume-title":"Theorem Proving in Higher Order Logics","author":"Bove","year":"2009"},{"key":"2019070814353911200_B9","first-page":"93","article-title":"A verified compiler for an impure functional language","volume-title":"POPL","author":"Chlipala","year":"2010"},{"key":"2019070814353911200_B10","first-page":"137","article-title":"Ancestral logic: a proof theoretical study","volume-title":"Logic, Language, Information, and Computation, Vol. 8652 of Lecture Notes in Computer Science","author":"Cohen","year":"2014"},{"key":"2019070814353911200_B11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0304-0208(08)73073-1","article-title":"Constructive mathematics as a programming logic I: some principles of theory","volume":"102","author":"Constable","year":"1985","journal-title":"North-Holland Mathematics Studies"},{"key":"2019070814353911200_B12","volume-title":"Implementing Mathematics with the Nuprl proof development System","author":"Constable","year":"1986"},{"key":"2019070814353911200_B13","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.apal.2013.07.009","article-title":"Intuitionistic completeness of first-order logic","volume":"165","author":"Constable","year":"2014","journal-title":"Annals of Pure and Applied Logic"},{"key":"2019070814353911200_B14"},{"key":"2019070814353911200_B15","doi-asserted-by":"crossref","first-page":"315","DOI":"10.2307\/2272068","article-title":"The consistency of classical set theory relative to a set theory with intuitionistic logic","volume":"38","author":"Friedman","year":"1973","journal-title":"The Journal of Symbolic Logic"},{"key":"2019070814353911200_B16","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-09724-4","volume-title":"Edinburgh LCF: A Mechanized Logic of Computation","author":"Gordon","year":"1979"},{"key":"2019070814353911200_B17"},{"key":"2019070814353911200_B18","doi-asserted-by":"crossref","first-page":"213","DOI":"10.2307\/2687775","article-title":"On the unusual effectiveness of logic in computer science","volume":"7","author":"Halpern","year":"2001","journal-title":"Bulletin of Symbolic Logic"},{"key":"2019070814353911200_B19","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1145\/138027.138060","article-title":"A framework for defining logics","volume":"40","author":"Harper","year":"1993","journal-title":"Journal of the ACM (JACM)"},{"key":"2019070814353911200_B20"},{"key":"2019070814353911200_B21","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","article-title":"Languages that capture complexity classes","volume":"16","author":"Immerman","year":"1987","journal-title":"SIAM Journal on Computing"},{"key":"2019070814353911200_B22","volume-title":"Representation of Events in Nerve Nets and Finite Automata","author":"Kleene","year":"1951"},{"key":"2019070814353911200_B23"},{"key":"2019070814353911200_B24"},{"key":"2019070814353911200_B25","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/978-3-662-43951-7_24","article-title":"Kleene algebra with equations","volume-title":"Automata, Languages, and Programming","author":"Kozen","year":"2014"},{"key":"2019070814353911200_B26","first-page":"42","volume-title":"Formal certification of a compiler back-end or: programming a compiler with a proof assistant","author":"Leroy","year":"2006"},{"key":"2019070814353911200_B27","first-page":"99","article-title":"Simulating reachability using first-order logic with applications to verification of linked data structures","volume-title":"Automated Deduction\u2013CADE-20, vol. 3632 of Lecture Notes in Computer Science","author":"Lev-Ami","year":"2005"},{"key":"2019070814353911200_B28","volume-title":"Mathematical Theory of Computation","author":"Manna","year":"1974"},{"key":"2019070814353911200_B29","volume-title":"The Logical Basis for Computer Programming","author":"Manna","year":"1985"},{"key":"2019070814353911200_B30","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0049-237X(09)70189-2","article-title":"Constructive mathematics and computer programming","volume":"104","author":"Martin-L\u00f6f","year":"1982","journal-title":"Studies in Logic and the Foundations of Mathematics"},{"key":"2019070814353911200_B31","volume-title":"Intuitionistic Type Theory","author":"Martin-L\u00f6f","year":"1984"},{"key":"2019070814353911200_B32"},{"key":"2019070814353911200_B33","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9452-5","volume-title":"Mathematical Logic","author":"Monk","year":"1976"},{"key":"2019070814353911200_B34","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-45949-9","volume-title":"Isabelle\/HOL: A Proof Assistant for Higher-order Logic","author":"Nipkow","year":"2002"},{"key":"2019070814353911200_B35","volume-title":"Programming in Martin-L\u00f6f's Type Theory: An Introduction","author":"Nordstr\u00f6m","year":"1990"},{"key":"2019070814353911200_B36"},{"key":"2019070814353911200_B37","volume-title":"Lectures on the Curry-Howard Isomoprhism","author":"S\u00f8rensen","year":"2006"},{"key":"2019070814353911200_B38","volume-title":"Constructivism in Mathematics: An Introduction","author":"Troelstra","year":"1988"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/29\/4\/469\/28917410\/exv073.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T19:47:12Z","timestamp":1562615232000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/29\/4\/469\/2917845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,6]]},"references-count":38,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,7,8]]},"published-print":{"date-parts":[[2019,6,6]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exv073","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,8,1]]},"published":{"date-parts":[[2019,6,6]]}}}