Проблема полноты в классе линейных дефинитных автоматов
Получена: 08.11.2026 Доработана: 09.11.2026 Принята: 10.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 112–116
Аннотация
В работе исследуются задачи полноты в классе линейных дефинитных автоматов над полем из двух элементов. Для аппроксимационной полноты и полноты относительно суперпозиции описаны приведенные критериальные системы замкнутых классов. На их основе также устанавливается алгоритмическая разрешимость проверки обоих видов полноты конечных систем.
Ключевые слова: линейные дефинитные автоматы, аппроксимационная полнота, суперпозиция.
BibTeX
@article{IS-Moldovanov2026,
author = {Молдованов, Илья Владимирович},
title = {{Проблема полноты в классе линейных дефинитных автоматов}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {112--116},
}
AMSBIB
\RBibitem{IS-Moldovanov2026}
\by И.\,В.~Молдованов
\paper Проблема полноты в классе линейных дефинитных автоматов
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 112--116
Опубликовано на условиях лицензии
Creative Commons Attribution 4.0 International (CC BY 4.0)
EN