|
К синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматов
Н. Г. Кушикa, Н. В. Евтушенкоbc, И. Б. Бурдоновb, А. С. Косачевb a Университет Телеком Южный Париж / Париж Сакле,
ул. Ш. Фурье, 9, г. Еври, 91000 Франция
b Институт системного программирования РАН, ул. Солженицына, 25, г. Москва
c Томский государственный университет, ул. Ленина, 36, г. Томск, 634050 Россия
Аннотация:
В работе рассматриваются задачи проверки существования и синтеза синхронизирующих и установочных последовательностей для конечных входо-выходных полуавтоматов. Соответствующие последовательности могут быть использованы при идентификации состояния проверяемой системы после подачи подходящей входной последовательности. В модели, исследуемой в работе, действия разделены на входные и выходные, однако отсутствуют выделенные явно семейства начальных и финальных состояний. В статье определяются понятия синхронизирующей и установочной последовательностей и предлагаются методы их синтеза для специального класса входо-выходных полуавтоматов, у которых в каждом состоянии определены переходы или только по входным, или только по выходным действиям; кроме того, в соответствующем графе переходов отсутствуют циклы по выходным символам. Для описанного класса входо-выходных полуавтоматов устанавливаются необходимые и достаточные условия существования синхронизирующих и установочных последовательностей и оценивается длина таких последовательностей. Выделяются подклассы полуавтоматов, для которых худшие (в основном экспоненциальные) оценки сложности не являются достижимыми.
Ключевые слова:
входо-выходные полуавтоматы, синхронизирующая последовательность, установочная последовательность.
Поступила в редакцию: 03.09.2017
Образец цитирования:
Н. Г. Кушик, Н. В. Евтушенко, И. Б. Бурдонов, А. С. Косачев, “К синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматов”, Модел. и анализ информ. систем, 24:6 (2017), 730–742
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais596 https://www.mathnet.ru/rus/mais/v24/i6/p730
|
Статистика просмотров: |
Страница аннотации: | 199 | PDF полного текста: | 92 | Список литературы: | 35 |
|