Ergebnisse zu den von ungerichteten DFAs erkannten Sprachen

Für meine Bachelorarbeit betrachte ich die Klasse von Sprachen, die von symmetrischen DFAs erkannt werden, dh deterministische (vollständige) endliche Automaten, die die folgende Bedingung erfüllen:

Sei ein vollständiger DFA über dem Alphabet . Wenn es für jedes a \ in \ Sigma und jeden Übergang u \ stackrel {a} {\ longrightarrow} v in A einen Übergang v \ stackrel {a} {\ longrightarrow} u in A gibt , nennen wir A einen symmetrischen DFA ( SDFA ). Wenn A nicht vollständig ist, nennen wir es eine partielle SDFA. Wir können ein SDFA auf natürliche Weise als ungerichteten, beschrifteten Graphen betrachten.$A$$\Sigma$$a\in \Sigma$$u \stackrel{a}{\longrightarrow}v$$A$$v \stackrel{a}{\longrightarrow}u$$A$$A$$A$

Ich konnte eine algebraische Charakterisierung der Klasse von Sprachen finden, die von (vollständigen sowie teilweisen) SDFAs erkannt wurden, und einige Schließungseigenschaften ableiten. Weder mir noch meinem Vorgesetzten sind jedoch frühere Ergebnisse in Bezug auf diese bestimmte Klasse regulärer Sprachen bekannt (mit Ausnahme von Ergebnissen wie Reingolds $\mathsf{SL = L}$ die verwandt erscheinen könnten).

Motiviert durch einen Kommentar, dass J.-E. Pin hat eine verwandte Frage weitergegeben, die ich gestellt habe . Meine Frage lautet jetzt:

Gibt es Ergebnisse zu diesen Automaten?

Ich kann nur eine teilweise Antwort geben. Sei die Klasse aller regulären Sprachen, die von einem vollständigen SDFA erkannt werden. Dann ist eine Unterklasse der Klasse der Gruppensprachen. Eine Gruppensprache ist eine Sprache, deren syntaktisches Monoid eine endliche Gruppe ist oder äquivalent von einem endlichen Permutationsautomaten erkannt wird (jeder Buchstabe induziert eine Permutation für die Menge der Zustände). Die Aufnahme ist streng. Das folgende Ergebnis zeigt jedoch, dass eine Art Generator für :$\mathcal{S}$$\mathcal{S}$$\mathcal{G}$$\mathcal{S} \subset \mathcal{G}$$\mathcal{S}$$\mathcal{G}$

Für jede Gruppensprache gibt es ein Alphabet , einen Monoidmorphismus und eine Sprache in so dass .$L \subseteq A^*$$B$$f: A^* \to B^*$$K \subseteq B^*$$\mathcal{S}$$L = f^{-1}(K)$

Beweis . Sei ein Permutationsautomat, der erkennt . Es ist bekannt, dass die Gruppe aller Permutationen auf durch die Menge ihrer Transpositionen erzeugt wird (eine Transposition permutiert zwei Zustände und fixiert alle anderen Zustände). Der Automat ist konstruktionsbedingt ein SDFA und erkennt daher eine Sprache von . Nun gibt es für jeden Buchstaben ein Wort , das in dieselbe Permutation wie definiert$\mathcal{A} = (\{1, ..., n\}, A, \cdot, 1, F)$$L$$\{1, ..., n\}$$B$$\mathcal{B} = (\{1, ..., n\}, B, \cdot, 1, F)$$K$$\mathcal{S}$$a \in A$$u_a \in B^*$$\mathcal{B}$$a$ in . Lassen sein , der durch morphism definiert für jeden Buchstaben . Es sollte nun klar sein , dass .$\mathcal{A}$$f: A^* \to B^*$$f(a) = u_a$$a \in A$$f^{-1}(K) = L$

Die Klasse der von einem partiellen SDFA erkannten Sprachen ist natürlich größer als , erschöpft jedoch nicht die Klasse aller regulären Sprachen. Tatsächlich kann man zeigen, dass wenn in , das syntaktische Monoid von ein inverses Monoid ist und insbesondere seine Idempotenten pendeln. Diese letztere Eigenschaft wird von der etwas größeren Klasse reversibler Automaten geteilt . Sehen$\mathcal{PS}$$\mathcal{S}$$L$$\mathcal{PS}$$L$

J.-É. Pin, Über die Sprachen, die von endlichen reversiblen Automaten akzeptiert werden , in 14. ICALP, Berlin, (1987), 237-249, LNCS 267 , Springer Verlag