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

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

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



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






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


Моделирование и анализ информационных систем, 2017, том 24, номер 6, страницы 730–742
DOI: https://doi.org/10.18255/1818-1015-2017-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.
Поступила в редакцию: 03.09.2017
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.713
Образец цитирования: Н. Г. Кушик, Н. В. Евтушенко, И. Б. Бурдонов, А. С. Косачев, “К синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматов”, Модел. и анализ информ. систем, 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{https://elibrary.ru/item.asp?id=30730612}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/mais596
  • https://www.mathnet.ru/rus/mais/v24/i6/p730
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Моделирование и анализ информационных систем
    Статистика просмотров:
    Страница аннотации:199
    PDF полного текста:92
    Список литературы:35
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024