Направленные мультиграфы как минимальные автоматы

Для регулярного языка на алфавите его минимальный детерминированный автомат можно рассматривать как ориентированный связный мультиграф с постоянной степенью outи отмеченное начальное состояние (забывая метки переходов, конечные состояния). Мы сохраняем исходное состояние, потому что каждая вершина должна быть доступна из него.$L$$A$$|A|$

Верно ли обратное? Т.е. для заданного связного мультиграфа с постоянной степенью out и начальным состоянием, так что из него доступна каждая вершина, всегда ли существует язык такой, что является базовым графом минимального автомата в ?$G$$L$$G$$L$

Например, если это правда, поскольку граф должен быть «лассо» с префиксом размера и циклом размера и соответствовать минимальному автомату .$|A|=1$$i$$j$$L=\{a^{i+nj}~|~n\in\mathbb N\}$

Мотивация проистекает из связанной проблемы, возникающей при снижении разрешимости, где решение проще: начиная с неориентированного простого графа и с большим количеством операций, таких как добавление приемников. Но мне было интересно, если кто-то уже посмотрел на этот более естественный вопрос?

Единственные вещи, которые я мог найти в литературе, - это « Сложность окраски дорог с предписанными словами сброса» , цель которой - раскрасить такой мультиграф, чтобы у получающегося автомата было слово синхронизации. Однако минимальность, похоже, не учитывается.

Обновление : дополнительный вопрос после ответа Клауса Дрегера: какова сложность решения, имеет ли график эту форму? Мы можем угадать маркировку и полиномиально проверить минимальность автомата, так что это в NP, но можем ли мы сказать больше?

Любой поглощающий узел должен либо принимать, либо нет (чтобы все или ничего не принималось после ввода ). Если граф имеет более двух поглощающих узлов, то некоторые из них в конечном итоге будут эквивалентны для любого выбора маркировки и принятия набора.$n$$n$

В более общем случае для любого сильно связного графа существует только конечное число различных возможных разметок и принимающих подмножеств; если ваш граф имеет более чем терминальных сильно связных компонент, эквивалентных (скажем, прикрепленных на листьях дерева), он не может соответствовать ни одному минимальному автомату.$H$$n(H)$$n(H)$$H$

РЕДАКТИРОВАТЬ, в отношении последующего вопроса: это звучит сложно. Один подход, предложенный моим аргументом, может выглядеть так:

• Разделение на ГТК. Это дешево; с использованием алгоритма Тарьяна.$G$$O(|V|+|E|)$
• Сортировка SCCs по классам изоморфизма. К сожалению , изоморфизм графов, не известно, что в .$P$
• Для каждого класса терминальных изоморфизмов определите число допустимых соответствующих автоматов и произведите сбой, если их недостаточно. Обратите внимание, что не каждая комбинация принятия меток подмножества и ребер допустима: например, предположим, что наш алфавит равен , а компонент имеет два узла, каждый из которых имеет самоконтроль и ребро для другого узла. Изготовление оба узла приема и маркировок как петли с (и другими ребрами с ) дает автомат , который bisimilar к одному поглощающему состоянию, нарушив минимальность.$\{a,b\}$$a$$b$
• Обращайтесь с остальными SCC в DAG аналогично, принимая во внимание нижние; Я немного неясен в деталях этой части.

Это один шаг, сложность которого, как известно, очевидна, а другой, который выглядит так, как будто это может потребовать экспоненциального времени (поскольку может быть экспоненциально много разделений на классы бисходства, которые должны быть исключены при определении допустимых автоматов). Можем ли мы сделать лучше?