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: 119
- Title Estimation for an output symbol multiplicity in invertible automata
- Headline Estimation for an output symbol multiplicity in invertible automata
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 7 (Приложение)
- Date:
- DOI
Keywords
конечные автоматы, обратимость, слабая обратимость, сильная обратимость, анализ обратимости, пороговое число обратимости, finite automata, invertibility, weakly invertibility, strongly invertibility, output symbol multiplicityAuthors
References
Tao R. J. Finite automata and application to cryptography. Tsinghua: Springer, 2008.
Курмит А. А. Автоматы без потери информации конечного порядка. Рига: Зинатне, 1972.
Estimation for an output symbol multiplicity in invertible automata | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 7 (Приложение).
Download full-text version
Counter downloads: 1920