О порождающих множествах в классе конечных автоматов с линейной функцией выходов

Аннотация

Ранее автором показано, что класс конечных автоматов с одним линейным выходом не является конечно порожденным по операциям ограниченной композиции. Построено его существенно более узкое порождающее множество из сумматора, константы и конъюнкций с задержкой. Для автоматов с не более чем \(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
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover