View source for Tests

''in cybernetics''

One of the most important means of logical analysis of information. Tests were first used in the problems of controlling the functioning of an electrical circuit. Later [[Pattern recognition|pattern recognition]] algorithms were developed on the basis of tests. The test approach can be applied successfully in many areas of mathematics. The fundamental problems concerning tests can be formulated in the following way.

1) One is given a rectangular table consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t0924701.png" /> rows and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t0924702.png" /> columns. The rows are characterized by questions (marks) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t0924703.png" /> from some set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t0924704.png" />, and the columns by objects (patterns) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t0924705.png" /> from some set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t0924706.png" />.

<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"></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t0924707.png" /></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t0924708.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t0924709.png" /></td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> </td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> </td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247010.png" /></td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="5" style="background-color:white;" colspan="1"></td> </tr> </tbody> </table>

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

The entry in the cell at the intersection of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247011.png" />-th row and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247012.png" />-th column is an answer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247013.png" /> (the value of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247014.png" />-th mark for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247015.png" />-th pattern), which lies in some set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247016.png" />. Thus, as long as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247017.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247018.png" /> one can consider the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247019.png" />-th column <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247020.png" /> as a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247021.png" />. It is natural to regard the columns as being pairwise distinct. Since the nature of the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247023.png" />, respectively, is irrelevant, from now on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247025.png" />. In certain cases there is a partial order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247026.png" /> given on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247028.png" />. Sometimes the columns are written as probabilities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247029.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247030.png" />).

2) One defines the aim of the logical analysis of the table. For this one fixes some subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247031.png" /> of pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247033.png" />, of column numbers. In particular, if the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247034.png" /> is partitioned into classes, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247035.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247037.png" /> belong to the same class and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247038.png" />. The subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247039.png" /> can be interpreted as a relation, or as some property.

There are two special cases: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247041.png" /> is a distinguishing function (this case is connected with the verification problem); 2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247042.png" />, related to the diagnostic problem (complete recognition).

The aim of the logical analysis can be formulated as follows: To obtain a procedure that, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247043.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247044.png" />, will distinguish the pattern <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247045.png" /> from the pattern <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247046.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247047.png" /> corresponds to a partition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247048.png" /> into classes, then the problem is equivalent to that of placing any given function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247049.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247050.png" /> into the appropriate class. Below, mainly this problem will be discussed. The question as formulated has a trivial solution, given complete knowledge of the table and of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247051.png" />. In actual problems it is possible to obtain information about <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247052.png" />, but at a certain cost. Moreover, for a large class of problems the complete table is either unknown, or so large that one cannot work with it. Hence one is restricted to a certain part of it — a so-called representative sample, and the problem appears in a heuristic form.

3) There turns out to be an admissible way for solving the problem. Suppose some function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247053.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247054.png" /> is unknown. One needs a way of asking questions, by naming certain rows <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247055.png" />, whose answers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247056.png" /> determine to which class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247057.png" /> belongs. The given interrogation can take place either by means of a so-called absolute experiment (cf. [[Automata, experiments with|Automata, experiments with]]), where the questions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247058.png" /> are all asked simultaneously and the answers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247059.png" /> are analyzed, or by means of a more general process, a so-called conditional experiment, where the questions are asked in turn, and each next question is asked dependent on the previous questions and answers (and taking into account the partial order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247060.png" />, if present). A conditional experiment can be represented in the form of an oriented tree, where the vertices represent the questions, the edges represent the answers and the branches represent the outcomes of the experiment. For the following table, three experiments <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247062.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247063.png" /> are presented in Fig. a.

<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"></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247064.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247065.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247066.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247067.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247068.png" /></td> <td colname="2" style="background-color:white;" colspan="1">0</td> <td colname="3" style="background-color:white;" colspan="1">0</td> <td colname="4" style="background-color:white;" colspan="1">1</td> <td colname="5" 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/t/t092/t092470/t09247069.png" /></td> <td colname="2" style="background-color:white;" colspan="1">0</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> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247070.png" /></td> <td colname="2" style="background-color:white;" colspan="1">0</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">1</td> </tr> </tbody> </table>

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

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247071.png" />

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

Figure: t092470a

A system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247072.png" /> of questions and the information necessary for it (answers), enabling one to distinguish the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247073.png" />, is called a test of the initial table.

In the case of an absolute experiment, it is usually understood that a test is a collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247074.png" /> of questions such that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247075.png" /> there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247076.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247077.png" /> (the condition for recognizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247078.png" />). For many-valued (and not-everywhere defined) tables one can replace the predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247079.png" /> by other predicates.

In the case of a conditional experiment, a test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247080.png" /> is an oriented tree obtained from a conditional experiment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247081.png" /> by removing all the final edges, and enabling one to recognize the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247082.png" />. Thus, in the examples given above for the diagnostic problem, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247083.png" /> will be an absolute test; the experiments <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247084.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247085.png" /> yield conditional tests <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247086.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247087.png" />, but the experiment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247088.png" /> does not lead to a conditional test.

For any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247089.png" /> the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247090.png" /> is an absolute test (the trivial test). If a table has large dimensions, then the trivial test leads to a very laborious process of logical analysis. Hence the question arises of constructing simpler tests. For this one defines the notion of complexity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247091.png" /> of a test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247092.png" />. Below some variants of the definition of complexity of an absolute test are given:

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247093.png" />, here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247094.png" /> denotes the  "multiplicity"  of a test, that is, the number of elements in the test;

<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/t/t092/t092470/t09247095.png" /></td> </tr></table>

this measure reflects the  "time"  taken to test a sequential  "sample"  of elements if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247096.png" /> is interpreted as the realization time for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247097.png" />;

<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/t/t092/t092470/t09247098.png" /></td> </tr></table>

here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t09247099.png" /> denotes the test time for a parallel  "sample"  of elements.

Similar complexity characteristics can also be introduced for conditional tests, starting from the corresponding tree, and expressing the number of vertices of the tree, the total length of the tree (the number of edges of the tree) and the maximal length of a branch. If the columns in the table occur with probabilities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470100.png" />, then it is natural to take as a measure of complexity the quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470101.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470102.png" /> is the length of the branch of the tree leading to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470103.png" />. A test for a given table, with control target <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470104.png" /> and the above methods of control and measures of complexity, is called minimal if it has minimal complexity. The construction of minimal tests is a central problem of testing theory. The reasons for this can be demonstrated by the example of an absolute test (where the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470105.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470106.png" /> are not partially ordered). For each table there exists a test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470107.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470108.png" />, and one can describe tables for which this bound is best possible. At the same time, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470109.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470110.png" />, for almost-all tables

<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/t/t092/t092470/t092470111.png" /></td> </tr></table>

in other words, the minimal test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470112.png" /> is simpler than that described above for a wide range of values of the parameters.

There is an abundance of algorithms for the construction of minimal tests. For example, for absolute tests by examination of the subsets of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470113.png" />, and for conditional tests by examination of trees with bounded branches and bounded number of vertices. These algorithms, however, are extremely laborious. It turns out that the construction of minimal tests is connected with the construction of so-called extremal tests. The notion of extremality allows one to select from the set of all tests those which in a certain sense have no redundancy. An absolute test (without <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470114.png" />) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470115.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470116.png" /> for the initial table is called extremal if none of its proper subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470117.png" /> is a test for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470118.png" />. The notion of extremality can be expressed in terms of partitions of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470119.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470120.png" /> be the partition of the columns of the table in which two columns belong to the same class if and only if they agree on questions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470121.png" />. The test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470122.png" /> is extremal if and only if, for any two subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470123.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470124.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470125.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470126.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470127.png" />, there exists a pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470128.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470129.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470130.png" /> but not on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470131.png" />. That is, if and only if the partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470132.png" /> is a subpartition of the partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470133.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470134.png" />. For an extremal test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470135.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470136.png" />. On the other hand, by discarding elements from any test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470137.png" /> one can obtain an extremal test.

For conditional tests (without <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470138.png" />), extremality means that every subsequent element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470139.png" /> is chosen such that, for at least one pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470140.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470141.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470142.png" /> belong to the same component of the partition at the previous stage, but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470143.png" />, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470144.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470145.png" /> now belong to distinct components of the partition.

In the example, the test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470146.png" /> is an absolute extremal test, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470147.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470148.png" /> are conditional extremal tests. The test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470149.png" /> yields a certain  "economy"  of time in comparison to the absolute test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470150.png" />, in as much as it requires only two elements in each diagnostic situation, as opposed to three for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470151.png" />. Generalizing this example, it is easy to construct tables for which the minimal absolute test has length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470152.png" />, but the maximal length of a branch in a conditional test is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470153.png" />. This is the greatest advantage that conditional tests have over absolute tests.

In the case where the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470154.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470155.png" /> are equipped with partial orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470156.png" />, the definition of extremality becomes more complicated. Such a definition exists for tables of automata functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470157.png" />, connected with the diagnostics of automata (cf. also [[Automata, experiments with|Automata, experiments with]]). Here the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470158.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470159.png" /> are words over alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470160.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470161.png" />, and the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470162.png" /> means that the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470163.png" /> is an initial segment of the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470164.png" />. When a word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470165.png" /> is fed into the automaton, then so also are entered all the words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470166.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470167.png" /> (all the initial segments of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470168.png" />). Hence redundancy can arise from this element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470169.png" />. More precisely, an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470170.png" /> is called irreducible if, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470171.png" />, either the transition from the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470172.png" /> to the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470173.png" /> involves one of the pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470174.png" /> which belongs to one of the components of the partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470175.png" />, or one can carry out a special move toward such a partition by way of transition to a new state system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470176.png" />; and for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470177.png" /> the transition definitely involves the partition. It turns out that every word can be made irreducible by discarding particular segments, in such a way that the partition involved is the same as for the original word. The notion of an absolute extremal test is now extended by adding the condition that all the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470178.png" /> be irreducible. The notion of a conditional extremal test has two extra conditions: 1) if the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470179.png" /> is chosen at some stage, then the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470180.png" /> chosen at the following step must follow <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470181.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470182.png" />; and 2) the elements corresponding to extremal vertices of the tree of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470183.png" /> must be irreducible.

The following problems arise in the theory of tests: the construction of effective algorithms for finding various types of tests; the estimation of the number of extremal tests; the classification of tests and tables; and the investigation of the influence of further information about the structure of a table on the complexity of tests and the effectiveness of their construction.

A whole series of diagnostic problems reduces to tabular form.

1) Fault finding in electrical circuits (cf. [[Reliability and inspection of control systems|Reliability and inspection of control systems]]). Here a circuit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470184.png" /> which realizes a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470185.png" /> is being tested. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470186.png" /> consists of all collections <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470187.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470188.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470189.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470190.png" /> consists of the Boolean functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470191.png" /> which characterize the correct and incorrect states of the circuit.

2) Control of automata. Here the table usually has infinitely-many rows (the set of input words is infinite). However, for the control one needs only those words which are initial segments of irreducible words, and the length of such words is bounded by a constant depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470192.png" /> and on the number of states for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470193.png" />. The resulting table is finite.

3) Diagnostic problems in medicine. To obtain diagnoses of certain classes of diseases, one sets up a table with rows corresponding to symptoms, and with columns corresponding to the characteristic collection of significant signs for each disease in the class. If the signs are displayed in discrete form (for example, whether temperature is normal, whether blood pressure is normal, etc.), then one obtains a table of the type described above, whereby if the set of signs is sufficiently large, then the columns are pairwise distinct.

4) Recognition of geometric shapes. Suppose that the squares of a discrete table may contain two symbols: 0 or 1. Each of them can have a specific realization, and they are distinguished from one another by their dimensions and positions (Fig. b). One needs to ask questions about the state of a cell in the table (is it shaded or not?) to find out which symbol to write in it. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470194.png" /> are the numbers of the cells, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470195.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470196.png" /> are all 0 or 1. The value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470197.png" /> is 1 if the square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470198.png" /> is shaded for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470199.png" />, and 0 otherwise.

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

Figure: t092470b

5) Game-theoretic problems. The famous game  "battleships"  actually consists of recognizing the arrangement of the opponent's  "ships"  by successive choices of squares, whereby the partner announces the result of each such choice. Here one can build a table with columns characterizing the variants of arranging the  "ships"  (it is constructed of 0's and 1's, as in the recognition problem). A conditional test would be a way of solving the problem.

6) Minimization of Boolean functions. This reduces to the special test problem in which the table describes the covering of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470200.png" /> (the points at which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470201.png" />) by so-called maximal faces (corresponding to simple implications of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092470/t092470202.png" />).

Many [[Classical combinatorial problems|classical combinatorial problems]] can be thought of as test problems, for example, the travelling-salesman problem, the knapsack problem, and also several problems about finding extrema.

Tests allow one to analyze logical connections between marks, and to introduce measures of the importance of marks. For example, one may say that the importance of a mark is defined to be the ratio of the number of all extremal tests. The establishment of measures of importance of marks is useful in the solution of applied problems for the construction of heuristic algorithms. This approach is used successfully in solving diagnostic problems in geology, economics, medicine, etc.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.V. Yablonskii,   I.A. Chegis,   "On tests for electric circuits"  ''Uspekhi Mat. Nauk'' , '''10''' :  4  (1955)  pp. 182–184  (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">  A.N. Dmitriev,   Yu.I. Zhuravlev,   F.P. Krendelev,   "On mathematical principles of classification of objects and events"  ''Diskretn. Anal.'' , '''7'''  (1966)  pp. 3–15  (In Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B.G. Batchelor,   "Pattern recognition" , Plenum  (1978)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  K.L. Clark,   D.F. Cowell,   "Programs, machines, and computation" , McGraw-Hill  (1976)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  O. Duda,   P.E. Hart,   "Pattern classification and scene analysis" , Wiley  (1973)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.J. Nelson,   "Introduction to automata" , Wiley  (1968)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  B.A. Trakhtenbrot,   Ya.M. Bardzdin',   "Finite automata. Behaviour and synthesis" , North-Holland  (1973)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  K. Weihrauch,   "Computability" , Springer  (1987)</TD></TR></table>