Об обратимости конечных автоматов с конечной задержкой | ПДМ. Приложение. 2013. № 6.

Об обратимости конечных автоматов с конечной задержкой

Построены экспериментальные оценки доли обратимых, слабо обратимых и сильно обратимых конечных автоматов с конечной задержкой, из которых следует, что эта доля мала (до 3 %) для автоматов с близкими мощностями их алфавитов состояний и выходных символов и велика (более 80 %) для автоматов, у которых выходной алфавит в 4 раза мощнее входного и в 2 раза — внутреннего.

About invertibility finite automata with finite delay.pdf Рассмотрены автоматы, обратимые с нулевой задержкой, и автоматы, слабо или сильно обратимые с конечной задержкой. В первых функция выходов инъективна в каждом состоянии, во вторых входная последовательность восстанавливается с задержкой по выходной последовательности и начальному состоянию, а в третьих — только по выходной последовательности. Для каждого типа обратимости известны тест обратимости и алгоритм построения обратного автомата [1,2]. В работе сообщается о программной реализации этих тестов и алгоритмов и об экспериментальных оценках доли обратимых автоматов всех типов. Полученные оценки приведены на рис. 1, где на оси абсцисс отмечена доля обратимых автоматов, на оси ординат — значения параметров автоматов, для которых проводилось исследование: m, n и k — мощности соответственно входного, внутреннего и выходного алфавитов автомата. В каждой точке оценки построены усреднением результатов вычислений для 104 примеров случайных автоматов. Результаты для доли обратимых автоматов с нулевой задержкой совпадают с теоретическими, вычисленными по формуле d = (Cm • m!)n kmn Из рис. 1 видно, что: 1) доля обратимых автоматов мала (менее 3%), если мощности входного, внутреннего и выходного алфавитов близки друг к другу или мощности внутреннего и выходного алфавитов меньше мощности входного алфавита; 2) доля обратимых автоматов высока (более 80 %), если мощность выходного алфавита много больше (более чем в 4 раза) мощности входного алфавита и больше (хотя бы в 2 раза) мощности внутреннего алфавита. □ сильно обратимые Н слабо обратимые ЕЭбез задержки Рис. 1. Доля обратимых автоматов

Ключевые слова

конечные автоматы, слабая обратимость, обратимость, анализ обратимости, синтез обратных автоматов, доля обратимых автоматов, finite automata, weakly invertibility, invertibility, analysis of invertibility, synthesis of inverse automata, proportion of invertible automata

Авторы

ФИООрганизацияДополнительноE-mail
Катеринский Денис АркадьевичТомский государственный университетстудент кафедры защиты информации и криптографииdeniskat@isc.tsu.ru
Всего: 1

Ссылки

Богаченко Н. Ф. Применение теоретико-автоматных моделей в криптографии // Математические структуры и моделирование. 2007. Вып. 17. С. 112-120.
Tao R. J. Finite automata and application to cryptography. Tsinghua: Springer, 2008.
 Об обратимости конечных автоматов с конечной задержкой | ПДМ. Приложение. 2013. № 6.

Об обратимости конечных автоматов с конечной задержкой | ПДМ. Приложение. 2013. № 6.