Abstract-In ramen för våra tidigare experiment för bevisbaserad syntes av sorteringsalgoritmer för listor och binära träd, använde vi vissa speciella tekniker som kan generera flera varianter av sortering och sammanslagning, genom att undersöka alla kombinationer av hjälpfunktioner tillgängliga för att komponera objekt (listor, respektive träd). Syftet med detta dokument är att beskriva denna teknik och de resultat som erhållits. Vi presenterar huvudprinciperna och tillämpningen av denna teknik för att slå samman sorterade binära träd till en sorterad. Anmärkningsvärt nog kräver sammanslagning en återvändo i boet, för vilken det är svårt att gissa sig till en lämplig induktionsprincip. Vår metod kan hitta den automatiskt genom att använda en allmän noeterisk induktion och den kombinatoriska tekniken.
Författarna tillämpar i Ref kombinatoriska tekniker för att upptäcka från bevis hjälpalgoritmer, andra än Infoga, som är versioner av en algoritm som slår samman två sorterade binära träd till en sorterad.
Combinatorial Techniques for Proof-Based Synthesis of Sorting Algorithms
{'venue': '2015 17th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)', 'journal': '2015 17th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)', 'mag_field_of_study': ['Computer Science']}