On the local invertibility of finite state information lossless automata

O. A. Logachev

Prikladnaâ diskretnaâ matematika, no. 1 (2018), pp. 78-93.

Résumé

A Mealy finite automaton $\mathcal M=(A,Q,A,\varphi,\psi)$ with input and output alphabets $A$, state set $Q$, and transition and output functions $\varphi\colon Q\times A\to Q$ and $\psi\colon Q\times A\to A$ respectively is said to be an information lossless automaton (ILA) if a map $\psi_q\colon A\to A$ defined as $\psi_q(a)=\psi(q,a)$ is a permutation on $A$ for any $q$ in $Q$. The ILA $\mathcal M$ is called locally invertible if there exist $u\in A^n$ and $n\in\mathbb N$ such that, for any $x^1=x_1^1x_2^1\dots$, $x^2=x_1^2x_2^2\dots\in A^\infty$, $q^1,q^2\in Q$, $w\in A^m$, $m\in\mathbb N$, and $y\in A^\infty$, the equality $\psi(q^1,x^1)=\psi(q^2,x^2)=wuy$ implies $(x^1_{m+n+1},x^1_{m+n+2},\dots)=x^2_{m+n+1},x^2_{m+n+2},\dots)$. For ILA $\mathcal M$, we define an automaton without outputs $\mathcal B(\mathcal M)=(A,Q,\delta)$ where $\delta(q,b)=\varphi(q,\psi_q^{-1}(b))$, $q\in Q$, and $b\in A$. The automaton $\mathcal B(\mathcal M)$ is called synchronizable if there exist $v\in A^l$, $l\in\mathbb N$, and $q_0\in Q$ such that $\delta(q,v)=q_0$ for any $q\in Q$. Our main results are the following: 1) we have proved that ILA $\mathcal M$ is locally invertible iff the automation $\mathcal B(\mathcal 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.

Détail

Keywords: finite state automaton, information lossless automaton, local invertibility, shift register.

Bibliographie

[1] Gecseq F., Peak I., Algebraic Theory of Automata, Akademiai Kiado, Budapest, 1972, 325 pp. | MR

[2] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. V., Introduction to the Automata Theory, Nauka Publ., Moscow, 1985, 316 pp. (in Russian) | MR

[3] Logachev O. A., Proskurin G. V., Yashchenko V. V., “Local inversion of a finite automaton by means of automata”, Diskr. Mat., 7:2 (1995), 19–33 (in Russian) | MR | Zbl

[4] Logachev O. A., “On the local invertibility of a class of Boolean maps”, Proc. IX Intern. Conf. “Discrete Mathematics and its Applications”, MSU Publ., Moscow, 2007, 440–442 (in Russian)

[5] Cerny J., “Poznamka k homogennym eksperimentoms konecnymi automatamy”, Matematicko-Fizikalny Casopis Slovensk. Akad. Vied., 14:3 (1964), 208–216 (in Slovak) | MR

[6] Laemmel A. E., Rudner B., Study of the Applications of Coding Theory, Report PIBEP-69-034, Politechnic Inst. Brooklyn, N.Y., 1969, 94 pp.

[7] Kloss B. B., “Some properties of noise-immune automata”, Kibernetika, 1988, no. 1, 10–15 (in Russian) | MR

[8] Rystsov I. K., “Return words for solvable automata”, Kibernetika i Sistemnyy Analiz, 1994, no. 6, 21–26 (in Russian) | MR

[9] Pin J., “On two combinatorial problems arising from automata theory”, Ann. Discrete Math., 17 (1983), 535–548 | MR

[10] Volkov M. V., “Synchronizing automata and the Cerny conjecture”, LNCS, 5196, 2008, 11–27 | MR

[11] Yablonskiy S. V., Introduction to Discrete Mathematics, Vysshaya Shkola Publ., Moscow, 2010, 384 pp. (in Russian) | MR