Автоматная сложность двуместных булевых базисов

Рассматривается задача о минимально возможном числе состояний для автомата, вычисляющего значения булевых выражений заданной длины в различных операторных базисах. Установлено, что множество всех базисов распадается на три класса, в зависимости от порядка роста логарифма необходимого числа состояний: константного, логарифмического или линейного. Получена критериальная система из пяти базисов, каждый из которых классифицирован в указанном смысле, а определение класса любого заданного множества операций осуществляется проверкой включения в базисы критериальной системы. Это позволило провести полную классификацию базисов операций с рассматриваемой точки зрения. В работе приводится доказательство полученных результатов.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант 95–01–00707.