Estimation for an output symbol multiplicity in invertible automata | Applied Discrete Mathematics. Supplement. 2014. № 7.

HomeIssuesEstimation for an output symbol multiplicity in invertible automata | Applied Discrete Mathematics. Supplement. 2014. № 7.

Estimation for an output symbol multiplicity in invertible automata

It is shown that the maximum repetition number for an output symbol in the output table of an invertible automaton with n states and m input symbols is [(n + 1)/2][(n + 2)/2] if [(n + 2)/2] ^ m, or (n - m + 1)m otherwise.

Download file
Counter downloads: 325

Keywords

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

Authors

NameOrganizationE-mail
Katerinskiy D. A.deniskat@isc.tsu.ru
Всего: 1

References

Курмит А. А. Автоматы без потери информации конечного порядка. Рига: Зинатне, 1972.
Tao R. J. Finite automata and application to cryptography. Tsinghua: Springer, 2008.
Estimation for an output symbol multiplicity in invertible automata | Applied Discrete Mathematics. Supplement. 2014. № 7.

Estimation for an output symbol multiplicity in invertible automata | Applied Discrete Mathematics. Supplement. 2014. № 7.