Разрешимость задачи полноты автоматного базиса в зависимости от его булевой части
Рассматривается проблема полноты систем автоматных функций вида $\Phi\cup \nu$ с операциями суперпозиции и обратной связи, где $\Phi \subseteq P_2$, множество $\nu$ конечно. Решение этой задачи приводит к разделению решетки замкнутых классов Поста на сильные (наличие которых в исследуемой системе гарантирует разрешимость задачи полноты конечных базисов) и слабые (наличие которых в исследуемой системе этого не гарантирует). Оказалось, что классификации базисов по свойству полноты и свойству А-полноты совпадают. В данной статье описана эта классификация.