Сложность автоматов, вычисляющих значения формул

Рассматривается задача о минимально возможном числе состояний для автомата, вычисляющего значения булевских выражений заданной длины в различных операторных базисах. Установлено, что порядок логарифма необходимого числа состояний может быть константным, логарифмическим или линейным. Проведена полная классификация базисов операций с этой точки зрения.
Библиогр. 4.