Abstract Incorrectness Separation Logic (ISL) is a proof system that is tailored specifically to resolve problems of under-approximation in programs that manipulate heaps, and it primarily focuses on bug detection. This approach is different from the over-approximation methods that are used in traditional logics such as Hoare Logic or Separation Logic. Although the soundness of ISL has been established, its completeness remains unproven. In this study, we establish relative completeness by leveraging the expressiveness of the weakest postconditions; expressiveness is a factor that is critical to demonstrating relative completeness in Reverse Hoare Logic. In our ISL framework, we allow for infinite disjunctions in disjunctive normal forms, where each clause comprises finite symbolic heaps with existential quantifiers. To compute the weakest postconditions in ISL, we introduce a canonicalization that includes variable aliasing.

ABSTRACT This paper gives a new proof of confluence for Carraro and Guerrieri’s call-by-value lambda calculus λvσ with permutation rules. We adapt the compositional Z theorem to λvσ.

Cyclic proof systems are sequent-calculus style proof systems that allow circular structures representing induction, and they are considered suitable for automated inductive reasoning. However, Kimura et al. have shown that the cyclic proof system for the symbolic heap separation logic does not satisfy the cut-elimination property, one of the most fundamental properties of proof systems. This paper proves that the cyclic proof system for the bunched logic with only nullary inductive predicates does not satisfy the cut-elimination property. It is hard to adapt the existing proof technique chasing contradictory paths in cyclic proofs since the bunched logic contains the structural rules. This paper proposes a new proof technique called proof unrolling. This technique can be adapted to the symbolic heap separation logic, and it shows that the cut-elimination fails even if we restrict the inductive predicates to nullary ones.

We study monadic translations of the call-by-name (cbn) and call-by-value (cbv) fragments of the classical sequent calculus ${\overline{\lambda}\mu\tilde{\mu}}$ due to Curien and Herbelin, and give modular and syntactic proofs of strong normalisation. The target of the translations is a new meta-language for classical logic, named monadic λμ. This language is a monadic reworking of Parigot's λμ-calculus, where the monadic binding is confined to commands, thus integrating the monad with the classical features. Also, its μ-reduction rule is replaced by a rule expressing the interaction between monadic binding and μ-abstraction. Our monadic translations produce very tight simulations of the respective fragments of ${\overline{\lambda}\mu\tilde{\mu}}$ within monadic λμ, with reduction steps of ${\overline{\lambda}\mu\tilde{\mu}}$ being translated in a 1–1 fashion, except for β steps, which require two steps. The monad of monadic λμ can be instantiated to the continuations monad so as to ensure strict simulation of monadic λμ within simply typed λ-calculus with β- and η-reduction. Through strict simulation, the strong normalisation of simply typed λ-calculus is inherited by monadic λμ, and then by cbn and cbv ${\overline{\lambda}\mu\tilde{\mu}}$ , thus reproving strong normalisation in an elementary syntactical way for these fragments of ${\overline{\lambda}\mu\tilde{\mu}}$ , and establishing it for our new calculus. These results extend to second-order logic, with polymorphic λ-calculus as the target, giving new strong normalisation results for classical second-order logic in sequent calculus style. CPS translations of cbn and cbv ${\overline{\lambda}\mu\tilde{\mu}}$ with the strict simulation property are obtained by composing our monadic translations with the continuations-monad instantiation. In an appendix to the paper, we investigate several refinements of the continuations-monad instantiation in order to obtain in a modular way improvements of the CPS translations enjoying extra properties like simulation by cbv β-reduction or reduction of administrative redexes at compile time.

Abstract This paper points out an error of Parigot's proof of strong normalization of second order classical natural deduction by the CPS-translation, discusses erasing-continuation of the CPS-translation, and corrects that proof by using the notion of augmentations.

Our paper [1] contains a serious error. Proposition 4.6 of [1] is actually false and hence our strong normalization proof does not work for the Curry-style λµ-calculus. However, our method still can show that (1) the correction of Proposition 5.4 of [2], and (2) the correction of the proof of strong normalization of Church-style λµ-calculus by CPS-translation. Firstly, our method is still effective for the correction of Proposition 5.4 of [2]. The proposition claims that for any Curry-style λµ-term u, which is not necessarily typable, if u ∗ is strongly normalizable, then u is strongly normalizable too. But its proof does not work, since Proposition 5.1 (i) of [2] is false because of erasing-continuation. Our method proves the similar result for the Curry-style λµ-calculus by Propositions 4.3 and 4.12 of [1]. Proposition. For any Curry-style λµ-term u, if there exists an augmentation u + of u such that u + ∗ is strongly normalizable, then u is strongly normalizable. Secondly, as mentioned in the concluding remarks of [1], our method is effective for the strong normalization proof of the Church-style λµ-calculus, which is called the second-order typed λµcalculus in [2]. The strong normalization of the typed λµ-calculus is proved in [2], but its proof with CPS-translation does not work since Proposition 5.5 of [2] is false because of erasing-continuation.