Namespaces
Variants
Actions

Difference between revisions of "Automata, minimization of"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
a0140701.png
 +
$#A+1 = 46 n = 0
 +
$#C+1 = 46 : ~/encyclopedia/old_files/data/A014/A.0104070 Automata, minimization of
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
Minimization of the parameter values of automata which results in equivalent and, in a sense, optimal automata. The problem of minimization of automata arises during the synthesis of automata, and its specific nature will depend on the approach adopted in the study of the problem.
 
Minimization of the parameter values of automata which results in equivalent and, in a sense, optimal automata. The problem of minimization of automata arises during the synthesis of automata, and its specific nature will depend on the approach adopted in the study of the problem.
  
If the macro-approach is adopted, the usual procedure is to minimize the number of states of automata, thus obtaining minimal or reduced automata. The actual method of search for reduced automata will depend on the form in which they are defined and on their type of behaviour. If, for example, the behaviour of a finite automaton (cf. [[Automaton, finite|Automaton, finite]]), defined with the aid of, for example, a transition diagram, is understood to mean the system of finitely-determined functions (cf. [[Finitely-determined function|Finitely-determined function]]) realized by the automaton, the minimal finite automaton equivalent to the initial automaton can be effectively found. This is based on Moore's theorem, according to which it may be established by an experiment of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a0140701.png" /> whether or not two states of an automaton with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a0140702.png" /> states are distinguishable from one another. The minimization algorithm consists of constructing an automaton as defined above whose states correspond to the classes of indistinguishable states of the initial automaton, whereas the transition and the output functions are defined by means of representatives of these classes. The minimal automaton is unique up to a state-isomorphism. If the final automaton is considered as an acceptor representing — by means of the subset of isolated states — an event described with the aid of the given regular expression, the minimal automaton is effectively constructed, and the algorithm of its construction may be divided into two stages. In its first stage, the initial regular expression is used to construct some automaton, not necessarily minimal, representing the corresponding regular event. Such an automaton may be constructed, for example, by induction from the operations of union <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a0140703.png" />, concatenation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a0140704.png" /> and iteration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a0140705.png" /> which are included in the regular expression. The automata <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a0140706.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a0140707.png" /> which represent, respectively, the events <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a0140708.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a0140709.png" /> serve to effect the special constructions of the automata <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407011.png" /> which represent the events <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407014.png" />; moreover, the number of states of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407015.png" /> does not exceed the product of the number of states of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407017.png" />; the number of states of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407018.png" /> does, generally, not exceed the product of the number of states of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407019.png" /> with the number of all subsets of the set of states of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407020.png" />; while the number of states of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407021.png" /> does not exceed the number of subsets of the set of states of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407022.png" />. During the second stage of the algorithm the number of states of the resulting automaton is minimized in the usual way, the classes of indistinguishable final states of the initial automaton corresponding to the final states of the minimal automaton. The minimal automaton representing a given super-event is constructed in the same manner. There are unique (up to a state-isomorphism) minimal automata which represent given events and super-events.
+
If the macro-approach is adopted, the usual procedure is to minimize the number of states of automata, thus obtaining minimal or reduced automata. The actual method of search for reduced automata will depend on the form in which they are defined and on their type of behaviour. If, for example, the behaviour of a finite automaton (cf. [[Automaton, finite|Automaton, finite]]), defined with the aid of, for example, a transition diagram, is understood to mean the system of finitely-determined functions (cf. [[Finitely-determined function|Finitely-determined function]]) realized by the automaton, the minimal finite automaton equivalent to the initial automaton can be effectively found. This is based on Moore's theorem, according to which it may be established by an experiment of length $  n - 1 $
 +
whether or not two states of an automaton with $  n $
 +
states are distinguishable from one another. The minimization algorithm consists of constructing an automaton as defined above whose states correspond to the classes of indistinguishable states of the initial automaton, whereas the transition and the output functions are defined by means of representatives of these classes. The minimal automaton is unique up to a state-isomorphism. If the final automaton is considered as an acceptor representing — by means of the subset of isolated states — an event described with the aid of the given regular expression, the minimal automaton is effectively constructed, and the algorithm of its construction may be divided into two stages. In its first stage, the initial regular expression is used to construct some automaton, not necessarily minimal, representing the corresponding regular event. Such an automaton may be constructed, for example, by induction from the operations of union $  \cup $,  
 +
concatenation $  \circ $
 +
and iteration $  * $
 +
which are included in the regular expression. The automata $  \mathfrak A _ {1} , \mathfrak A _ {2} $
 +
and $  \mathfrak A _ {3} $
 +
which represent, respectively, the events $  R _ {1} , R _ {2} $
 +
and $  R _ {3} $
 +
serve to effect the special constructions of the automata $  \mathfrak A _ {4} , \mathfrak A _ {5} $
 +
and $  \mathfrak A _ {6} $
 +
which represent the events $  R _ {1} \cup R _ {2} $,  
 +
$  R _ {1} \circ R _ {2} $
 +
and $  R _ {3}  ^ {*} $;  
 +
moreover, the number of states of $  \mathfrak A _ {4} $
 +
does not exceed the product of the number of states of $  \mathfrak A _ {1} $
 +
and $  \mathfrak A _ {2} $;  
 +
the number of states of $  \mathfrak A _ {5} $
 +
does, generally, not exceed the product of the number of states of $  \mathfrak A _ {1} $
 +
with the number of all subsets of the set of states of $  \mathfrak A _ {2} $;  
 +
while the number of states of $  \mathfrak A _ {6} $
 +
does not exceed the number of subsets of the set of states of $  \mathfrak A _ {3} $.  
 +
During the second stage of the algorithm the number of states of the resulting automaton is minimized in the usual way, the classes of indistinguishable final states of the initial automaton corresponding to the final states of the minimal automaton. The minimal automaton representing a given super-event is constructed in the same manner. There are unique (up to a state-isomorphism) minimal automata which represent given events and super-events.
  
 
A reduced automaton, which is unique up to a state-isomorphism, also exists for non-deterministic finite automata, and for both deterministic and non-deterministic infinite automata. In the former case, this automaton is found using a method similar to that in the case of finite automata discussed above, while in the second case its construction is, as a rule, non-effective. For a stochastic automaton with a finite number of states there exists, generally speaking, a continuum of various reduced automata are equivalent to the initial automaton. This is why there is no effective way of describing the set of reduced automata derived from a given stochastic automaton.
 
A reduced automaton, which is unique up to a state-isomorphism, also exists for non-deterministic finite automata, and for both deterministic and non-deterministic infinite automata. In the former case, this automaton is found using a method similar to that in the case of finite automata discussed above, while in the second case its construction is, as a rule, non-effective. For a stochastic automaton with a finite number of states there exists, generally speaking, a continuum of various reduced automata are equivalent to the initial automaton. This is why there is no effective way of describing the set of reduced automata derived from a given stochastic automaton.
  
In the micro-approach to the study of finite automata, a given automaton is constructed starting from some finite selection of a basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407023.png" /> of logical networks. Given an automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407024.png" />, defined, for example, by canonical equations, it is required to exhibit a logical network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407025.png" />, constructed from the elements of the basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407026.png" /> using superposition and feedback operations, realizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407027.png" /> and containing a minimum number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407028.png" /> of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407029.png" /> necessary for the realization of this automaton. In this sense the network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407030.png" /> will be the optimal scheme of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407031.png" />. In the general case, the problem of realizing an arbitrary automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407032.png" /> with the aid of networks over a basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407033.png" /> is unsolvable, and for this reason the complexity function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407034.png" /> of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407035.png" /> cannot be calculated. If a basis of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407036.png" /> is known to be complete (cf. [[Automata, complete systems of|Automata, complete systems of]]), the construction of any optimal network for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407037.png" /> can be effectively realized e.g. in the following manner. It is known that the realizability check of an automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407038.png" /> with the aid of a given network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407039.png" /> can be effectively established. Moreover, for a given number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407040.png" /> the number of networks over a base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407041.png" /> of complexity at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407042.png" /> can be calculated, and all these networks can be effectively constructed. Therefore, a sequential inspection of all networks of complexity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407043.png" /> for the realizability of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407044.png" /> may be used as the algorithm for constructing all optimal networks for a given automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407045.png" />. The problem of the behaviour of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014070/a01407046.png" /> and of certain of its generalizations is part of the general problem of synthesis of automata. There exist several heuristic algorithms for the synthesis of minimal schemes for automata, based on the special properties of the bases and on specific interpretations of the concept of optimality. For references see [[Automaton, finite|Automaton, finite]].
+
In the micro-approach to the study of finite automata, a given automaton is constructed starting from some finite selection of a basis $  \mathfrak B $
 +
of logical networks. Given an automaton $  \mathfrak A $,  
 +
defined, for example, by canonical equations, it is required to exhibit a logical network $  S $,  
 +
constructed from the elements of the basis $  \mathfrak B $
 +
using superposition and feedback operations, realizing $  \mathfrak A $
 +
and containing a minimum number $  L ( \mathfrak A ) $
 +
of elements of $  \mathfrak B $
 +
necessary for the realization of this automaton. In this sense the network $  S $
 +
will be the optimal scheme of the automaton $  \mathfrak A $.  
 +
In the general case, the problem of realizing an arbitrary automaton $  \mathfrak A $
 +
with the aid of networks over a basis $  \mathfrak B $
 +
is unsolvable, and for this reason the complexity function $  L ( \mathfrak A ) $
 +
of the automaton $  \mathfrak A $
 +
cannot be calculated. If a basis of $  \mathfrak A $
 +
is known to be complete (cf. [[Automata, complete systems of|Automata, complete systems of]]), the construction of any optimal network for $  \mathfrak A $
 +
can be effectively realized e.g. in the following manner. It is known that the realizability check of an automaton $  \mathfrak A $
 +
with the aid of a given network $  S $
 +
can be effectively established. Moreover, for a given number $  l $
 +
the number of networks over a base $  \mathfrak B $
 +
of complexity at most $  l $
 +
can be calculated, and all these networks can be effectively constructed. Therefore, a sequential inspection of all networks of complexity $  1 \dots L ( \mathfrak A ) $
 +
for the realizability of the automaton $  \mathfrak A $
 +
may be used as the algorithm for constructing all optimal networks for a given automaton $  \mathfrak A $.  
 +
The problem of the behaviour of the function $  L ( \mathfrak A ) $
 +
and of certain of its generalizations is part of the general problem of synthesis of automata. There exist several heuristic algorithms for the synthesis of minimal schemes for automata, based on the special properties of the bases and on specific interpretations of the concept of optimality. For references see [[Automaton, finite|Automaton, finite]].

Latest revision as of 18:49, 5 April 2020


Minimization of the parameter values of automata which results in equivalent and, in a sense, optimal automata. The problem of minimization of automata arises during the synthesis of automata, and its specific nature will depend on the approach adopted in the study of the problem.

If the macro-approach is adopted, the usual procedure is to minimize the number of states of automata, thus obtaining minimal or reduced automata. The actual method of search for reduced automata will depend on the form in which they are defined and on their type of behaviour. If, for example, the behaviour of a finite automaton (cf. Automaton, finite), defined with the aid of, for example, a transition diagram, is understood to mean the system of finitely-determined functions (cf. Finitely-determined function) realized by the automaton, the minimal finite automaton equivalent to the initial automaton can be effectively found. This is based on Moore's theorem, according to which it may be established by an experiment of length $ n - 1 $ whether or not two states of an automaton with $ n $ states are distinguishable from one another. The minimization algorithm consists of constructing an automaton as defined above whose states correspond to the classes of indistinguishable states of the initial automaton, whereas the transition and the output functions are defined by means of representatives of these classes. The minimal automaton is unique up to a state-isomorphism. If the final automaton is considered as an acceptor representing — by means of the subset of isolated states — an event described with the aid of the given regular expression, the minimal automaton is effectively constructed, and the algorithm of its construction may be divided into two stages. In its first stage, the initial regular expression is used to construct some automaton, not necessarily minimal, representing the corresponding regular event. Such an automaton may be constructed, for example, by induction from the operations of union $ \cup $, concatenation $ \circ $ and iteration $ * $ which are included in the regular expression. The automata $ \mathfrak A _ {1} , \mathfrak A _ {2} $ and $ \mathfrak A _ {3} $ which represent, respectively, the events $ R _ {1} , R _ {2} $ and $ R _ {3} $ serve to effect the special constructions of the automata $ \mathfrak A _ {4} , \mathfrak A _ {5} $ and $ \mathfrak A _ {6} $ which represent the events $ R _ {1} \cup R _ {2} $, $ R _ {1} \circ R _ {2} $ and $ R _ {3} ^ {*} $; moreover, the number of states of $ \mathfrak A _ {4} $ does not exceed the product of the number of states of $ \mathfrak A _ {1} $ and $ \mathfrak A _ {2} $; the number of states of $ \mathfrak A _ {5} $ does, generally, not exceed the product of the number of states of $ \mathfrak A _ {1} $ with the number of all subsets of the set of states of $ \mathfrak A _ {2} $; while the number of states of $ \mathfrak A _ {6} $ does not exceed the number of subsets of the set of states of $ \mathfrak A _ {3} $. During the second stage of the algorithm the number of states of the resulting automaton is minimized in the usual way, the classes of indistinguishable final states of the initial automaton corresponding to the final states of the minimal automaton. The minimal automaton representing a given super-event is constructed in the same manner. There are unique (up to a state-isomorphism) minimal automata which represent given events and super-events.

A reduced automaton, which is unique up to a state-isomorphism, also exists for non-deterministic finite automata, and for both deterministic and non-deterministic infinite automata. In the former case, this automaton is found using a method similar to that in the case of finite automata discussed above, while in the second case its construction is, as a rule, non-effective. For a stochastic automaton with a finite number of states there exists, generally speaking, a continuum of various reduced automata are equivalent to the initial automaton. This is why there is no effective way of describing the set of reduced automata derived from a given stochastic automaton.

In the micro-approach to the study of finite automata, a given automaton is constructed starting from some finite selection of a basis $ \mathfrak B $ of logical networks. Given an automaton $ \mathfrak A $, defined, for example, by canonical equations, it is required to exhibit a logical network $ S $, constructed from the elements of the basis $ \mathfrak B $ using superposition and feedback operations, realizing $ \mathfrak A $ and containing a minimum number $ L ( \mathfrak A ) $ of elements of $ \mathfrak B $ necessary for the realization of this automaton. In this sense the network $ S $ will be the optimal scheme of the automaton $ \mathfrak A $. In the general case, the problem of realizing an arbitrary automaton $ \mathfrak A $ with the aid of networks over a basis $ \mathfrak B $ is unsolvable, and for this reason the complexity function $ L ( \mathfrak A ) $ of the automaton $ \mathfrak A $ cannot be calculated. If a basis of $ \mathfrak A $ is known to be complete (cf. Automata, complete systems of), the construction of any optimal network for $ \mathfrak A $ can be effectively realized e.g. in the following manner. It is known that the realizability check of an automaton $ \mathfrak A $ with the aid of a given network $ S $ can be effectively established. Moreover, for a given number $ l $ the number of networks over a base $ \mathfrak B $ of complexity at most $ l $ can be calculated, and all these networks can be effectively constructed. Therefore, a sequential inspection of all networks of complexity $ 1 \dots L ( \mathfrak A ) $ for the realizability of the automaton $ \mathfrak A $ may be used as the algorithm for constructing all optimal networks for a given automaton $ \mathfrak A $. The problem of the behaviour of the function $ L ( \mathfrak A ) $ and of certain of its generalizations is part of the general problem of synthesis of automata. There exist several heuristic algorithms for the synthesis of minimal schemes for automata, based on the special properties of the bases and on specific interpretations of the concept of optimality. For references see Automaton, finite.

How to Cite This Entry:
Automata, minimization of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automata,_minimization_of&oldid=45253
This article was adapted from an original article by V.A. Buevich (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article