|
Automaton complexity of two-place Boolean bases
A. E. Andreev, A. A. Chasovskikh
Abstract:
The problem on the minimal possible number of states for an automaton
computing values of Boolean expressions of the given length over
different operator bases is considered.
It is established that the set of all the bases falls into three
classes depending on whether the growth of logarithm of the
necessary number of states is constant, logarithmic or linear.
The criteria system of five bases classified in the stated sense is
obtained and the determination of the class of any given set of
operations is performed by checking its inclusion into the bases of
the criteria system.
This allows us to carry out the complete classification of bases of
operations from the considered point of view.
The proofs of the results are given. This work was supported by the Russian Foundation for Basic Research,
grant 95–01–00707.
Received: 23.10.1996
Citation:
A. E. Andreev, A. A. Chasovskikh, “Automaton complexity of two-place Boolean bases”, Diskr. Mat., 8:4 (1996), 123–133; Discrete Math. Appl., 6:6 (1996), 599–610
Linking options:
https://www.mathnet.ru/eng/dm545https://doi.org/10.4213/dm545 https://www.mathnet.ru/eng/dm/v8/i4/p123
|
Statistics & downloads: |
Abstract page: | 432 | Full-text PDF : | 227 | First page: | 3 |
|