View source for Synthesis problems

An aggregate of problems centered on the problem of constructing a [[Control system|control system]] with a prescribed way of functioning. A control system is usually made up of elements which are themselves simple control systems. Formerly synthesis meant that the structure of the elements, a rule for combining them and a means of using the structure of the control system to define the function which it realizes are given.

Every class of control systems gives rise in a natural way to a specific class of functions. A synthesis problem originally consisted of constructing a control system realizing a given function from this class.

Examples. 1) Given a [[Boolean function|Boolean function]], construct a formula which realizes it. 2) Given a set of Boolean functions, construct a multipolar [[Contact scheme|contact scheme]] which realizes this set. 3) Given an exact description of the behaviour of an [[Automaton|automaton]], construct the automaton itself. 4) Given a [[Computable function|computable function]], find an algorithm that computes it, or compose the corresponding program.

The above examples are concerned with discrete mathematics. However, the following are characteristic examples of a continuous nature. a) Given the logarithmic amplitude-frequency characteristic of an (automatic) control system (or, more generally, working conditions of it such as perturbation and control actions, disturbances, restrictions on working time, etc.), synthesize an (automatic) control system with these characteristics. b) Given a system of linear equations and inequalities, and also a linear function, construct a computing scheme which maximizes this function on the solution set of this system. c) Given a system of differential equations and a desired degree of accuracy for its solution, find an algorithm for solving this system numerically to within this degree of accuracy.

It is conventional to treat the last three examples as belonging to continuous mathematics, although the search for an approximate numerical solution already presupposes the approximation of continuous functions by discrete ones. These problems thus involve an interplay between continuous and discrete mathematics.

The mathematical formulation of synthesis problems presupposes an exact indication of the language in which a function is given. Which problems can arise in the solution of synthesis problems depend on this language. In the majority of cases there is a comparatively simple method for constructing a control system of a canonical form.

However, when the class of control systems is not too small, the problem can have many other solutions; the problem naturally arises of choosing one that is optimal in some sense. To this end one introduces a functional characterizing the quality of a control system, such as the number of elements in it, its cost, its volume, its capacity (that is, the greatest number of its elements in an active state), its working time, the probability of breakdown, etc. It is important that this functional, usually called the complexity, should accurately reflect the property required of the control system, and be readily computable from it. A refinement of synthesis problems consists of constructing, for a given function, a control system that realizes it with minimal complexity.

In fact, such a definite formulation of the problem is only possible for finite models of control systems. As a result, all synthesis problems are more clearly stated in this case, and so finite models are given most attention below.

For finite models of control systems a typical situation is that in which the problem has a trivial solution. For example, if one wishes to minimize the number of elements in a scheme, then the trivial method of solution consists in first listing all schemes containing one element and verifying whether or not one of them realizes the given function, then listing all schemes containing two elements and verifying again, etc. until one finds a scheme that realizes the given function. This scheme then has the minimum number of elements.

However, due to the large number of steps required, the trivial method is not very effective. Besides, if the complexity of the function to be realized exceeds a certain comparatively low threshold, then the trivial method becomes practically unworkable and the use of the fastest computers extends its scope only slightly. This means that a further refinement of the formulation of synthesis problems is required.

The tendencies listed here are illustrated below for the example of one class of control systems, diagrams of functional elements (cf. [[Diagram of functional elements|Diagram of functional elements]]), for the special case where complexity is taken to be the number of elements in the scheme. The functions realizable by this type of control system are those of the algebra of logic (Boolean functions).

First of all, one must note that the non-applicability of solving by the trivial method is only one of the reasons leading to a revision of the formulation of synthesis problems. There is a conjecture that any algorithm which constructs for every Boolean function a scheme with a minimal number of elements inevitably contains in some sense a listing of all Boolean functions. As positive evidence for this there is a theorem which states that if one considers an infinite set of Boolean functions containing one most complex function for every number of variables, and if one takes the closure of this set under the operations of renaming variables (without identification) and substituting constants, then one obtains the set consisting of all general Boolean functions (up to inessential variable functions). This conjecture has much indirect support confirming the fact that even if one relaxes the requirement on the number of elements that are allowed for the construction of the schemes close to optimal, but retains the requirement that the algorithm be applicable to every Boolean function, then the listing cannot be reduced. The concept of the inevitability in principle of listing is another basic reason for modifying the formulation of synthesis problems. There are several possibilities here.

The Shannon approach (named after C.E. Shannon, who first suggested it for contact schemes) is connected with the function

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s0919101.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s0919102.png" /> is the smallest possible number of elements in a scheme realizing a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s0919103.png" />, and the maximum is taken over all Boolean functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s0919104.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s0919105.png" /> variables. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s0919106.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s0919107.png" /> depend on the basis, that is, on the set of function elements that can be used in the construction of the schemes. Synthesis problems consist of finding an effective method of constructing, for any Boolean function in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s0919108.png" /> variables, schemes with a number of elements essentially not greater than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s0919109.png" />.

For a more general formulation of the problem, one assigns to every functional element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191010.png" /> a positive number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191011.png" /> as the complexity of this element, which depends only on the function realizable by the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191012.png" />, and ascribes to every scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191013.png" /> the complexity

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191014.png" /></td> </tr></table>

where the summation is over all the elements of the scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191015.png" />. For every Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191016.png" /> the complexity of its realization (in a given basis) is defined as follows:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191017.png" /></td> </tr></table>

where the minimum is taken over all schemes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191018.png" /> realizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191019.png" />. Then, as before, one sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191020.png" />, and for an arbitrary Boolean function in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191021.png" /> variables it is required to construct a scheme of complexity not greater (or not much greater) than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191022.png" />.

For this approach one needs to be able to compute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191023.png" /> or bound it accurately, at least from below. It turns out that one can obtain a fairly good lower bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191024.png" /> by the power method, which is based on the following consideration. The number of all possible schemes realizing Boolean functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191025.png" /> variables and having complexity not greater than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191026.png" />, cannot be smaller than the total number of Boolean functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191027.png" /> variables. In the power method, one needs only obtain a satisfactory upper bound for the number of schemes under consideration.

One can then judge to a great extent the quality of an arbitrary universal synthesis method (that is, a method suitable for any Boolean function) by how many times the complexity of the schemes constructed by it for a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191028.png" /> differs from the lower bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191029.png" />. At the same time, the complexity of these schemes serves as a constructive bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191030.png" /> and is asymptotically equal to it as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191031.png" />. Thus, this is asymptotically the best synthesis method and enables one to describe the asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191032.png" />. Let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191033.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191034.png" /> is the number of occurrences of an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191035.png" /> and the minimum is taken over all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191036.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191037.png" />. Then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191038.png" /></td> </tr></table>

For other classes of control systems, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191039.png" />, and also the complexities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191041.png" />, are defined in a similar way. For a contact scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191042.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191043.png" /> is usually the number of contacts in it, and when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191044.png" /> is a formula, it is the number of symbols denoting variables in it. For automata and Turing machines (cf. [[Turing machine|Turing machine]]), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191045.png" /> is sometimes taken to be the number of states. In these cases the corresponding asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191046.png" /> is shown in Table 1.''''''<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1">Class of control systems</td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191047.png" /></td> <td colname="3" style="background-color:white;" colspan="1">Remark</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">Diagrams of functional elements</td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191048.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191049.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">Contact schemes</td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191050.png" /></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">Formulas</td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191051.png" /></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">Automata</td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191052.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191053.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">Turing machines</td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191054.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191055.png" /> is the number of letters in the internal alphabet of the machine</td> </tr> </tbody> </table>

</td></tr> </table>

For other types of complexity, such as the probability of error, and for other classes of control systems, such as automata, the corresponding asymptotic relation may contain not one but two or more parameters, and, in general, the problem of finding asymptotics (say for automata) is algorithmically unsolvable.

An analysis of the lower bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191056.png" /> shows that, in fact, for almost-all Boolean functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191057.png" /> variables, the complexity of realization is asymptotically not less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191058.png" />. This means that a given synthesis method for almost-all Boolean functions yields almost the simplest schemes.

However, first, despite the fact that the class contains almost-all Boolean functions, for sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191059.png" /> none of the functions in the class can be clearly described, and secondly, it consists of the hardest functions to realize, and these are seldom encountered in problems of an applied nature. So, such functions are not of great interest, and it again becomes necessary to modify the formulation of the synthesis problem.

It must be noted that functions for which the synthesis problem is actually important form a negligible part of all Boolean functions, and if the conjecture on the necessity of listing is true as stated, any effective universal synthesis method will automatically give in some cases schemes that are by no means the simplest. It is impossible to describe the set of these functions, and the problem arises of classifying Boolean functions for synthesis purposes. This approach to the formulation of the problem is concerned with the selection of important classes of functions, with the creation of special synthesis methods for them, each oriented towards a function of a specific class, and also with estimating the quality of the schemes thus obtained.

An effective means for solving such problems is provided by the local coding principle. This principle presupposes a coding of the functions in the class under consideration in such a way that the value of a function can be computed using a comparatively small part of the code. If one succeeds in realizing certain auxiliary operators in a sufficiently simple way, then the local coding principle gives a synthesis method which is asymptotically optimal for the class considered. Moreover, the following relation holds with a fair degree of generality:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191060.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191061.png" /> is the subset of those functions of the class that depend on a given set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191062.png" /> variables, and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191063.png" /></td> </tr></table>

where the maximum is taken over all Boolean functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191064.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191065.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191066.png" /> here).

The concrete form taken by this asymptotic relation is most conveniently illustrated on classes of Boolean functions which take the value 1 at a given number of points. The most typical examples are shown in Table 2.''''''<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1">Number of points at which the function is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191067.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191068.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191069.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191070.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191071.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191072.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191073.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191074.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191075.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191076.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191077.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191078.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191079.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191080.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191081.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191082.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191083.png" /></td> </tr> </tbody> </table>

</td></tr> </table>

On the basis of the local coding principle good synthesis methods have also been obtained for very narrow classes of functions (such as symmetric functions), i.e. for those functions which are of most interest from a practical point of view. However, in the case under consideration, the lower bound obtained by the power method turns out to be too weak for judging the quality of schemes. As far as restricting the class of functions being considered at a given time is concerned, this is inevitable, since the limiting case of a narrow class is one containing not more than one function in each number of variables. This means in practice that one considers individual concrete functions.

Two problems arise here. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191084.png" />) To construct, for a given concrete function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191085.png" />, a scheme with the smallest possible number of elements, and thus to obtain an upper bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191086.png" />. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191087.png" />) To obtain the best possible lower bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191088.png" />. Of these problems, the first is usually the simpler, since for its solution it is sufficient in the final analysis to construct just one scheme, whereas the second requires a survey in some sense of all the schemes realizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191089.png" />. This motivated a whole new trend in the search for methods of obtaining lower bounds for concrete functions.

In finding lower bounds that are linear in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191090.png" />, the number of arguments of the function (or, in general, the volume of input information) usually causes no great difficulties. Finding stricter lower bounds is a significantly more complex problem. The first examples of this type were a lower bound of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191091.png" /> for formulas in the basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191092.png" /> realizing a linear function (with addition modulo 2) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191093.png" /> arguments, and a lower bound of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191094.png" /> for Markov normal algorithms (cf. [[Normal algorithm|Normal algorithm]]) applied to words of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191095.png" />. The best lower bounds so far (1984) obtained are of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191096.png" />, provided one ignores those obtained under very strong restrictions on the class of control systems (for example, when the system of elements is incomplete) or by the use of powerful means for representing a function that actually include a listing all functions.

The non-triviality of the investigation into the complexity of realizing concrete functions is also indicated by the fact that many problems (such as the multiplication of integers, the multiplication of matrices, and the recognition of symmetry of a word on multi-tape Turing machines) for which comparatively high lower bounds were expected, turned out to be in actual fact simpler than at first supposed.

In minimizing other parameters of schemes, such as delays, probability of a breakdown, etc. roughly the same problems arise. One can establish a definite connection between various parameters, and thanks to the simulation of certain objects by others, this can often be done for parameters of control systems in different classes. Thus, results obtained in synthesis problems are not isolated, but are closely interrelated, and can often be transferred from one domain into another.

Much of the above carries over to infinite models of control systems. However, in the formulation of synthesis problems, and even more so in their solution, the situation is significantly more complex.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  O.B. Lupanov,   "On a certain approach to the synthesis of control systems - the local coding principle"  ''Probl. Kibernet.'' , '''14'''  (1965)  pp. 31–110  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  S.V. Yablonskii,   "On algorithmic difficulties in designing minimal control circuits"  ''Probl. Kibernet.'' , '''2'''  (1959)  pp. 75–121  (In Russian)</TD></TR></table>



====Comments====
Given a discrete- or continuous-time input-output dynamical system or control dynamical system, also simply called dynamical system,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191097.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191098.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s09191099.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910100.png" /></td> </tr></table>

and a starting point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910101.png" /> at time zero, the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910102.png" /> defines a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910103.png" /> from a space of input functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910104.png" /> to a space of output function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910105.png" />, sometimes called the behaviour of the initialized system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910106.png" />. Given a behaviour <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910107.png" />, one now has the synthesis problem of finding a dynamical system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910108.png" /> (of a suitable class) such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910109.png" />. One says then that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910110.png" /> realizes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910111.png" />, and in this setting the synthesis problem is usually called the realization problem and one speaks of realization theory.

In the case of a time-invariant linear dynamical input-output system

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910112.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910113.png" /></td> </tr></table>

(or its discrete counterpart), its behaviour is completely determined by its transfer function

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910114.png" /></td> </tr></table>

with

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910115.png" /></td> </tr></table>

which gives the Laplace transforms (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910116.png" />-transforms in the discrete-time case) of the input and output functions. In this case one speaks of realizing the strictly proper rational matrix function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910117.png" /> or of the series of Markov parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910118.png" />. Thus, a realization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910119.png" /> is a triple of matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910120.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910121.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910122.png" />. The least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910123.png" /> such that there exists a realization with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910124.png" /> an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910125.png" />-matrix is the McMillan degree of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910126.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910127.png" />. It is equal to the rank of the infinite block Hankel matrix

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910128.png" /></td> </tr></table>

If one is looking for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910129.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910130.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910131.png" />, one speaks of a partial realization problem.

There are realization algorithms that are locally continuous in the parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910132.png" />. There exists a global continuous realization if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910133.png" /> (one output) or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910134.png" /> (one input). (Non-existence of continuous canonical forms.)

Realizations of matrix functions and, more generally, operator-valued functions have proved to be a valuable tool in, e.g., minimal factorization and Wiener–Hopf factorization of matrix and operator-valued functions, cf. e.g. [[#References|[a11]]]–[[#References|[a13]]].

Analogous realization questions arise for stochastic dynamical systems; cf. e.g. [[#References|[a5]]] and [[#References|[a6]]] for a discussion of two stochastic realization problems (state space models for Gaussian random processes, transmission line models realizing a given covariance function).

For a survey of non-linear deterministic finite-dimensional realization theory, cf. e.g. [[#References|[a10]]].

In control theory the phrase  "synthesis problem in control theorysynthesis problem"  mostly refers to the problem of finding for a given input-output dynamical system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910135.png" /> a suitable feedback law <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910136.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910137.png" /> is some (measured) output. (Or, more generally, a dynamical input-output system with input <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910138.png" /> and output <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910139.png" /> such that the resulting closed-loop system System Controller <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910140.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910141.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910142.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910143.png" />

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/s091910a.gif" />

Figure: s091910a

has some desired behaviour. For instance, that certain disturbances are suppressed or that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s091/s091910/s091910144.png" /> matches a pre-given behaviour.)

For the specific question of the synthesis or realization of electrical networks, cf. (the editorial comments to) [[Network|Network]] and the references given there.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  N. Pippenger,   "The complexity of monotone Boolean functions"  ''Math. Syst. Theory'' , '''11'''  (1978)  pp. 289–316</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A.A. Razborov,   "Lower bounds for the monotone complexity of some Boolean functions"  ''Soviet Math. Dokl.'' , '''31'''  (1985)  pp. 354–357  ''Dokl. Akad. Nauk SSSR'' , '''281''' :  4  (1985)  pp. 798–801</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.E. Savage,   "The complexity of computing" , Wiley  (1976)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  I. Wegener,   "The complexity of Boolean functions" , Wiley &amp; Teubner  (1987)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Lindquist,   G. Picci,   "State space models for Gaussian stochastic processes"  M. Hazewinkel (ed.)  J.C. Willems (ed.) , ''Stochastic Systems: Math. of Filtering and Identification and Appl.'' , Reidel  (1981)  pp. 169–204</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P. DeWilde,   J.T. Fokkema,   I Widya,   "Inverse scattering and linear prediction"  M. Hazewinkel (ed.)  J.C. Willems (ed.) , ''Stochastic Systems: Math. of Filtering and Identification and Appl.'' , Reidel  (1981)  pp. 307–350</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  M. Hazewinkel,   "(Fine) moduli spaces for linear systems: what are they and what are they good for"  C.I. Byrnes (ed.)  C.F. Martin (ed.) , ''Geometrical Methods for the Theory of Linear Systems'' , Reidel  (1980)  pp. 125–193</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  A.H. Zemanian,   "Realizability theory for continuous linear systems" , Acad. Press  (1972)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  R.E. Kalman,   P.L. Falb,   M.A. Arbib,   "Topics in mathematical systems theory" , McGraw-Hill  (1969)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  B. Jakubczyk,   "Realization theory for nonlinear systems: three approaches"  M. Fliess (ed.)  M. Hazewinkel (ed.) , ''Algebraic and geometric methods in nonlinear control theory'' , Reidel  (1986)  pp. 3–32</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  H. Bart,   I. Gohberg,   M.A. Kaashoek,   "Minimal factorization of matrix and operation functions" , Birkhäuser  (1979)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  K. Clancey,   I. Gohberg,   "Factorization of matrix functions and singular integral operators" , Birkhäuser  (1981)</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  H. Bart,   I. Gohberg,   M.A. Kaashoek,   "Explicit Wiener–Hopf bifurcation and realization"  I. Gohberg (ed.)  M.A. Kaashoek (ed.) , ''Constructive Methods of Wiener–Hopf Factorization'' , Birkhäuser  (1986)  pp. 235–316</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  W.M. Wonham,   "Linear multivariable control" , Springer  (1974)</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  E.D. Sontag,   "Mathematical control theory" , Springer  (1990)</TD></TR></table>