Просмотр кода страницы 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>\alpha</math> that the following properties hold:

(1) <math>X_\alpha= \{x\}</math>,

(2) <math>\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.