О сложности решения задачи $\alpha$-выразимости в $k$-значной логике

В работе исследуется алгоритмическая сложность задачи распознавания принадлежности функции $k$-значной логики $\alpha$-замыканию системы функций. Понятие $\alpha$-замыкания возникает при исследованиях в теории конечных автоматов и является сужением понятия обычного замыкания. При $k=2$ показано существенное отличие решетки $\alpha$-замкнутых классов от известной решетки замкнутых классов. Это затрудняет построение эффективного алгоритма решения поставленной задачи без глубоких исследований решетки $\alpha$-замкнутых классов в $P_2$ При $k>2$ доказана NP-трудность поставленной задачи.