HomeIssuesOn the local invertibility of finite state information lossless automata

On the local invertibility of finite state information lossless automata | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 39. DOI: 10.17223/20710410/39/7

A Mealy finite automaton M = (A, Q, A, я: A ^ A defined as фя(a) = ф(д, a) is a permutation on A for any q in Q. The ILA M is called locally invertible if there exist u e An and n e N such that, for any x1 = x\xl,..., x2 = x2x2... e A^, q1 ,q2 e Q, w e Am, m e N, and y e A^, the equality ^q1,x1) = ^q2,x2) = wuy implies (xL+n+l,xL+n+2,...) = (xm+n+i,xm+n+2,...). For ILA M, we define an automaton without outputs B(M) = (A,Q,S) where S(q,b) = ^(q,ф“1(b)), q e Q, and b e A. The automaton B(M) is called synchroniz-able if there exist v e A1, l e N, and q0 e Q such that S(q, v) = q0 for any q e Q. Our main results are the following: 1) we have proved that ILA M is locally invertible iff the automation B(M) is synchronizable, 2) we have constructed some new classes of locally invertible binary shift registers with output functions being some monotonic Boolean functions, namely the nondecreasing (nonincreasing) functions for which the weights of all the minimal (respectively maximal) elements in support are less or more than the half of the number of variables.
Download file
Counter downloads: 210
  • Title On the local invertibility of finite state information lossless automata
  • Headline On the local invertibility of finite state information lossless automata
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 39
  • Date:
  • DOI 10.17223/20710410/39/7
Keywords
конечный автомат, автомат без потери информации, локальная обратимость, регистр сдвига, булева функция, finite state automaton, information lossless automaton, local invertibil-ity, shift register
Authors
References
Gecseq F. and Peak I. Algebraic Theory of Automata. Budapest: Akademiai Kiado, 1972. 325 p.
Кудрявцев В. Б., Алешин С. В., Подколзин А. В. Введение в теорию автоматов. М.: Наука, 1985. 316с.
Логачев О. А., Проскурин Г. В., Ященко В. В. Локальное обращение конечного автомата с помощью автоматов // Дискретная математика. 1995. Т. 7. Вып. 2. С. 19-33.
Логачев О. А. О локальной обратимости одного класса булевых отображений // Материалы IX Междунар. семинара «Дискретная математика и ее приложения». Москва, 18-23 июня 2007 г. М.: Изд-во мех.-мат. факультета МГУ, 2007. С. 440-442.
Cerny J. Poznamka k homogennym eksperimentoms konecnymi automatamy. Matematicko-Fizikalny Casopis Slovensk. Akad. Vied. 1964. V. 14. No.3. P.208-216. (in Slovak)
Laemmel A. E. and Rudner B. Study of the Applications of Coding Theory. Report PIBEP-69-034. Politechnic Inst. Brooklyn, N.Y., 1969. 94p.
Клосс Б. Б. Некоторые свойства помехоустойчивых автоматов // Кибернетика. 1988. № 1. С. 10-15.
Рысцов И. К. Возвратные слова для разрешимых автоматов // Кибернетика и системный анализ. 1994. №6. С. 21-26.
Pin J. On two combinatorial problems arising from automata theory // Ann. Discrete Math. 1983. V. 17. P. 535-548.
Volkov M. V. Synchronizing automata and the Cerny conjecture // LNCS. 2008. V. 5196. P.11-27.
Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2010. 384 с.
On the local invertibility of finite state information lossless automata | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 39. DOI: 10.17223/20710410/39/7
On the local invertibility of finite state information lossless automata | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 39. DOI: 10.17223/20710410/39/7
Download full-text version
Counter downloads: 592