On the local invertibility of finite state information lossless automata

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.