Mechanical Synthesis of Sorting Algorithms for Binary Trees by Logic and Combinatorial Techniques

Isabela Dramnesc (1) , Tudor Jebelean (2) , Sorin Stratulat (3, 4)

1 UVT - Universitatea de Vest din Timișoara [România] = West University of Timișoara [Romania] = Université Ouest de Timișoara [Roumanie]
2 RISC - Research Institute for Symbolic Computation
3 MOSEL - Proof-oriented development of computer-based systems
4 VERIDIS - Modeling and Verification of Distributed Algorithms and Systems

We develop logic and combinatorial methods for automating the generation of sorting algorithms for binary trees, starting from input-output specifications and producing conditional rewrite rules. The main approach consists in proving (constructively) the existence of an appropriate output from every input. The proof may fail if some necessary sub–algorithms are lacking. Then, their specifications are suggested and their synthesis is performed by the same principles. Our main goal is to avoid the possibly prohibitive cost of pure resolution proofs by using a natural–style proving in which domain-specific strategies and inference steps lead to a significant increase of efficiency. In addition to classical techniques for natural–style proving, we introduce novel ones (priority of certain types of assumptions, transformation of elementary goals into conditions, special criteria for decomposition of the goal and of the assumptions), as well as methods based on the properties of domain-specific relations and functions. In particular, we use combinatorial techniques in order to generate possible witnesses, which in certain cases lead to the discovery of new induction principles. From the proof, the algorithm is extracted by transforming inductive proof steps into recursions, and case-based proof steps into conditionals. The approach is demonstrated in parallel using the Theorema system, by developing the theory , implementing the prover, and performing the proofs of the necessary properties and synthesis conjectures. It is also validated in the Coq system, which allows to compare the facilities of the two systems from the point of view of our application.

Mots clés: algorithm synthesis; natural–style proving; automated reasoning

Domaines: Calcul formel [cs.SC]

Isabela Dramnesc, Tudor Jebelean, Sorin Stratulat. Mechanical Synthesis of Sorting Algorithms for Binary Trees by Logic and Combinatorial Techniques. Journal of Symbolic Computation, 2019, 90, pp.3-41. ⟨10.1016/j.jsc.2018.04.002⟩. ⟨hal-01590654⟩