Reżyserowane multigrafie jako minimalne automaty

Biorąc pod uwagę zwykły język $L$ na alfabecie $A$, jego minimalny deterministyczny automat może być postrzegany jako ukierunkowana połączona multigraf ze stałym stopniem $|A|$i zaznaczony stan początkowy (poprzez zapomnienie etykiet przejść, stanów końcowych). Zachowujemy stan początkowy, ponieważ każdy wierzchołek musi być z niego dostępny.

Czy odwrotność jest prawdziwa? Tj. Otrzymał skierowaną połączoną multigraf$G$ ze stałym stanem wyjściowym i początkowym, tak że każdy wierzchołek jest z niego dostępny, zawsze istnieje język $L$ takie, że $G$ jest podstawowym wykresem minimalnego automatu $L$ ?

Na przykład jeśli $|A|=1$ to prawda, ponieważ wykres musi być „lasso” z prefiksem wielkości $i$ i pętla wielkości $j$i odpowiada minimalnemu automatowi $L=\{a^{i+nj}~|~n\in\mathbb N\}$.

Motywacja pochodzi z pokrewnego problemu napotkanego podczas redukcji rozstrzygalności, w którym rozwiązanie jest łatwiejsze: zaczynając od nieorientowanego prostego wykresu i przy większej liczbie operacji, takich jak dodawanie ujść. Ale zastanawiałem się, czy ktoś już spojrzał na to bardziej naturalne pytanie?

Jedyne, co zdalnie połączone, jakie mogłem znaleźć w literaturze, to artykuły takie jak Złożoność kolorowania dróg za pomocą przepisanych słów resetowania , w których celem jest pokolorowanie takiej multigrafii, aby powstały automat miał słowo synchronizujące. Wydaje się jednak, że minimalizm nie jest brany pod uwagę.

Aktualizacja : Dalsze pytanie po odpowiedzi Klausa Draegera: jaka jest złożoność decyzji, czy wykres ma taki kształt? Możemy odgadnąć etykietowanie i wielomianowo zweryfikować minimalność automatu, więc jest w NP, ale czy możemy powiedzieć więcej?

Dowolny węzeł absorbujący $n$ będzie musiał albo akceptować, albo nie (aby wszystko albo nic nie zostało zaakceptowane raz $n$jest wprowadzony). Jeśli wykres ma więcej niż dwa węzły absorbujące, wówczas niektóre z nich będą równoznaczne z dowolnym wyborem etykietowania i przyjmowania zestawu.

Mówiąc bardziej ogólnie, dla każdego silnie połączonego wykresu $H$ jest tylko skończona liczba $n(H)$różnych możliwych etykiet i akceptacji podzbiorów; jeśli twój wykres ma więcej niż$n(H)$ zaciski silnie połączone elementy równoważne z $H$ (przymocowany do liści drzewa, powiedzmy), nie może odpowiadać żadnemu minimalnemu automatowi.

EDYCJA w odniesieniu do pytania uzupełniającego: To brzmi podchwytliwie. Jedno podejście sugerowane przez mój argument może wyglądać następująco:

• Przegroda $G$w SCC. To jest tanie;$O(|V|+|E|)$ za pomocą algorytmu Tarjana.
• Posortuj SCC w klasy izomorfizmu. Niestety nie wiadomo, czy występuje izomorfizm grafów$P$.
• Dla każdej końcowej klasy izomorfizmu określ liczbę dopuszczalnych odpowiednich podautomatów i zawieść, jeśli nie ma ich wystarczającej liczby. Zauważ, że nie każda kombinacja akceptacji etykiet podzbiorów i krawędzi jest dozwolona: na przykład załóżmy, że jest to nasz alfabet$\{a,b\}$, a komponent ma dwa węzły, każdy z pętlą własną i krawędzią do drugiego węzła. Sprawienie, by oba węzły przyjmowały i oznaczały obie pętle$a$ (a pozostałe krawędzie za pomocą $b$) daje automat, który jest podobny do jednego stanu pochłaniania, naruszając minimalność.
• Podobnie traktuj pozostałe SCC w DAG, biorąc pod uwagę te niższe; Jestem trochę rozmyślny na temat szczegółów tej części.

Jest to jeden krok, którego złożoność jest znana, a drugi, który wygląda na to, może wymagać czasu wykładniczego (ponieważ może istnieć wykładniczo wiele podziałów na klasy podobieństwa, które zostaną wykluczone przy określaniu dopuszczalnych automatów). Czy możemy zrobić lepiej?