Jul 2026· Electronic Proceedings in Theoretical Computer Science· Vol abs/2607.20188, pp. 239-257· 0 citations· 51 references
Computer Science
TL;DR
This paper presents formal proofs of confluence for beta-reduction and of alpha-commutative relations, and develops a theory of alpha-commutative relations which, in the author's view, entails a clearer presentation and treatment of the problem than in similar developments.
Abstract
In this paper we continue assessing the feasibility of the approach to the mechanization of type theory by using classical syntax and Stoughton's multiple substitutions and report some substantial progress. We present formal proofs of confluence for beta-reduction and by using Takahashi's revision of Tait and Martin-L\"of's proof, subject reduction for the entire family of the Pure Type Systems and consistency for some impredicative subclass, assuming normalization. As to the proof of confluence, we also develop a theory of alpha-commutative relations which, in our view, entails a clearer presentation and treatment of the problem than in similar developments. Finally, we assess general merits and drawbacks of the approach. The whole development has been machine-checked using Agda.
A proof checker called Nörgler is introduced that builds upon and extends the established approach pioneered by GDV and supports checking propositional, (untyped and typed) first-order, and higher-order refutations represented in TSTP.
Melanie Taprogge, H. Sariyanto, Alexander Steen· 1 citation
This paper provides a setting in which congruences can be treated as actual equalities, mirroring the informal practice of mathematicians and eliminating the need to use the lemmas typically required for formal congruence proofs.
Dale A. Miller· International Conference on...· 0 citations
A translation from a fragment of DTT to polymorphic DHOL is introduced, preserving constructs such as polymorphism and dependent types and suggesting that the translation could be used in a hammer system.
Luca Maio, Alexander, Bentkamp et al.· 0 citations
The top-down solver TD is a generic fixpoint algorithm that can be used to compute partial post-solutions of equation systems for abstract interpretation. We consider two extensions of the TD to deal with infinite strictly ascending chains. For the TD extended with warrowing, we formally prove that it always returns pa...
Sarah Tilscher, Alexandra Graß, Helmut Seidl et al.· Journal of automated reasoni...· 0 citations
A QuickCheck testing method based on generating and shrinking random execution traces based on checking if the first and last terms of a generated trace share the same deterministic normal form that efficiently finds counterexamples and enables fast, robust shrinking.
Koen Claessen· Proc. ACM Program. Lang.· 0 citations
This paper provides an expository comparison of two foundational proof systems in classical propositional logic: Gentzen's sequent calculus and Beth's semantic tableaux. Gentzen's sequent calculus is presented as a rule-based system built upon the single axiom $\alpha \Rightarrow \alpha$, whose key feature — the subfor...
Zuzanna Rygiewicz· Reason· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
