Dale Miller
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Dale Miller has a total of 32 co-authors. Here are the top co-authors by number of shared publications:
- Gopalan Nadathur
University of Minnesota, Minneapolis, Minnesota, USA
15 shared publications - Kaustuv Chaudhuri
Inria & LIX, Institut Polytechnique Paris
5 shared publications - Alwen Tiu
Australian National University
3 shared publications Quentin Heath
Inria-Saclay, LIX/Ecole Polytechnique, and CNRS UMR 7161
3 shared publicationsAlwen Tiu
Australian National University and NICTA
2 shared publications- Arunava Gantait
Inria & LIX, Institut Polytechnique Paris
2 shared publications
Latest Publications
- Open Access
- 24 July 2026
- Published by Springer Nature
- p. 73-90
Automating Proof Search when Equality is a Logical Connective
Treating syntactic equality as a logical connective—governed by left- and right-introduction rules within the sequent calculus—offers an elegant and powerful approach to term identity. This treatment of equality allows for the derivation of core mathematical principles, such as Peano’s axioms (excluding induction), and serves as a foundation for the Abella interactive proof assistant. However, integrating this equality into automated proof search remains challenging. We present a proof search procedure that extends unification to handle the complexities of quantifier alternation and equations that occur in both positive and negative occurrences. While established logical frameworks such as $$\lambda $$ Prolog and LF lack direct support for this kind of equality, our procedure enables a lightweight logical framework that addresses this gap. Our system enables unification-aware proof search across a diverse range of first-order sequent calculi that can directly use this form of equality.- 24 July 2026
- Published by Springer Nature
- p. 73-90
Open AccessAutomating Proof Search when Equality is a Logical Connective
Treating syntactic equality as a logical connective—governed by left- and right-introduction rules within the sequent calculus—offers an elegant and powerful approach to term identity. This treatment of equality allows for the derivation of core mathematical principles, such as Peano’s axioms (excluding induction), and serves as a foundation for the Abella interactive proof assistant. However, integrating this equality into automated proof search remains challenging. We present a proof search procedure that extends unification to handle the complexities of quantifier alternation and equations that occur in both positive and negative occurrences. While established logical frameworks such as $$\lambda $$ Prolog and LF lack direct support for this kind of equality, our procedure enables a lightweight logical framework that addresses this gap. Our system enables unification-aware proof search across a diverse range of first-order sequent calculi that can directly use this form of equality. - Open Access
- 25 September 2025
- Published by Springer Nature
- p. 299-317
Designing a Safe Forward Chaining Tactic Using Productive Proofs
We present a proof-theoretic treatment of forward chaining and saturation within a multisorted, first-order intuitionistic logic with equality. The notions of polarity and focused proofs are central to our approach since they provide a characterization of geometric implications as bipolar formulas as well as a natural setting to describe forward chaining and the concept of productive proofs. We identify conditions under which forward chaining with a given set of formulas is guaranteed to saturate in a finite number of steps. The motivation for this research stems, in part, from exploring avenues to automate the Abella theorem prover, which relies on relational specifications, and where theorems in typical proof developments are essentially bipolar formulas. We illustrate the potential benefits of automating forward chaining and saturation for Abella by presenting examples that compute congruence closure and assist in other equational and relational reasoning tasks.
- 25 September 2025
- Published by Springer Nature
- p. 299-317
Open AccessDesigning a Safe Forward Chaining Tactic Using Productive Proofs
We present a proof-theoretic treatment of forward chaining and saturation within a multisorted, first-order intuitionistic logic with equality. The notions of polarity and focused proofs are central to our approach since they provide a characterization of geometric implications as bipolar formulas as well as a natural setting to describe forward chaining and the concept of productive proofs. We identify conditions under which forward chaining with a given set of formulas is guaranteed to saturate in a finite number of steps. The motivation for this research stems, in part, from exploring avenues to automate the Abella theorem prover, which relies on relational specifications, and where theorems in typical proof developments are essentially bipolar formulas. We illustrate the potential benefits of automating forward chaining and saturation for Abella by presenting examples that compute congruence closure and assist in other equational and relational reasoning tasks.
- Open Access
- 21 November 2024
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 24 (6) , 1123-1162
Property-Based Testing by Elaborating Proof Outlines
Property-based testing (PBT) is a technique for validating code against an executable specification by automatically generating test-data. We present a proof-theoretical reconstruction of this style of testing for relational specifications and employ the Foundational Proof Certificate framework to describe test generators. We do this by encoding certain kinds of “proof outlines” as proof certificates that can describe various common generation strategies in the PBT literature, ranging from random to exhaustive, including their combination. We also address the shrinking of counterexamples as a first step toward their explanation. Once generation is accomplished, the testing phase is a standard logic programing search. After illustrating our techniques on simple, first-order (algebraic) data structures, we lift it to data structures containing bindings by using the $\lambda$ -tree syntax approach to encode bindings. The $\lambda$ Prolog programing language can perform both generating and checking of tests using this approach to syntax. We then further extend PBT to specifications in a fragment of linear logic.- 21 November 2024
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 24 (6) , 1123-1162
Open AccessProperty-Based Testing by Elaborating Proof Outlines
Property-based testing (PBT) is a technique for validating code against an executable specification by automatically generating test-data. We present a proof-theoretical reconstruction of this style of testing for relational specifications and employ the Foundational Proof Certificate framework to describe test generators. We do this by encoding certain kinds of “proof outlines” as proof certificates that can describe various common generation strategies in the PBT literature, ranging from random to exhaustive, including their combination. We also address the shrinking of counterexamples as a first step toward their explanation. Once generation is accomplished, the testing phase is a standard logic programing search. After illustrating our techniques on simple, first-order (algebraic) data structures, we lift it to data structures containing bindings by using the $\lambda$ -tree syntax approach to encode bindings. The $\lambda$ Prolog programing language can perform both generating and checking of tests using this approach to syntax. We then further extend PBT to specifications in a fragment of linear logic. - 4 September 2024
- Published by Springer Nature
- p. 162-183
About Trust and Proof: An Experimental Framework for Heterogeneous Verification
- 4 September 2024
- Published by Springer Nature
- p. 162-183
About Trust and Proof: An Experimental Framework for Heterogeneous Verification
- Open Access
- 13 February 2024
- Published by Springer Nature
- p. 275-313
Focusing Gentzen’s LK Proof System
- 13 February 2024
- Published by Springer Nature
- p. 275-313
Open AccessFocusing Gentzen’s LK Proof System
- Open Access
- 13 September 2023
- Published by Springer Nature
- p. 176-194
Formal Reasoning Using Distributed Assertions
When a proof system checks a formal proof, we can say that its kernel asserts that the formula is a theorem in a particular logic. We describe a general framework in which such assertions can be made globally available so that any other proof assistant willing to trust the assertion’s creator can use that assertion without rechecking any associated formal proof. This framework, called DAMF, is heterogeneous and allows each participant to decide which tools and operators they are willing to trust in order to accept external assertions. This framework can also be integrated into existing proof systems by making minor changes to the input and output subsystems of the prover. DAMF achieves a high level of distributivity using such off-the-shelf technologies as IPFS, IPLD, and public key cryptography. We illustrate the framework by describing an implemented tool for validating and publishing assertion objects and a modified version of the Abella theorem prover that can use and publish such assertions.
- 13 September 2023
- Published by Springer Nature
- p. 176-194
Open AccessFormal Reasoning Using Distributed Assertions
When a proof system checks a formal proof, we can say that its kernel asserts that the formula is a theorem in a particular logic. We describe a general framework in which such assertions can be made globally available so that any other proof assistant willing to trust the assertion’s creator can use that assertion without rechecking any associated formal proof. This framework, called DAMF, is heterogeneous and allows each participant to decide which tools and operators they are willing to trust in order to accept external assertions. This framework can also be integrated into existing proof systems by making minor changes to the input and output subsystems of the prover. DAMF achieves a high level of distributivity using such off-the-shelf technologies as IPFS, IPLD, and public key cryptography. We illustrate the framework by describing an implemented tool for validating and publishing assertion objects and a modified version of the Abella theorem prover that can use and publish such assertions.
- Open Access
- 26 June 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-11
A system of inference based on proof search: an extended abstract
Gentzen designed his natural deduction proof system to "come as close as possible to actual reasoning." Indeed, natural deduction proofs closely resemble the static structure of logical reasoning in mathematical arguments. However, different features of inference are compelling to capture when one wants to support the process of searching for proofs. PSF (Proof Search Framework) attempts to capture these features naturally and directly. The design and metatheory of PSF are presented, and its ability to specify a range of proof systems for classical, intuitionistic, and linear logic is illustrated.
- 26 June 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-11
Open AccessA system of inference based on proof search: an extended abstract
Gentzen designed his natural deduction proof system to "come as close as possible to actual reasoning." Indeed, natural deduction proofs closely resemble the static structure of logical reasoning in mathematical arguments. However, different features of inference are compelling to capture when one wants to support the process of searching for proofs. PSF (Proof Search Framework) attempts to capture these features naturally and directly. The design and metatheory of PSF are presented, and its ability to specify a range of proof systems for classical, intuitionistic, and linear logic is illustrated.
- 1 July 2022
- Published by Project MUSE in Journal of the History of Philosophy
- Vol. 60 (3) , 453-473
“We May Stand Aloof”: Mill’s Natural Penalties
In On Liberty, J. S. Mill says that even though individuals should not be punished for their character traits and actions when these do not harm anyone else, people who disapprove of an individual’s “self-regarding” traits and actions may still respond to that individual in various ways that reflect their disapproval and that the individual does not welcome. He calls these permissible disapproving responses “natural penalties.” Despite some recent work on the topic, Mill’s treatment of the natural penalties remains understudied. I propose an account of how he distinguishes between these penalties and punishments and elucidate several other aspects of his treatment. I also consider whether Mill should have disallowed the natural penalties.
- 1 July 2022
- Published by Project MUSE in Journal of the History of Philosophy
- Vol. 60 (3) , 453-473
“We May Stand Aloof”: Mill’s Natural Penalties
In On Liberty, J. S. Mill says that even though individuals should not be punished for their character traits and actions when these do not harm anyone else, people who disapprove of an individual’s “self-regarding” traits and actions may still respond to that individual in various ways that reflect their disapproval and that the individual does not welcome. He calls these permissible disapproving responses “natural penalties.” Despite some recent work on the topic, Mill’s treatment of the natural penalties remains understudied. I propose an account of how he distinguishes between these penalties and punishments and elucidate several other aspects of his treatment. I also consider whether Mill should have disallowed the natural penalties.
- 18 November 2021
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 22 (6) , 859-904
A Survey of the Proof-Theoretic Foundations of Logic Programming
Several formal systems, such as resolution and minimal model semantics, provide a framework for logic programming. In this article, we will survey the use ofstructural proof theoryas an alternative foundation. Researchers have been using this foundation for the past 35 years to elevate logic programming from its roots in first-order classical logic into higher-order versions of intuitionistic and linear logic. These more expressive logic programming languages allow for capturing stateful computations and rich forms of abstractions, including higher-order programming, modularity, and abstract data types. Term-level bindings are another kind of abstraction, and these are given an elegant and direct treatment within both proof theory and these extended logic programming languages. Logic programming has also inspired new results in proof theory, such as those involving polarity and focused proofs. These recent results provide a high-level means for presenting the differences between forward-chaining and backward-chaining style inferences. Anchoring logic programming in proof theory has also helped identify its connections and differences with functional programming, deductive databases, and model checking.
- 18 November 2021
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 22 (6) , 859-904
A Survey of the Proof-Theoretic Foundations of Logic Programming
Several formal systems, such as resolution and minimal model semantics, provide a framework for logic programming. In this article, we will survey the use ofstructural proof theoryas an alternative foundation. Researchers have been using this foundation for the past 35 years to elevate logic programming from its roots in first-order classical logic into higher-order versions of intuitionistic and linear logic. These more expressive logic programming languages allow for capturing stateful computations and rich forms of abstractions, including higher-order programming, modularity, and abstract data types. Term-level bindings are another kind of abstraction, and these are given an elegant and direct treatment within both proof theory and these extended logic programming languages. Logic programming has also inspired new results in proof theory, such as those involving polarity and focused proofs. These recent results provide a high-level means for presenting the differences between forward-chaining and backward-chaining style inferences. Anchoring logic programming in proof theory has also helped identify its connections and differences with functional programming, deductive databases, and model checking.
- Open Access
- 30 September 2021
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 90 (5) , 455-479
Functions-as-constructors higher-order unification: extended pattern unification
Unification is a central operation in constructing a range of computational logic systems based on first-order and higher-order logics. First-order unification has several properties that guide its incorporation in such systems. In particular, first-order unification is decidable, unary, and can be performed on untyped term structures. None of these three properties hold for full higher-order unification: unification is undecidable, unifiers can be incomparable, and term-level typing can dominate the search for unifiers. The so-calledpatternsubset of higher-order unification was designed to be a small extension to first-order unification that respects the laws governingλ-binding (i.e., the equalities forα,β, andη-conversion) but which also satisfied those three properties. While the pattern fragment of higher-order unification has been used in numerous implemented systems and in various theoretical settings, it is too weak for many applications. This paper defines an extension of pattern unification that should make it more generally applicable, especially in proof assistants that allow for higher-order functions. This extension’s main idea is that the arguments to a higher-order, free variable can be more than just distinct bound variables. In particular, such arguments can be terms constructed from (sufficient numbers of) such bound variables using term constructors and where no argument is a subterm of any other argument. We show that this extension to pattern unification satisfies the three properties mentioned above.
- 30 September 2021
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 90 (5) , 455-479
Open AccessFunctions-as-constructors higher-order unification: extended pattern unification
Unification is a central operation in constructing a range of computational logic systems based on first-order and higher-order logics. First-order unification has several properties that guide its incorporation in such systems. In particular, first-order unification is decidable, unary, and can be performed on untyped term structures. None of these three properties hold for full higher-order unification: unification is undecidable, unifiers can be incomparable, and term-level typing can dominate the search for unifiers. The so-calledpatternsubset of higher-order unification was designed to be a small extension to first-order unification that respects the laws governingλ-binding (i.e., the equalities forα,β, andη-conversion) but which also satisfied those three properties. While the pattern fragment of higher-order unification has been used in numerous implemented systems and in various theoretical settings, it is too weak for many applications. This paper defines an extension of pattern unification that should make it more generally applicable, especially in proof assistants that allow for higher-order functions. This extension’s main idea is that the arguments to a higher-order, free variable can be more than just distinct bound variables. In particular, such arguments can be terms constructed from (sufficient numbers of) such bound variables using term constructors and where no argument is a subterm of any other argument. We show that this extension to pattern unification satisfies the three properties mentioned above.