Equivalent transformations

of control systems

Transformations that preserve the equivalence relation of control systems (cf. Control system). They are used in problems of optimization and control, and as a means of characterizing (for example, by axiomatization) specific classes of control systems; a deduction in formal systems can also be regarded as an equivalent transformation of control systems. The equivalence relation is usually taken to be functional equivalence, that is, in this case two control systems are equivalent if they have the same functioning. Sometimes other equivalence relations are considered, in connection with other concepts.

Equivalent transformations of control systems are linked with a large number of problems the concrete formulation of which varies with the specific nature of the given class of control systems. The basic problems of this type are as follows:

1) The construction of finite (or recursive) complete systems of transformation rules. A system of rules of equivalent transformations is said to be complete for a given class of control systems if an arbitrary control system of this class can be transformed into any other equivalent to it by means of finitely many applications of these rules. The solution of this problem depends essentially on the class of control systems and their equivalence relation, as well as on the admissible family of transformations.

The most extensive formulations of this problem are those for which the means of solution are restricted in the following way. The concept of a fragment (or a subscheme) of a control system is defined, and those transformations of the control system are considered that consist in replacing some fragments of this system by others. Thus, a pair $(\alpha,\beta)$ of fragments defines a set of transformations of an arbitrary control system $\gamma$, each consisting in replacing some inclusion of the fragment $\alpha$ of $\gamma$ by the fragment $\beta$ (if $\gamma$ does not contain $\alpha$, then it is assumed that the transformation defined by $(\alpha,\beta)$ leaves $\gamma$ unchanged). A pair $(\alpha,\beta)$ of fragments is said to be a law for the given class of control systems if the transformations defined by it preserve the equivalence relation, that is, if they convert an arbitrary control system from the given class into an equivalent one. Some laws may be equipped with applicability conditions, which describe the situations where they can be applied and guarantee the preservation of the equivalence relation. If a law $(\alpha,\beta)$ is applicable to any inclusion of the fragment $\alpha$ in every control system, then it is called local. The non-local character of a law usually means that its applicability is determined by the structure of the entire control system. The concept of completeness of a system of laws is often defined as follows:

A pair $(\alpha,\beta)$ of fragments is said to be deducible from a system $\Sigma$ of laws if the fragment $\alpha$ can, by means of laws from $\Sigma$, be transformed into the fragment $\beta$. (The application of laws to a fragment is defined just as in the case of a control system.) A system $\Sigma$ of laws is called complete if all pairs of the form $(\alpha,\beta)$, where $\alpha$ and $\beta$ are equivalent control systems, are deducible from it. Usually along with laws, schemes of laws are also considered. These contain certain parameters (free variables). By ascribing a specific value to the parameters, every scheme of laws yields, in general, an infinite set of laws, and the most extensive formulation of the problem consists in requiring one to find a finite complete system of schemes of laws for a given class of control systems.

2) The problem of completeness of systems of transformation laws (both for individual systems and from the algorithmic point of view) is: To determine, relative to the system of laws, whether it is complete or not.

3) The construction of effective procedures that generate equivalence relations. This problem is a weaker version of the first one. The methods of solution here consist of arbitrary algorithms and non-deterministic formally-describable procedures.

4) The construction of optimizing (or, in general, target-aiming) transformation procedures. Most often the problem here is to minimize the complexity of the schemes of control systems or to transform a control system into some canonical form that is unique in the equivalence class. In the latter case the solution of the problem also yields a solution procedure for the equivalence relation. The aim of the transformations can also be the construction of self-correcting or other special control systems. The optimization problem is connected with a whole series of problems of metric character, for example on obtaining estimates of the complexity of the solutions, on parts of optimal control systems, etc.

5) The solution of a problem of the first type, that is, the question of the existence of a finite or recursive complete system of transformation laws for an arbitrary class of control systems from some infinite set of classes. Such a set of classes of control systems may be, for example, the collection of sets of all terms of algebras of the same type, the collection of classes of diagrams of functional elements (cf. Diagram of functional elements) in various bases, etc.

The peculiarities of specific classes of control systems leave their mark on the formulation and method of solution of the problems above. Some examples are considered below.

Equivalent transformations in algebras.

To every algebra of a certain signature corresponds an infinite class of control systems — the set of all terms (formulas) of the given signature (together with the functions defined by them). A natural equivalence relation on the set of terms is that of functional equivalence: Two terms $t_1$ and $t_2$ are equivalent if and only if they define one and the same function up to inessential arguments. The usual notation in this case is $t_1=t_2$ (or $t_1\equiv t_2$), and such expressions are called identities or equalities of the given algebra. Fragments of terms are in this case subterms, that is, those parts that are terms in their own right. Since any substitution of a subterm by a term equivalent to it preserves the equivalence relation, any identity of the algebra (regarded as an unordered pair of terms) is a local law. Any identity of the algebra may also be regarded as a scheme of laws whose parameters are the variables. Consequently, Problem 1 for algebras can be formulated as follows: For a given algebra, to find a finite complete system of identities regarded as schemes or laws. In other words, in this case Problem 1 coincides with the problem of the algebraic axiomatization of algebras.

The existence of a finite complete system of identities is a functional property of algebras, that is, it is fully determined by the class of functions expressible in the given algebra, and does not depend on the signature. Any functionally-complete (finite) algebra has a finite complete system of identities; any two-element algebra has a finite complete system of identities; there are three-element groupoids, finite semi-groups and infinite groups that do not have finite complete systems of identities; any finite group has a finite complete system of identities; for the algebras of all recursive functions, as well as for those of regular events (cf. Regular event), Problem 1 has a negative solution.

Equivalent transformations of diagrams of functional elements.

The concept of a diagram of functional elements may be regarded as a generalization of the concept of a term. The class of diagrams of functional elements in some basis realizes the same set of functions as the algebra with the collection of signature operations corresponding to the given basis. Consequently, the results concerning the problem of equivalent transformations for algebras carry over with minor modifications to diagrams of functional elements. The fragments in this case are subschemes that may differ from diagrams of functional elements only by the presence of several outputs.

Equivalent transformations of contact schemes.

Just as in the case of terms, the concept of a fragment coincides with that of a contact scheme. The only thing required is to sharpen the definition of the set of poles in the input of the fragment in the scheme. Two contact schemes between whose poles there is a one-to-one correspondence are considered to be equivalent if the conductivity function between arbitrary poles of one scheme coincides with the conductivity function between the corresponding poles of the other. If pairs of equivalent contact schemes are regarded as schemes of laws whose parameters are the letters assigned to the edges of the schemes, and if it is assumed that every such scheme generates laws only by renaming these letters, then the class of all contact schemes does not have a finite complete system of schemes of laws. At the same time, for any $n$ the class of all contact schemes whose edges are ascribed at most $n$ distinct letters has a finite complete system of such schemes of laws. If it is assumed that the specific laws are generated from schemes by means of a coordinated replacement of the edges with identical letters by arbitrary contact schemes, then a finite complete system of laws can also be constructed for the class of all contact schemes.

Equivalent transformations of automata.

For finite automata (cf. Automaton, finite) there is no finite complete system of local transformation laws. However, if use is made of non-local laws or of schemes of laws depending on special parameters, then Problem 1 may have a positive solution for them. Finite automata are connected with the algebra of regular events, whose elements are sets of words realizable (recognizable) by the finite automata and whose signature operations are union $x\vee y$, concatenation $xy$ and iteration $x^*$. This algebra does not have a finite complete system of identities. However, the subalgebra consisting of all events that contain the empty word has a finite complete system of identities.

Equivalent transformations of algorithms.

For the complete class of algorithms (cf. Algorithm) and the functional equivalence relation, the problem of equivalent transformations has a negative solution, since in this case the relation of functional equivalence is not recursively enumerable. Consequently, to obtain positive solutions either the class of algorithms should be restricted, or the formulation of the problem should be modified. Subclasses of algorithms are often specified by means of finite automata, automata with magazine or stack memory, discrete transformers of a different type, programs with restrictions on the topological structure or on the volume of the working memory, etc. Sometimes subclasses of algorithms are distinguished with respect to a functional criterion by giving the class of computable functions (cf. Computable function). In the last case a specific basis set of functions is given, which is then closed by means of operations such as superposition, recursion, restricted summation, etc. However, for the classes of algorithms distinguished in this way, the relation of functional equivalence turns out to be solvable only in cases where the corresponding class of functions is fairly narrow.

Consequently, other methods have been developed, in particular, the approach based on the study of schemes of algorithms. These schemes differ from algorithms basically by the way in which they ascribe functions. The equivalence relation of schemes of algorithms is regarded as a specific approximation of the relation of functional equivalence of algorithms, so that the solution of the problem of equivalent transformations for schemes of algorithms may be considered as an approximate solution of this problem for algorithms. However, positive solutions here can also be obtained only for fairly rough approximations, which are close to finite automata. Positive solutions may be obtained for the class of all algorithms if the concept of completeness of a system of laws is relaxed, for example, by dropping the requirement that the laws should be applied finitely many times. More precise, a system of laws is called limiting complete if, by applying laws of it, any two equivalent algorithms can be transformed in the limit — that is, after infinitely many steps — into a (in general, an infinite) computational complex. It turns out that a finite limiting-complete system of schemes of local laws can be constructed for a functionally-complete class of everywhere-defined programs in some simple basis. The real meaning of limit completeness resides, in particular, in the fact that systems with this property are also complete in the usual sense for the class of programs that compute finitary functions.

In connection with the problem of optimization of control systems an important role is played by directed transformations, the final outcomes of which are optimal control systems or systems close to optimal. In particular, great interest is attached to the study of the possibility of monotone transformations, which at every step do not increase the complexity of the control system in some sense.

References

[1]	Yu.I. Yanov, "On the problem of equivalent transformations" Mitt. Math. Ges. DDR : 2–3 (1973) pp. 47–58 (In Russian)
[2]	Yu.I. Yanov, "On systems of identities for algebras" Probl. Kibernet. , 8 (1962) pp. 75–90 (In Russian)
[3]	V.L. Murskii, "The existence in three-valued logic of a closed class with finite basis, not having a finite complete system of identities" Soviet Math. Dokl. , 6 pp. 1020–1024 Dokl. Akad. Nauk SSSR , 163 : 4 (1965) pp. 815–818
[4]	V.L. Murskii, "On the equivalent transformations of switching circuits" Probl. Cybernetics , 5 (1964) pp. 77–98 Probl. Kibernet. , 5 (1961) pp. 61–76
[5]	V.L. Murskii, "On transformations of finite automata" Probl. Kibernet. , 15 (1965) pp. 101–116 (In Russian)
[6a]	Yu.I. Yanov, "The logical scheme of algorithms" Probl. Cybernetics , 1 (1960) pp. 82–140 Probl. Kibernet. , 1 (1958) pp. 75–127
[6b]	Yu.I. Yanov, "Limiting-complete systems of rules of equivalent transformations for programs computed by everywhere defined functions" Probl. Kibernet. , 37 (1980) pp. 215–238 (In Russian)