Part 2. Mathematics and Computer Science

On the labelings of abelian automata graphs

R. A. Ishchenko

Lomonosov Moscow State University

Abstract: The author investigates the number of possible labelings of the edges of a strongly connected directed graph so that the resulting Moore diagram corresponds to some abelian automaton. It is proved that in the case of an alphabet of two elements, such a labeling is unique (except for the extreme case), and the algorithm for such a labeling is given. In the case of an alphabet with a larger number of elements the exponential dependence of the maximum number of labelings on the number of vertices is proved.

Keywords: abelian automata, automation diagramm, transition graph, labelings of automation graph, structure of automation graph.