Experimental estimates are obtained for the proportion of invertible, weakly invertible and strong invertible finite automata with finite delay. The estimates show that the proportion of the invertible automata is small (about 3 %) for automata with near numbers of states and output symbols and is large (over 80 %) for automata with the number of output symbols being 4 times more than the number of input symbols and 2 times more than the number of states.
Download file
Counter downloads: 143
- Title About invertibility finite automata with finite delay
- Headline About invertibility finite automata with finite delay
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 6 (Приложение)
- Date:
- DOI
Keywords
конечные автоматы, слабая обратимость, обратимость, анализ обратимости, синтез обратных автоматов, доля обратимых автоматов, finite automata, weakly invertibility, invertibility, analysis of invertibility, synthesis of inverse automata, proportion of invertible automataAuthors
References
Богаченко Н. Ф. Применение теоретико-автоматных моделей в криптографии // Математические структуры и моделирование. 2007. Вып. 17. С. 112-120.
Tao R. J. Finite automata and application to cryptography. Tsinghua: Springer, 2008.
About invertibility finite automata with finite delay | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).
Download full-text version
Download fileCounter downloads: 1888