{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T14:11:36Z","timestamp":1787062296573,"version":"build-2736575974"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:00:00Z","timestamp":1767830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2327738"],"award-info":[{"award-number":["2327738"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,1,8]]},"abstract":"<jats:p>\n                    In a dependent type theory with\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mi>\u03b2<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -equivalence as its equational theory, the confluence of untyped reduction and termination immediately give us a proof of the decidability of type conversion, where the decision procedure for convertibility simply checks the equality of the\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mi>\u03b2<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -normal forms of its inputs. This technique is not available in the presence of surjective pairing (i.e. the\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mi>\u03b7<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -law for pairs) because\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mrow>\n                          <mml:mi>\u03b2<\/mml:mi>\n                          <mml:mi>\u03b7<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -reduction is not confluent. In this work, we show that by adopting established syntactic techniques, we can resolve the issue with confluence caused by surjective pairing, and recover a confluence-based proof of decidability of type conversion. Compared to existing proof developments, which rely on semantic tools such as Kripke-style logical relations, our proof modularly composes a minimal semantic proof of untyped normalization and a syntactic proof of decidability. This modularity enables us to explore algorithmic conversion through syntactic methods without modifying the minimal semantic proof. We have fully mechanized our results using the Rocq theorem prover.\n                  <\/jats:p>","DOI":"10.1145\/3776672","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T18:59:43Z","timestamp":1767898783000},"page":"865-894","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithmic Conversion with Surjective Pairing: A Syntactic and Untyped Approach"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8717-2498","authenticated-orcid":false,"given":"Yiyun","family":"Liu","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6756-9168","authenticated-orcid":false,"given":"Stephanie","family":"Weirich","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"e_1_3_2_2_1","volume-title":"Normalization by evaluation: Dependent types and impredicativity. Ph.D. Dissertation","author":"Abel Andreas","year":"2013","unstructured":"Andreas Abel. 2013. Normalization by evaluation: Dependent types and impredicativity. Ph.D. Dissertation. Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen."},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796819000170"},{"issue":"4","key":"e_1_3_2_4_1","first-page":"345","article-title":"Untyped algorithmic equality for Martin-L\u00f6f\u2019s logical framework with surjective pairs","volume":"77","author":"Abel Andreas","year":"2007","unstructured":"Andreas Abel and Thierry Coquand. 2007. Untyped algorithmic equality for Martin-L\u00f6f\u2019s logical framework with surjective pairs. Fundamenta Informaticae 77, 4 (2007), 345\u2013395.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70594-9_4"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158111"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.2168\/lmcs-8(1:29)2012"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005770"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3636501.3636951"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645891.671415"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-89366-2_16"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","unstructured":"Thorsten Altenkirch and Ambrus Kaposi. 2016. Normalisation by Evaluation for Dependent Types. (2016) 16 pages. doi:10.4230\/LIPICS.FSCD.2016.6 Artwork Size: 16 pages Medium: application\/pdf Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Wadern\/Saarbruecken Germany.","DOI":"10.4230\/LIPICS.FSCD.2016.6"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/s0956796800020025"},{"key":"e_1_3_2_14_1","first-page":"117","volume-title":"Lambda Calculi with Types","author":"Barendregt Henk P.","year":"1993","unstructured":"Henk P. Barendregt. 1993. Lambda Calculi with Types. Oxford University Press, Inc., USA, 117\u2013309."},{"key":"e_1_3_2_15_1","volume-title":"Coq en coq. Ph. D. Dissertation","author":"Barras Bruno","year":"1996","unstructured":"Bruno Barras. 1996. Coq en coq. Ph. D. Dissertation. INRIA."},{"key":"e_1_3_2_16_1","volume-title":"Th\u00e8se l\u2019habilitation \u00e0 diriger des recherches","author":"Barras Bruno","year":"2012","unstructured":"Bruno Barras. 2012. Semantical investigations in intuitionistic set theory and type theories with inductive families. Th\u00e8se l\u2019habilitation \u00e0 diriger des recherches, Universit\u00e9 Paris 7 - Denis Diderot."},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78499-9_26"},{"key":"e_1_3_2_18_1","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/3-540-49254-2_4","article-title":"Normalization by evaluation","author":"Berger Ulrich","year":"1998","unstructured":"Ulrich Berger, Matthias Eberl, and Helmut Schwichtenberg. 1998. Normalization by evaluation. Prospects for Hardware Foundations: ESPRIT Working Group 8533 NADA\u2014New Hardware Design Methods Survey Chapters (1998), 117\u2013137.","journal-title":"Prospects for Hardware Foundations: ESPRIT Working Group 8533 NADA\u2014New Hardware Design Methods Survey Chapters"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129505004822"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99336-8_15"},{"key":"e_1_3_2_21_1","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1017\/CBO9780511569807.011","article-title":"An algorithm for testing conversion in type theory","volume":"1","author":"Coquand Thierry","year":"1991","unstructured":"Thierry Coquand. 1991. An algorithm for testing conversion in type theory. Logical frameworks 1 (1991), 255\u2013279.","journal-title":"Logical frameworks"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.01.015"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9879-9"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-018-9458-4"},{"key":"e_1_3_2_25_1","volume-title":"Bachelor thesis","author":"Dapprich Adrian","year":"2021","unstructured":"Adrian Dapprich and Andrej Dudenhefner. 2021. Generating Infrastructural Code for Terms with Binders using MetaCoq and OCaml. Bachelor thesis, Saarland University (2021)."},{"key":"e_1_3_2_26_1","first-page":"462","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Di Cosmo Roberto","year":"1994","unstructured":"Roberto Di Cosmo and Delia Kesner. 1994. Combining first order algebraic rewriting systems, recursion and extensional lambda calculi. In International Colloquium on Automata, Languages, and Programming. Springer, 462\u2013472."},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60579-7_2"},{"key":"e_1_3_2_28_1","unstructured":"Jan Herman Geuvers. 1993. Logics and type systems. [Sl: sn]."},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/64805"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31982-5_26"},{"key":"e_1_3_2_31_1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1145\/581478.581501","article-title":"A compiled implementation of strong reduction","author":"Gr\u00e9goire Benjamin","year":"2002","unstructured":"Benjamin Gr\u00e9goire and Xavier Leroy. 2002. A compiled implementation of strong reduction. In Proceedings of the seventh ACM SIGPLAN international conference on Functional programming. 235\u2013246.","journal-title":"Proceedings of the seventh ACM SIGPLAN international conference on Functional programming"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1042038.1042041"},{"key":"e_1_3_2_33_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-1-4471-0963-1_2","article-title":"Syntax and semantics of dependent types","author":"Hofmann Martin","year":"1997","unstructured":"Martin Hofmann and Martin Hofmann. 1997. Syntax and semantics of dependent types. Extensional Constructs in Intensional Type Theory (1997), 13\u201354.","journal-title":"Extensional Constructs in Intensional Type Theory"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796823000060"},{"key":"e_1_3_2_35_1","unstructured":"Junyoung Jang Jason ZS Hu Antoine Gaulin and Brigitte Pientka. 2025. McTT: Building A Correct-By-Construction Proof Checker For Martin-L\u00f6f Type Theory. (2025)."},{"issue":"2","key":"e_1_3_2_36_1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1017\/S0956796800001301","article-title":"The virtues of eta-expansion","volume":"5","author":"Barry Jay C","year":"1995","unstructured":"C Barry Jay and Neil Ghani. 1995. The virtues of eta-expansion. Journal of functional programming 5, 2 (1995), 135\u2013154.","journal-title":"Journal of functional programming"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-002-0156-9"},{"key":"e_1_3_2_38_1","volume-title":"Combinatory Reduction Systems","author":"Klop Jan Willem","year":"1980","unstructured":"Jan Willem Klop. 1980. Combinatory Reduction Systems. Mathematisch centrum, Amsterdam."},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90014-X"},{"key":"e_1_3_2_40_1","first-page":"175","article-title":"Eta-Equivalence in Core Dependent Haskell","author":"Kravchuk-Kirilyuk Anastasiya","year":"2020","unstructured":"Anastasiya Kravchuk-Kirilyuk, Antoine Voizard, and Stephanie Weirich. 2020. Eta-Equivalence in Core Dependent Haskell. Leibniz international proceedings in informatics 175 (2020).","journal-title":"Leibniz international proceedings in informatics"},{"key":"e_1_3_2_41_1","unstructured":"Meven Lennon-Bertrand. 2022. \u00c0 bas l\u2019\u03b7\u2014Coq\u2019s troublesome \u03b7-conversion. The first Workshop on the Implementation of Type Systems (WITS). https:\/\/www.meven.ac\/documents\/22-WITS-abstract.pdf."},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSCD.2025.27"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632886"},{"key":"e_1_3_2_44_1","unstructured":"Yiyun Liu Jonathan Chan and Stephanie Weirich. 2024a. Functional Pearl: Short and Mechanized Logical Relation for Dependent Type Theories. (2024)."},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3704843"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","unstructured":"Yiyun Liu and Stephanie Weirich. 2025. Artifact associated with \u201cAlgorithmic Conversion with Surjective Pairing: A Syntactic and Untyped Approach\u201d. doi:10.5281\/zenodo.17343517","DOI":"10.5281\/zenodo.17343517"},{"key":"e_1_3_2_47_1","volume-title":"An extended calculus of constructions. Ph. D. Dissertation","author":"Luo Zhaohui","year":"1990","unstructured":"Zhaohui Luo. 1990. An extended calculus of constructions. Ph. D. Dissertation. University of Edinburgh."},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45413-6_27"},{"key":"e_1_3_2_49_1","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/3-540-39185-1_14","volume-title":"Types for Proofs and Programs","author":"Miquel Alexandre","year":"2003","unstructured":"Alexandre Miquel and Benjamin Werner. 2003. The Not So Simple Proof-Irrelevant Model of CC. In Types for Proofs and Programs, Herman Geuvers and Freek Wiedijk (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 240\u2013258."},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796812000044"},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3706056"},{"key":"e_1_3_2_52_1","first-page":"1","volume-title":"2021 36th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)","author":"Sterling Jonathan","year":"2021","unstructured":"Jonathan Sterling and Carlo Angiuli. 2021. Normalization for cubical type theory. In 2021 36th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 1\u201315."},{"key":"e_1_3_2_53_1","first-page":"2","article-title":"Extending the extensional lambda calculus with surjective pairing is conservative","author":"St\u00f8vring Kristian","year":"2006","unstructured":"Kristian St\u00f8vring. 2006. Extending the extensional lambda calculus with surjective pairing is conservative. Logical Methods in Computer Science 2 (2006).","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_2_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1057"},{"key":"e_1_3_2_55_1","doi-asserted-by":"publisher","unstructured":"The Rocq Development Team. 2025. The Rocq Prover. doi:10.5281\/zenodo.15149629","DOI":"10.5281\/zenodo.15149629"},{"key":"e_1_3_2_56_1","first-page":"30","author":"Timany Amin","year":"2017","unstructured":"Amin Timany and Matthieu Sozeau. 2017. Consistency of the Predicative Calculus of Cumulative Inductive Constructions (pCuIC). Research Report RR-9105. KU Leuven, Belgium ; Inria Paris. 30 pages. https:\/\/inria.hal.science\/hal-01615123","journal-title":"Consistency of the Predicative Calculus of Cumulative Inductive Constructions (pCuIC). Research Report RR-9105"},{"key":"e_1_3_2_57_1","unstructured":"Femke Van Raamsdonk and PG Severi. 1995. On normalisation. (1995)."},{"key":"e_1_3_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110275"},{"key":"e_1_3_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3167091"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776672","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T13:42:50Z","timestamp":1784209370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":58,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2026,1,8]]}},"alternative-id":["10.1145\/3776672"],"URL":"https:\/\/doi.org\/10.1145\/3776672","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-07-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}