Gibt es eine Methode zum Nachweis der Nicht-Regelmäßigkeit von String-Transformationen?

Es gibt verschiedene Modelle zum Definieren von Transformationen zwischen Sprachen. Finite-State-Wandler und MSO-definierbare Graphtransformationen über String-Graphen sind die beiden, die ich am besten kenne. Wir wissen, dass 2-Wege-Finite-State-Wandler (die ausdrucksstärker sind als ihre 1-Wege-Gegenstücke) und MSO-definierbare String-Transformationen denselben Satz von Transformationen zusammen mit einigen anderen weniger bekannten Modellen erfassen, die Kombinatoren verwenden. Diese Klasse von Transformationen wird als regulär betrachtet. Daher ist es leicht zu zeigen, dass eine Transformation regulär ist, wenn Sie sie mit einem dieser Modelle beschreiben können.

Gibt es eine einfache Möglichkeit zu sagen, dass eine Transformation außerhalb dieser Klasse liegt? Etwas, das dem Pump-Lemma für reguläre Sprachen oder dem Myhill-Nerode-Theorem ähnelt, aber für String-Transformationen, ist das, wonach ich suche.

Ihre Frage ist nicht ganz genau definiert: Wie erhalten Sie die Transformation, mit der Sie beginnen? Wenn Sie beispielsweise annehmen, dass die Transformation beispielsweise von einer Turing-Maschine gegeben wird, gibt es eindeutig keine algorithmische Möglichkeit, zu entscheiden, ob es sich um eine reguläre Transduktion handelt.

Es scheint jedoch, dass Sie fragen, ob es eine "maschinenunabhängige" Charakterisierung von String-Transduktionen gibt (z. B. Myhill-Nerode).

Obwohl ich eine solche Charakterisierung im Allgemeinen nicht kenne (ich bin mir ziemlich sicher, dass keine solche Charakterisierung bekannt ist), gibt es eine solche Charakterisierung für String-Wandler mit Ursprungsinformationen, die von Bojnaczyk entwickelt wurde.

Sie können hier beginnen.