Algorithmic synthesis

L. K. E. Achenie and L. T. Biegler. Algorithmic synthesis of chemical reactor networks using mathematical programming. Ind. Eng. Chem. Fundam., 25 621, 1986. 

Achenie. L. E. K.. and Biegler. L. T. Algorithmic Synthesis of Chemical Reactor Networks Using Mathematical Programming," Ind. Eng. Chem. Fundam. 25, 621 (1986). 

Section 3.2.4, we define the niche of algorithm synthesis from examples within empirical learning from examples, and give pointers to the literature in Section 3.2.5. 

Algorithm Synthesis from Examples as a Niche of Learning... 

But algorithm synthesis from examples is a highly specialized niche within empirical learning from examples. Table 3-1 summarizes the differences between the concerns of algorithm synthesis (as we view it) and the mainstream concerns (so far) of empirical learning. 

Table 3-1 Algorithm synthesis from examples as a niche of learning...

Traces are however a very tedious and error-prone specification formalism. Worse, traces oblige the specifier to already know the desired algorithm, which often goes counter the setting of algorithm synthesis. All this somewhat discredits synthesis from traces as an approach to automatic programming, but see below. 

In Section 3.2.4, we have defined algorithm synthesis from examples as a niche of empirical learning from examples. As a reminder, for algorithm synthesis, we are here only interested in the setting with human specifiers who know (even if only informally) the intended relation, and who are assumed to choose only examples that are consistent with the intended relation. Moreover, the intended relation is assumed to have a recursive algorithm. There is a general consensus that a synthesizer from examples would be a useful component of any larger synthesis system. So we now draw some conclusions about the approaches surveyed in the previous two sections. 

The objective of this book is (semi-)automatic logic algorithm synthesis. First, in Section 5.1, we define this objective in more detail and clearly state its boundaries. In order to motivate this research, we develop a series of sample problems in Section 5.2 and show that non-trivial issues have to be solved. This allows us to identify, in Section 5.3, the challenges of logic algorithm synthesis. 

The first building block is the actual specification formalism used to elaborate the input to algorithm synthesis. An arbitrary choice has been made here to investigate synthesis from incomplete specifications. Starting from the pros and cons of specifications by examples, and of specifications by axioms, as outlined in Part I, we define, in Section 6.1, a specification approach that is based on examples and properties. Then, in Section 6.2, we illustrate this approach on a few sample problems. Future work and related work are discussed in Section 6.3 and Section 6.4, respectively, before drawing some conclusions in Section 6.5. 

---