Geodesic
Number of labelings of definite automata graphs
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2022), pp. 71-75 
R. A. Ishchenko. Number of labelings of definite automata graphs. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2022), pp. 71-75. http://geodesic.mathdoc.fr/item/VMUMM_2022_2_a11/
@article{VMUMM_2022_2_a11,
     author = {R. A. Ishchenko},
     title = {Number of labelings of definite automata graphs},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {71--75},
     year = {2022},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2022_2_a11/}
}
TY  - JOUR
AU  - R. A. Ishchenko
TI  - Number of labelings of definite automata graphs
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2022
SP  - 71
EP  - 75
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2022_2_a11/
LA  - ru
ID  - VMUMM_2022_2_a11
ER  - 
%0 Journal Article
%A R. A. Ishchenko
%T Number of labelings of definite automata graphs
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2022
%P 71-75
%N 2
%U http://geodesic.mathdoc.fr/item/VMUMM_2022_2_a11/
%G ru
%F VMUMM_2022_2_a11

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

The issue concerning the number of possible labelings of directed graph's edges such that the resulting automation diagramm corresponds to a graph of a definite automaton is studied in the paper. It is proved that such a labeling is unique for a strongly-connected graph in an alphabet of two elements. In the case of an alphabet with a larger number of elements, the exponential dependence of the maximal number of labelings on the number of vertices is proved.

[1] Perles M., Rabin M.O., Shamir E., “Theory of definite automata”, IEEE Trans. Electron. Comput., 12 (1963), 233–243 | DOI | MR | Zbl

[2] Ginzburg A., “About some properties of definite, reverse-definite and related automata”, IEEE Trans. Electron. Comput., 15 (1966), 806–810 | DOI | Zbl

[3] Ito M., Duske J., “On cofinal and definite automata”, Acta Cybernetica, 6:2 (1983), 181–189 | MR | Zbl

[4] Zhuk D.N., “O klassifikatsii avtomatnykh bazisov Posta po razreshimosti svoistv A-polnoty dlya definitnykh avtomatov”, Diskretn. matem., 22:2 (2010), 80–95 | Zbl

[5] Ischenko R.A., “O razmetke grafov definitnykh avtomatov”, Vestn. Mosk. un-ta. Matem. Mekhan., 2019, no. 5, 44–48

[6] Babin D.N., “On completeness of the binary bounded determined functions with respect to superposition”, Discrete Math. and Appl., 1:4 (1991), 423–431 | DOI | MR | Zbl

[7] Ischenko R.A., “Otsenka kolichestva razmetok grafov gruppovykh avtomatov”, Intellekt. sistemy, 24:4 (2020), 75–86