|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2022, Number 2, Pages 71–75
(Mi vmumm4465)
|
|
|
|
Short notes
Number of labelings of definite automata graphs
R. A. Ishchenko Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
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.
Key words:
definite automata, automation diagramm, transition graph, labelings of automation graph, structure of automation graph.
Received: 28.07.2021
Citation:
R. A. Ishchenko, “Number of labelings of definite automata graphs”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2022, no. 2, 71–75; Moscow University Mathematics Bulletin, 77:2 (2022), 102–107
Linking options:
https://www.mathnet.ru/eng/vmumm4465 https://www.mathnet.ru/eng/vmumm/y2022/i2/p71
|
Statistics & downloads: |
Abstract page: | 39 | Full-text PDF : | 10 | References: | 21 | First page: | 2 |
|