RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2016, выпуск 9, страница 115 (Mi pdma305)

Эта публикация цитируется в 1 статье

Прикладная теория автоматов и графов

О простых условных экспериментах идентификации обратимых автоматов некоторого класса

А. О. Жуковская, В. Н. Тренькаев

Кафедра защиты информации и криптографии Национального исследовательского Томского государственного университета, г. Томск

Аннотация: Рассматривается класс сильносвязных автоматов, получаемых из некоторого инициального обратимого автомата с $m$ состояниями, $n$ входными и $n$ выходными символами путём изменения его функции переходов в зависимости от ключа. Показывается существование простого условного эксперимента, идентифицирующего автоматы в этом классе и имеющего длину не более $mn(m+3)/2$.

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

УДК: 519.713.4

DOI: 10.17223/2226308X/9/45



© МИАН, 2024