Алгоритмическая разрешимость задачи полноты конечных содержащих константу ноль множеств в классе линейных дефинитных автоматов

Аннотация

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