EN
Проблема полноты линейных дефинитных автоматов
Молдованов И. В.
Получена: 26.05.2026 Доработана: 03.06.2026 Принята: 05.06.2026
Опубликована: 2026 год, том 30, выпуск 2, С. 120–141
Аннотация
В работе исследуется задача полноты в классе линейных дефинитных автоматов над полем из двух элементов относительно операции суперпозиции. Основным результатом является получение критерия полноты для произвольных подмножеств класса линейных дефинитных автоматов, сформулированного в терминах системы замкнутых классов. Полученный критерий обобщает ранее известные результаты, относящиеся к конечнопорожденным подмножествам, содержащим нулевую константу. На его основе доказывается алгоритмическая разрешимость задачи распознавания полноты конечных подмножеств класса линейных дефинитных автоматов.
Ключевые слова: задача полноты, суперпозиция, линейные автоматы, дефинитные автоматы.
BibTeX
@article{IS-Moldovanov2026,
author = {Молдованов, Илья Владимирович},
title = {{Проблема полноты линейных дефинитных автоматов}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {2},
pages = {120--141},
}
AMSBIB
\RBibitem{IS-Moldovanov2026}
\by И.\,В.~Молдованов
\paper Проблема полноты линейных дефинитных автоматов
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 2
\pages 120--141