Geodesic
Automaton complexity of two-place Boolean bases
Diskretnaya Matematika, Tome 8 (1996) no. 4, pp. 123-133 
A. E. Andreev; A. A. Chasovskikh. Automaton complexity of two-place Boolean bases. Diskretnaya Matematika, Tome 8 (1996) no. 4, pp. 123-133. http://geodesic.mathdoc.fr/item/DM_1996_8_4_a9/
@article{DM_1996_8_4_a9,
     author = {A. E. Andreev and A. A. Chasovskikh},
     title = {Automaton complexity of two-place {Boolean} bases},
     journal = {Diskretnaya Matematika},
     pages = {123--133},
     year = {1996},
     volume = {8},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1996_8_4_a9/}
}
TY  - JOUR
AU  - A. E. Andreev
AU  - A. A. Chasovskikh
TI  - Automaton complexity of two-place Boolean bases
JO  - Diskretnaya Matematika
PY  - 1996
SP  - 123
EP  - 133
VL  - 8
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_1996_8_4_a9/
LA  - ru
ID  - DM_1996_8_4_a9
ER  - 
%0 Journal Article
%A A. E. Andreev
%A A. A. Chasovskikh
%T Automaton complexity of two-place Boolean bases
%J Diskretnaya Matematika
%D 1996
%P 123-133
%V 8
%N 4
%U http://geodesic.mathdoc.fr/item/DM_1996_8_4_a9/
%G ru
%F DM_1996_8_4_a9

Voir la notice de l'article provenant de la source Math-Net.Ru

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.