Количество разметок графов дефинитных автоматов

В статье исследуется вопрос о количестве возможных разметок ребер ориентированного графа, при котором образованная диаграмма Мура соответствует некоторому дефинитному автомату. Доказано, что в случае сильносвязного графа автомата в алфавите из двух элементов такая разметка единственна. В случае алфавита из большего числа элементов показано, что максимальное количество разметок экспоненциально зависит от количества вершин.