A note on program specialization. what can syntactical properties of residual programs reveal? arXiv:1209.5407

The paper presents two examples of non-traditional using of pro-gram specialization by Turchin’s supercompilation method. In both cases we are interested in syntactical properties of residual pro-grams produced by supercompilation. In the first example we ap-ply supercompilation to a program encoding a word equation and as a result we obtain a program representing a graph describing the solution set of the word equation. The idea of the second exam-ple belongs to Alexandr V. Korlyukov. He considered an interpreter simulating the dynamic of the well known missionaries-cannibals puzzle. Supercompilation of the interpreter allows us to solve the puzzle. The interpreter may also be seen as an encoding of a non-deterministic protocol