О порождающих множествах в классе конечных автоматов с линейной функцией выходов
Получена: 06.11.2026 Принята: 07.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 139–142
Аннотация
Ранее автором показано, что класс конечных автоматов с одним линейным выходом не является конечно порожденным по операциям ограниченной композиции. Построено его существенно более узкое порождающее множество из сумматора, константы и конъюнкций с задержкой. Для автоматов с не более чем \(s\) входами найдено приведенное порождающее множество из трех автоматов, включающее конъюнкцию от \(s+1\) переменной с задержкой, и доказано, что меньшей местности конъюнкции недостаточно. Получена верхняя оценка сложности реализации автоматов схемами из этого множества.
Ключевые слова: конечные автоматы, автоматы с линейной функцией выходов, операции композиции, порождающее множество, сложность реализации.
BibTeX
@article{IS-Yusupov2026,
author = {Юсупов, Феликс Ренатович},
title = {{О порождающих множествах в классе конечных автоматов с линейной функцией выходов}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {139--142},
}
AMSBIB
\RBibitem{IS-Yusupov2026}
\by Ф.\,Р.~Юсупов
\paper О порождающих множествах в классе конечных автоматов с линейной функцией выходов
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 139--142
EN