О классификации базисов в $P_k$ по разрешимости полноты для автоматов

Рассматривается проблема полноты систем автоматных функций с операциями суперпозиции и обратной связи вида $\Phi \cup \nu$, где $\Phi \subseteq P_k$, $\nu$ — конечно. При $k = 2$ решение этой задачи приводит к разделению решётки замкнутых классов Поста на сильные (наличие которых в исследуемой системе гарантирует разрешимость задачи полноты конечных базисов) и слабые (наличие которых в исследуемой системе этого не гарантирует). При $k = 2$ эта задача для систем автоматных функций произвольного вида была решена (Бабин Д.Н. 1998). В статье рассмотрены следствия и возможные обобщения этой задачи, а также некоторые результаты для $P_k$, $k > 2$.