Automaton complexity of two-place Boolean bases

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.