English
О мощности порождающих множеств в классе автоматов с линейной функцией выходов
Получена: 25.03.2026
Опубликована: 2025 год, том 29, выпуск 4, С. 150–162
Аннотация
Класс конечных автоматов конечно порожден по операциям композиции [1]. Важными его подклассами являются классы автоматов с линейными функциями выходов. Набор операций над автоматами, состоящий из подстановки переменных, подстановки автоматов и обратной связи, мы называем ограниченной композицией. По операциям ограниченной композиции класс одноместных автоматов замкнут. В настоящей работе показано, что в классе одноместных конечных автоматов с линейными функциями выходов и операциями ограниченной композиции отсутствуют конечные полные множества, но автоматы из этого класса, реализуемые схемами с не более чем одной задержкой, порождают этот класс.
Ключевые слова: конечные автоматы, операции композиции для автоматов, конечные автоматы с линейными выходами.
BibTeX
@article{IS-Yusupov2025,
author = {Юсупов, Феликс Ренатович},
title = {{О мощности порождающих множеств в классе автоматов с линейной функцией выходов}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2025},
volume = {29},
number = {4},
pages = {150--162},
}
AMSBIB
\RBibitem{IS-Yusupov2025}
\by Ф.\,Р.~Юсупов
\paper О мощности порождающих множеств в классе автоматов с линейной функцией выходов
\jour Интеллектуальные системы. Теория и приложения
\yr 2025
\vol 29
\issue 4
\pages 150--162