Number of Labelings of Definite Automata Graphs
R. A. Ishchenko · Moscow University Mathematics Bulletin · 2022
Abstract The issue concerning the number of possible labelings of directed graph’s edges such that the resulting automation diagram 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.