Sequencing tree

THE EXECUTION SEQUENCE TREE TCP) (with values added at assignments)... 

There are two possible approaches. In one approach we in effect build the execution sequence tree for P. We start with node (1,0) labelled START. A node (k,r) will be at level r of the new tree-like structure and be labelled with the instruction named by k. Suppose statement k in P is connected by an arrow (with or without a label) to statement p in P and that we have constructed node (k,r) in P to date. If (k,r) has no ancestor of the form (p,r ), r < r, place node (p,r+l) labelled by statement p on the tree, with an arrow from (k,r) to (p,r+l) which contains any label on the arrow from k to p. If there is already an ancestor (p,rT), r < r, of (k,r) on the tree, then do not create (p,r+l) but instead add an arrow from (k,r) back to (p,r ) containing any label also on the arrow from k to p. If P has N statements, this process must terminate in a scheme P with at most N levels. Clearly P is tree-like and is strongly equivalent to P. This transformation is global and structure preserving. In fact P is a strong homomorphic image of P under the homomorphism h taking each (k,r>) back into k. ... 

Statements (l)-(4) are equivalent since we saw before that if a scheme halts for any interpretation, it halts for some finite interpretation. Further, if P halts for any input under any interpretation, (P,I,x) converges for some free interpretation I and we can discover this by building the (possibly infinite) execution sequence tree and seeing whether STOP ever appears. Hence CD—(M-) are partially decidable. 

You may list the addresses of assignment statements executed, the respecifications of the y and what must be the value of T(y ) if the computation is to continue, making allowances for choices (compare our treatment of Example II - 3). Or you may draw a version of the execution sequence tree (as in Example III - 1), recording at each node only important information such as the address of the executed statement and the new values of the y for an assignment or the values tested for a test statement since we always have val(y, j) = f x) for some n, you can save space by recording only n. ... 

Figure 2. Contrasts between the methods and goals of development of a synthesis tree in computer-assisted synthesis and development of a reaction sequence tree in structure elucidation. We denote two applications of reaction sequences A) conversion of known precursors into unknown compounds, a problem encountered in mechanistic studies B) conversion of candidate structures for an unknown into a series of products, usually employed in the general problem of structure elucidation.

III) Expansion of the synthesis tree is controlled by constraints on the reactions which are applied Expansion of the reaction sequence tree in CONGEN is controlled by constraints on structures, i.. , products. 

Differences (II) and (III) are reflections of the fact that synthesis programs use reactions as variables Several reactions from a library of possible reactions may apply to any target We consider reactions as constants A reaction is defined (see Methods) and applied to a list of structures The products at any level are obtained from structures at the preceding level through one or more applications of that reaction. Although many reactions may be applied to a given list of structures, leading to branches in the reaction sequence tree (see Methods) our basic task is the exhaustive exploration or evaluation, not of reactions, but of structural possibilities ... 

Figure 4. Development and pruning of a reaction sequence tree. Candidate structures are 31-39. Interconnecting lines and the size of a structure convey information on the fate of each candidate. Broken lines pointing to small structures mean that the product(s) and its predecessor(s) are invalid and would be removed by constraints. Regular lines mean the product(s) and its associated candidate structure remain after reaction 1 medium lines connect products and associated structures which are viable after reaction 2 and heavy lines indicate the products from the one structure, 38, which survives after all constraints are applied.

Development Indexing and Pruning of the Reaction Sequence Tree ... 

A reaction sequence may be of arbitrary complexity A convenient representation for describing a reaction sequence is a tree structure We illustrate the development and indexing of a reaction sequence tree in Figure 4 We assume for this example that there are nine candidate structures (3 L - i2.) an unknown which is a 1, 1, -cvcloheptane diol, possessing no gem-diol functionality. In the example (Fig 4) we present the results (and their ultimate consequences) of the application of two reactions in a stepwise manner, a single-step oxidation (reaction 1) followed by a dehydration (reaction 2) A third reaction, exhaustive dehydration, is also applied to the set of candidate structures (3 L - 39) ... 

A reaction sequence tree has seve features Branching of the tree occurs whenever more than one reaction is applied to a s... 

It is possible to develop the complete reaction sequence tree by applying a planned series of reactions to the candidate structures before any laboratory work is actually done In real applications, however, the tree would be developed in a stepwise manner by carrying out a reaction in the laboratory, acquiring data on the products and then turning to CONGEN to explore the implications of this information We attempt to illustrate what is a very dynamic process with the static form of Figure 4 ... 

There are several types of constraints which can be applied to structures in the reaction sequence tree One constraint is a minimum to maximum number of products In the laboratory , oxidation (reaction 1) of the unknown structure yielded two structures Applying the oxidation to the set of candidate structures (3J. - 35.) yields two pr... 

---