Martynyuk schemata

Martynyuk schemata --- схемы Мартынюка.

Martynuk schemata do not contain any information about a program except for a control flow graph. An identity relation can be introduced between vertices of the control flow graph. Two Martynuk schemata are regarded as equivalent if they have the same set of so called chains (i.e. paths in the control flow graph from the entry to the exit vertices). The problem of recognition of equivalence is decidable here, since the set of chains of an oriented graph with specified entry and exit vertices is a regular event.

The class of Martynyuk schemata is a proper subclass of large-block schemata. It consists of all such large-block schemata [math]\displaystyle{ \alpha }[/math] that the following properties hold:

(1) [math]\displaystyle{ X_\alpha= \{x\} }[/math],

(2) [math]\displaystyle{ \Omega_\alpha }[/math] is the set of all possible interpretations,

(3) every transformer has two operands: strong input and nonstrong output,

(4) every recognizer has one operand: strong input.