On restoration of a diagram of automata by its graph
Dmitry Nikolaevich Babin, Roman Andreevich Ishchenko · 2022
If in the transition diagram of an automaton we remove information about the input letters, we get a directed graph. Up to renaming the letters of the input alphabet, we solve the inverse problem restoring the automaton diagram from a digraph. Usually the number solutions turns out to be large, but sometimes it can be done unambiguously. The problem arises to find an algorithm for checking the existence of a solution, and also estimate the number of solutions in the worst case depending on the type automatic transitions.