Оценка кратности выходного символа в обратимом автомате | ПДМ. Приложение. 2014. № 7.

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

Доказано, что максимальное количество р повторений некоторого выходного символа в таблице выходов автомата с n состояниями и m входными символами, при котором автомат обратим, вычисляется по формуле р = [(n + 1)/2][(n + 2)/2], если [(n + 2)/2] ^ m, и р = (n - m + 1)m в противном случае.

Estimation for an output symbol multiplicity in invertible automata.pdf Рассматриваются сильно и слабо обратимые конечные автоматы с конечной задержкой. В первых входная последовательность восстанавливается с задержкой по выходной последовательности, во вторых - по выходной последовательности и начальному состоянию [1, 2]. Автомат называется обратимым, если он слабо или сильно обратим. Множество всех обратимых автоматов обозначается Inv. Пусть далее A есть произвольный конечный автомат с n состояниями, m входными символами и с множеством выходных символов Y. Пусть также рА (у) -количество вхождений выходного символа у G Y в таблице выходов автомата A, P(A) = ryeYx{PA(y)} и Р = jrapc P(A). По определению, р есть максимально возможное количество повторений символа в таблице выходов автомата, при котором этот автомат обратим. Теорема 1. n + 1 n + 2 , если n + 2 2 2 2 (n - m + 1)m, если 2 ^ m; р n + 2 > m.

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

конечные автоматы, обратимость, слабая обратимость, сильная обратимость, анализ обратимости, пороговое число обратимости, finite automata, invertibility, weakly invertibility, strongly invertibility, output symbol multiplicity

Авторы

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

Ссылки

Курмит А. А. Автоматы без потери информации конечного порядка. Рига: Зинатне, 1972.
Tao R. J. Finite automata and application to cryptography. Tsinghua: Springer, 2008.
 Оценка кратности выходного символа в обратимом автомате | ПДМ. Приложение. 2014. № 7.

Оценка кратности выходного символа в обратимом автомате | ПДМ. Приложение. 2014. № 7.