View source for Reliability and inspection of control systems

''problems in the reliability of control systems''

A branch of the theory of control systems that studies control systems subject to noise.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r0811701.png" /> be a class of control systems and suppose there is a source of noise, or of faults, the effect of which on a [[Control system|control system]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r0811702.png" /> is to convert it into control systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r0811703.png" /> of some class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r0811704.png" />. If it is assumed that the source of noise may also preserve the control system unchanged, e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r0811705.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r0811706.png" />. Suppose that each control system in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r0811707.png" /> is uniquely determined by its scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r0811708.png" />; then the action of the source of noise reduces to its action on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r0811709.png" />. A source of failures subjects the scheme to a transformation, manifested in one of the following ways: a) a disruption in the operation of the elements, i.e. changes in the elements; b) a change in the connections among the elements; etc. As a result, the original scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117010.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117011.png" /> moves into  "faulty"  states <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117012.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117013.png" />, defining control systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117014.png" />, respectively. Associated with these schemes one has corresponding functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117015.png" />, called failure functions (note that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117016.png" /> characterizes the performance of the original control system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117017.png" />). The source of failure is usually characterized additionally either by an error-probability distribution or by restrictions on the possible number of elementary failures.

Reliability problems are considered mainly for three classes of control systems: diagrams of functional elements, contact schemes and automata (cf. [[Automaton|Automaton]]; [[Contact scheme|Contact scheme]]; [[Diagram of functional elements|Diagram of functional elements]]).

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117018.png" /> be a class of diagrams of functional elements, the latter belonging to a given basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117019.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117021.png" />. If the failure source affects only the elements of the diagram, it converts elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117022.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117024.png" />, into elements with the same number of inputs as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117025.png" />, but with a possibly different performance; the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117026.png" /> remain unchanged. Thus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117027.png" /> consists of unreliable elements and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117028.png" /> of reliable ones. In this case the source of failure can be described in terms of the failure probabilities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117029.png" /> of the elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117030.png" />, respectively. For example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117031.png" /> might consist of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117032.png" />-elements, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117033.png" />-elements and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117034.png" />-elements, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117035.png" /> of voting elements, implementing the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117038.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117039.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117040.png" />, respectively. It may be assumed here that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117041.png" /> is the (common) failure probability of the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117042.png" />.

When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117043.png" /> is a class of contact schemes, one considers a failure source in which the elementary failures are either short-circuited or broken contacts. In this context one assumes in addition that in a contact scheme implementing functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117044.png" /> variables there may occur at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117045.png" /> elementary failures.

The problems that arise in connection with the reliability and inspection of such systems may be divided into three types.

==I. Design of reliable schemes of unreliable elements.==
This branch of the theory has been developed for two classes of systems: contact schemes and diagrams of functional elements. For the latter, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117046.png" /> is characterized by a certain probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117047.png" /> of cases in which it functions incorrectly. Here there are two basic questions.

1) What properties must the basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117048.png" /> have so that it should be possible, for any [[Boolean function|Boolean function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117049.png" /> and any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117050.png" />, to design a diagram realizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117051.png" /> and such that the probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117052.png" /> of faulty performance be less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117053.png" />? In other words, it is desired that any Boolean function should be realizable by an arbitrarily reliable diagram.

It has been established that there are bases in which, for any function, there is an arbitrarily reliable diagram realizing it. An example is the basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117054.png" /> (see above): <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117055.png" /> consists of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117056.png" />-elements, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117057.png" />-elements and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117058.png" />-elements with failure probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117059.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117060.png" /> consists of an absolutely-reliable voting element. Necessary and sufficient conditions have been determined in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117061.png" /> under which arbitrarily reliable diagrams can be designed for all Boolean functions.

2) To devise a method for the synthesis of minimal (or in some sense almost minimal) diagrams realizing Boolean functions, of unreliability not exceeding a preassigned value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117062.png" />. It turns out (e.g. for the above-described basis, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117063.png" />) that a method can be devised for synthesizing diagrams which, for the majority of Boolean functions and a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117064.png" />, yields asymptotically (in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117065.png" />) minimal diagrams. In particular, for the Shannon function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117066.png" />, expressing the minimum number of elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117067.png" /> (see previous example) sufficient for the realization of any Boolean function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117068.png" /> variables with unreliability at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117069.png" />, one has the following asymptotic relationship:

<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/r/r081/r081170/r08117070.png" /></td> </tr></table>

==II. Design of self-correcting schemes.==
This direction has been most thoroughly studied for two classes of systems — contact schemes and diagrams of functional elements. In this context the failure source is characterized by constraints on the number of elementary breakdowns. It is assumed that within the limits of the discussion no further changes occur in the scheme. A scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117071.png" /> realizing a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117072.png" /> is said to be self-correcting relative to a given failure source if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117073.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117074.png" />. In other words, a self-correcting scheme functions correctly, regardless of the effect of the failure source. For example, the contact scheme of Fig. a, which realizes the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117075.png" />, is self-correcting for a source that produces at most one broken contact.

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

Figure: r081170a

The major problems in this area are: 1) to clarify the conditions under which self-correcting schemes exist; and 2) to work out methods for the synthesis of minimal (or in some sense almost minimal) self-correcting schemes. Below the solution to these problems in the case of contact schemes with a failure source producing at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117076.png" /> short-circuited and broken contracts is given.

It turns out that for any Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117077.png" /> one can design a self-correcting scheme relative to this failure source. This can be done by taking any contact scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117078.png" /> that realizes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117079.png" />, replacing therein every contact <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117080.png" /> by a subscheme consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117081.png" /> identical blocks connected in series, each of which consists of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117082.png" /> copies of the given contact <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117083.png" /> connected in parallel. This scheme is known as a trivial self-correcting scheme. Its complexity is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117084.png" /> times that of the original scheme. The example of Fig. a shows that there also exist non-trivial self-correcting schemes.

The problem of designing self-correcting schemes is a special case of the synthesis problem for control systems with additional conditions. The main result here is that for most Boolean functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117085.png" /> one can design a self-correcting scheme (relative to some class of sources) whose complexity asymptotically approaches (as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117086.png" />) the complexity of a minimal scheme realizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117087.png" /> but not being self-correcting. It has been shown that, subject to certain restrictions on the order of increase of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117088.png" />, the Shannon function satisfies the following asymptotic relationship:

<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/r/r081/r081170/r08117089.png" /></td> </tr></table>

==III. Inspection of control systems.==
This area has been most thoroughly investigated for three classes of systems: contact schemes, diagrams of functional elements and automata. The consideration of inspection problems for control systems pre-supposes the following: 1) the presence of a failure source that, having affected the control system, maintains the latter in its failed state for some time, during which it produces no further failures; 2) a specification of the desired objective of the inspection; the latter is defined as the detection of some property of the control system. E.g., to determine whether the system is functioning correctly or not (checking problem), or, if the system has failed, to detect the source of the failure (diagnostics problem); and 3) a specification of the means of inspection. Inspection may be carried out with or without intervention in the scheme — for example, replacement of elements by standard elements, interchanging blocks of the same type, using additional check-points in the scheme, etc. The means of inspection also include some procedure for extracting information about the controlled object. These are experiments falling into two categories — unconditional and conditional. In unconditional experiments, the signal sequences fed to the input of the controlled device are pre-determined and are independent of the sequence at its output. In conditional experiments each successive symbol in the input sequence can be selected depending on the symbols appearing at the output at the previous instant of time.

A set of experiments that permits the detection of a given property is called a test. Since there are usually a great number of different tests detecting any desired property, one introduces a complexity measure in the set of tests and aims to find a test of minimum complexity. The main problem here is how to devise minimal or near-minimal tests for each property. This is part of a more general problem — the construction of compact algorithms for the recognition of various properties.

To illustrate this, consider the solution of these problems for contact schemes and diagrams of functional elements, assuming no interference in the scheme. The starting point here is the sequence of failure functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117090.png" /> of the scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117091.png" /> realizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117092.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117093.png" />. It may happen that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117094.png" /> for some pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117095.png" />, meaning that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117096.png" />-th and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117097.png" />-th failures are indistinguishable. Thus, the set of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117098.png" /> is partitioned into equivalence classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r08117099.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170100.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170101.png" /> belong to the same class if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170102.png" />; it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170103.png" /> is in the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170104.png" />. Failures producing functions of the same class are indistinguishable. The classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170105.png" /> yield a table of failure functions.

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

Figure: r081170b

Example. The contact scheme of Fig. bimplements 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/r/r081/r081170/r081170106.png" /></td> </tr></table>

and the failure source produces at most one broken contact. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170108.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170109.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170110.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170111.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170112.png" />. Thus there are seven classes: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170113.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170114.png" />, generating the failure function table illustrated below. The property to be detected is usually specified in terms of a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170115.png" /> of pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170116.png" />, denoting the indices of the classes of failure functions that one wishes to distinguish. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170117.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170118.png" />, the property is distinguishability of the correctly-operating scheme from any failed stated (checking problem). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170119.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170120.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170121.png" />, one wishes to know how to distinguish each state from any other state (diagnostics problem). Finally, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170122.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170123.png" />, one has the problem of  "block"  diagnostics, i.e. to identify the part of the scheme containing the failed element.''''''<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">sequence</td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170124.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170125.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170126.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170127.png" /></td> <td colname="6" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170128.png" /></td> <td colname="7" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170129.png" /></td> <td colname="8" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170130.png" /></td> <td colname="9" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170131.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170132.png" /></td> <td colname="2" style="background-color:white;" colspan="1">001</td> <td colname="3" style="background-color:white;" colspan="1">1</td> <td colname="4" style="background-color:white;" colspan="1">0</td> <td colname="5" style="background-color:white;" colspan="1">1</td> <td colname="6" style="background-color:white;" colspan="1">1</td> <td colname="7" style="background-color:white;" colspan="1">1</td> <td colname="8" style="background-color:white;" colspan="1">1</td> <td colname="9" style="background-color:white;" colspan="1">0</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170133.png" /></td> <td colname="2" style="background-color:white;" colspan="1">011</td> <td colname="3" style="background-color:white;" colspan="1">1</td> <td colname="4" style="background-color:white;" colspan="1">0</td> <td colname="5" style="background-color:white;" colspan="1">0</td> <td colname="6" style="background-color:white;" colspan="1">1</td> <td colname="7" style="background-color:white;" colspan="1">1</td> <td colname="8" style="background-color:white;" colspan="1">1</td> <td colname="9" style="background-color:white;" colspan="1">1</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170134.png" /></td> <td colname="2" style="background-color:white;" colspan="1">010</td> <td colname="3" style="background-color:white;" colspan="1">1</td> <td colname="4" style="background-color:white;" colspan="1">1</td> <td colname="5" style="background-color:white;" colspan="1">0</td> <td colname="6" style="background-color:white;" colspan="1">0</td> <td colname="7" style="background-color:white;" colspan="1">1</td> <td colname="8" style="background-color:white;" colspan="1">1</td> <td colname="9" style="background-color:white;" colspan="1">1</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170135.png" /></td> <td colname="2" style="background-color:white;" colspan="1">110</td> <td colname="3" style="background-color:white;" colspan="1">1</td> <td colname="4" style="background-color:white;" colspan="1">1</td> <td colname="5" style="background-color:white;" colspan="1">1</td> <td colname="6" style="background-color:white;" colspan="1">0</td> <td colname="7" style="background-color:white;" colspan="1">0</td> <td colname="8" style="background-color:white;" colspan="1">1</td> <td colname="9" style="background-color:white;" colspan="1">1</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170136.png" /></td> <td colname="2" style="background-color:white;" colspan="1">100</td> <td colname="3" style="background-color:white;" colspan="1">1</td> <td colname="4" style="background-color:white;" colspan="1">1</td> <td colname="5" style="background-color:white;" colspan="1">1</td> <td colname="6" style="background-color:white;" colspan="1">1</td> <td colname="7" style="background-color:white;" colspan="1">0</td> <td colname="8" style="background-color:white;" colspan="1">0</td> <td colname="9" style="background-color:white;" colspan="1">1</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170137.png" /></td> <td colname="2" style="background-color:white;" colspan="1">101</td> <td colname="3" style="background-color:white;" colspan="1">1</td> <td colname="4" style="background-color:white;" colspan="1">1</td> <td colname="5" style="background-color:white;" colspan="1">1</td> <td colname="6" style="background-color:white;" colspan="1">1</td> <td colname="7" style="background-color:white;" colspan="1">1</td> <td colname="8" style="background-color:white;" colspan="1">0</td> <td colname="9" style="background-color:white;" colspan="1">0</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170138.png" /></td> <td colname="2" style="background-color:white;" colspan="1">000</td> <td colname="3" style="background-color:white;" colspan="1">0</td> <td colname="4" style="background-color:white;" colspan="1">0</td> <td colname="5" style="background-color:white;" colspan="1">0</td> <td colname="6" style="background-color:white;" colspan="1">0</td> <td colname="7" style="background-color:white;" colspan="1">0</td> <td colname="8" style="background-color:white;" colspan="1">0</td> <td colname="9" style="background-color:white;" colspan="1">0</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170139.png" /></td> <td colname="2" style="background-color:white;" colspan="1">111</td> <td colname="3" style="background-color:white;" colspan="1">0</td> <td colname="4" style="background-color:white;" colspan="1">0</td> <td colname="5" style="background-color:white;" colspan="1">0</td> <td colname="6" style="background-color:white;" colspan="1">0</td> <td colname="7" style="background-color:white;" colspan="1">0</td> <td colname="8" style="background-color:white;" colspan="1">0</td> <td colname="9" style="background-color:white;" colspan="1">0</td> </tr> </tbody> </table>

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

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170140.png" /> be the set of sequences on which the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170141.png" /> are defined. A set of sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170142.png" /> selected from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170143.png" /> is called a test for the given failure function table relative to the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170144.png" /> if, for any pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170145.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170146.png" />, there is a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170147.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170148.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170149.png" />. A test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170150.png" /> is said to be minimal if it contains the minimum possible number of sequences. A test is called a dead-end test if removal of any sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170151.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170152.png" /> results in a subset of sequences that is not a test. The entire set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170153.png" /> is a (trivial) test. A minimal test is a dead-end test. The problem of finding a minimal test is motivated by the need to reduce the inspection time.

There exists an algorithm for the determination of all dead-end tests (hence also of minimal tests). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170154.png" /> be the set of all sequences on which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170155.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170156.png" /> are different. Multiplying out in the expression

<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/r/r081/r081170/r081170157.png" /></td> </tr></table>

according to the rules of Boolean algebra and then deleting  "absorbed"  terms by using the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170158.png" />, the remaining expression will correspond to a dead-end test. Thus, considering the above example, with regard to the checking problem

<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/r/r081/r081170/r081170159.png" /></td> </tr></table>

the algorithm yields

<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/r/r081/r081170/r081170160.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/r/r081/r081170/r081170161.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/r/r081/r081170/r081170162.png" /></td> </tr></table>

There are five dead-end tests: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170163.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170164.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170165.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170166.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170167.png" />; of these, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170168.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081170/r081170169.png" /> are minimal. This algorithm may be used to detect errors in the assembling of component elements. With slight modifications, it is also applicable to the design of short dead-end experiments for automata. Its efficiency drops sharply as the failure function table increases in size. To improve its efficiency one must take into consideration such factors as the structure of the table and further information as to the structure of the scheme itself. Several methods have been devised to this end. Other aspects of the reliability and inspection of control systems are elaborated in probability theory.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.A. Chegis,   S.V. Yablonskii,   "Logical means for controlling the functioning of electric systems"  ''Trudy Mat. Inst. Steklov.'' , '''51'''  (1958)  pp. 270–360  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.A. Solov'ev,   "Tests" , Novosibirsk  (1978)  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  Yu.G. Potapov,   S.V. Yablonskii,   "On the synthesis of self-correcting relay circuits"  ''Soviet Phys. Dokl.'' , '''5'''  (1961)  pp. 932–935  ''Dokl. Akad. Nauk SSSR'' , '''134''' :  3  (1960)  pp. 544–547</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  J. von Neumann,   "Probabilistic logics and the synthesis of reliable organisms from unreliable components" , ''Automata studies'' , Princeton Univ. Press  (1956)  pp. 43–98</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E.F. Moore,   C.E. Shannon,   "Reliable circuits using less reliable relays I, II"  ''J. Franklin Inst.'' , '''262'''  (1956)  pp. 198–208; 281–297</TD></TR></table>