RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Модел. и анализ информ. систем, 2017, том 24, номер 6, страницы 730–742 (Mi mais596)  

К синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматов

Н. Г. Кушикa, Н. В. Евтушенкоbc, И. Б. Бурдоновb, А. С. Косачевb

a Университет Телеком Южный Париж / Париж Сакле, ул. Ш. Фурье, 9, г. Еври, 91000 Франция
b Институт системного программирования РАН, ул. Солженицына, 25, г. Москва
c Томский государственный университет, ул. Ленина, 36, г. Томск, 634050 Россия

Аннотация: В работе рассматриваются задачи проверки существования и синтеза синхронизирующих и установочных последовательностей для конечных входо-выходных полуавтоматов. Соответствующие последовательности могут быть использованы при идентификации состояния проверяемой системы после подачи подходящей входной последовательности. В модели, исследуемой в работе, действия разделены на входные и выходные, однако отсутствуют выделенные явно семейства начальных и финальных состояний. В статье определяются понятия синхронизирующей и установочной последовательностей и предлагаются методы их синтеза для специального класса входо-выходных полуавтоматов, у которых в каждом состоянии определены переходы или только по входным, или только по выходным действиям; кроме того, в соответствующем графе переходов отсутствуют циклы по выходным символам. Для описанного класса входо-выходных полуавтоматов устанавливаются необходимые и достаточные условия существования синхронизирующих и установочных последовательностей и оценивается длина таких последовательностей. Выделяются подклассы полуавтоматов, для которых худшие (в основном экспоненциальные) оценки сложности не являются достижимыми.

Ключевые слова: входо-выходные полуавтоматы, синхронизирующая последовательность, установочная последовательность.

Финансовая поддержка Номер гранта
Российский научный фонд 16-49-03012
Российский фонд фундаментальных исследований 17-07-00682_а
Работа частично поддержана проектами РНФ № 16-49-03012 и РФФИ № 17-07-00682.


DOI: https://doi.org/10.18255/1818-1015-2017-6-730-742

Полный текст: PDF файл (548 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.713
Поступила в редакцию: 03.09.2017

Образец цитирования: Н. Г. Кушик, Н. В. Евтушенко, И. Б. Бурдонов, А. С. Косачев, “К синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматов”, Модел. и анализ информ. систем, 24:6 (2017), 730–742

Цитирование в формате AMSBIB
\RBibitem{KusEvtBur17}
\by Н.~Г.~Кушик, Н.~В.~Евтушенко, И.~Б.~Бурдонов, А.~С.~Косачев
\paper К синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматов
\jour Модел. и анализ информ. систем
\yr 2017
\vol 24
\issue 6
\pages 730--742
\mathnet{http://mi.mathnet.ru/mais596}
\crossref{https://doi.org/10.18255/1818-1015-2017-6-730-742}
\elib{http://elibrary.ru/item.asp?id=30730612}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais596
  • http://mi.mathnet.ru/rus/mais/v24/i6/p730

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:47
    Полный текст:14
    Литература:12

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018