Применение отрицания к сильно связным автоматам

Маслеников Д. О.
Маслеников Денис Олегович
студент каф. математической теории интеллектуальных систем мех.-мат. ф-та МГУ

Получена: 25.03.2026

Опубликована: 2025 год, том 29, выпуск 3, С. 164–179

Скачать полный текст

Аннотация

Вводится понятие результата применения к инициальному автомату функции \( f \), заданной на его выходном алфавите, как минимизированный инициальный автомат, реализующий определённую ограниченно-детерминированную функцию. Найдено достаточное условие его сильной связности. Также введено понятия остова - неинициального автомата без выходной функции - и результата применения функции к нему, как неинициальный аналог предыдущего определения. Рассмотрены результаты применения отрицания к остовам определённого вида. Для результата применения отрицания к сильно связному автомату с входным и выходным алфавитам \( {0,1} \) получены верхняя и нижняя оценки числа состояний, для чего было рассмотрено обобщение понятия пространства циклов на ориентированные графы.

Ключевые слова: конечный инициальный автомат, самомодифицирующийся конечный автомат, диаграмма Мура, граф, пространство циклов.

BibTeX 
@article{IS-Maslenikov2025,
  author  = {Маслеников, Денис Олегович},
  title   = {{Применение отрицания к сильно связным автоматам}},
  journal = {Интеллектуальные системы. Теория и приложения},
  year    = {2025},
  volume  = {29},
  number  = {3},
  pages   = {164--179},
}
AMSBIB 
\RBibitem{IS-Maslenikov2025}
\by Д.\,О.~Маслеников
\paper Применение отрицания к сильно связным автоматам
\jour Интеллектуальные системы. Теория и приложения
\yr 2025
\vol 29
\issue 3
\pages 164--179
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

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

× Issue cover