Geodesic
Identification method for invertible finite state machine with known output function
Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 140-142.

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper presents some simple adaptive identification experiments with a finite state machine (FSM) $A=(X,S,Y,\psi,\varphi)$ taken from an exclusive class of invertible strongly connected deterministic FSM specified by a nondeterministic FSM $R=(X,S,Y,\Psi,\varphi)$ with one or two transition variants. In $R$, a set $S_1$ is a $x/y$-successor of a subset $S_0\subseteq S$ if $S_1=\{s\colon\exists s_0 \in S_0\ (s\in\Psi(x, s_0)\ \\ \varphi(x,s_0)=y)\}$. A successor graph of the FSM $R$ is an oriented graph constructed in the following way. Each non-empty subset $S_0\subseteq S$ is represented by a node $v(S_0)$ of the graph. A node $v(S_0)$ is an end vertex if $|S_0|\le2$. If a node $v(S_0)$ is not an end vertex, then there exists an edge labelled by $x/y$ from this node to a node $v(S_1)$, where $S_1$ is the $x/y$-successor of $S_0$. A node $v(S_0)$ is decidable if it is an end vertex or there exists $x_0$ such that all edges $x_0/y$ direct to decidable nodes. It is proved that if the node $v(S)$ of the successor graph of the FSM $R$ is decidable, then there exists a simple adaptive homing experiment with $A$. This fact results in the following method for identification of $A$. First, construct the successor graph of $R$ and find the decidable nodes in it. Second, if the node $v(S)$ is decidable, then carry out a simple adaptive homing experiment with $A$. At last, execute an identification experiment with $A$ when the initial state of $A$ is known. Methods for producing homing experiments and identification experiments with the initial FSM of an exclusive class are well known.
Keywords: finite state machines, successor graphs, identification experiments. 
@article{PDMA_2017_10_a54,
     author = {A. O. Zhukovskaja and V. N. Trenkaev},
     title = {Identification method for invertible finite state machine with known output function},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {140--142},
     publisher = {mathdoc},
     number = {10},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2017_10_a54/}
}
TY  - JOUR
AU  - A. O. Zhukovskaja
AU  - V. N. Trenkaev
TI  - Identification method for invertible finite state machine with known output function
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2017
SP  - 140
EP  - 142
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2017_10_a54/
LA  - ru
ID  - PDMA_2017_10_a54
ER  - 
%0 Journal Article
%A A. O. Zhukovskaja
%A V. N. Trenkaev
%T Identification method for invertible finite state machine with known output function
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2017
%P 140-142
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2017_10_a54/
%G ru
%F PDMA_2017_10_a54
A. O. Zhukovskaja; V. N. Trenkaev. Identification method for invertible finite state machine with known output function. Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 140-142. http://geodesic.mathdoc.fr/item/PDMA_2017_10_a54/

[1] Gill A., Vvedenie v teoriyu konechnykh avtomatov, Nauka, M., 1966, 272 pp. | MR

[2] Trenkaev V. N., “Realizatsiya shifra Zakrevskogo na osnove perestraivaemogo avtomata”, Prikladnaya diskretnaya matematika, 2010, no. 3, 69–76

[3] Zhukovskaya A. O., Trenkaev V. N., “O prostykh uslovnykh eksperimentakh identifikatsii obratimykh avtomatov nekotorogo klassa”, Prikladnaya diskretnaya matematika. Prilozhenie, 2016, no. 9, 115 | DOI