• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

Квазиуниверсальные инициальные булевы автоматы с константными состояниями

С. 229-232.

Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n>1. Получены точные оценки на максимальное число булевых функций от n фиксированных переменных, реализуемых инициальным булевым автоматом с двумя, тремя и произвольным количеством константных состояний, где n>1. Для автоматов с двумя константными состояниями эта оценка равна 5/8*2^{2^n}, для автоматов с тремя константными состояниями --- 2^{2^n} - 2^n, для автоматов с произвольным количеством состояний --- 2^{2^n} - 2. Автоматы, на которых эти оценки достигаются, называются квазиуниверсальными. Получены необходимые условия на квазиуниверсальные автоматы с двумя и тремя константными состояниями.