Czy istnieje metoda udowodnienia nieregularności transformacji łańcucha?

Istnieje wiele różnych modeli definiowania transformacji między językami. Przetworniki stanu skończonego i transformacje grafu definiowane przez MSO na grafach łańcuchowych to dwa, z którymi najlepiej się znam. Wiemy, że dwudrożne przetworniki stanu skończonego (które są bardziej ekspresyjne niż ich jednokierunkowe odpowiedniki) i transformacje ciągów definiowane przez MSO przechwytują ten sam zestaw transformacji wraz z niektórymi mniej znanymi modelami, które wykorzystują kombinatory. Ta klasa transformacji jest uważana za regularną, dlatego łatwo jest wykazać, że transformacja jest regularna, jeśli możesz podać jej opis za pomocą jednego z tych modeli.

Czy istnieje prosty sposób na stwierdzenie, że transformacja jest poza tą klasą? Coś podobnego do lematu pompowania dla zwykłych języków lub twierdzenia Myhill-Nerode, ale dla transformacji łańcuchów jest tym, czego szukam.

Twoje pytanie nie jest do końca dobrze określone: ​​w jaki sposób otrzymujesz transformację, od której zaczynasz? Na przykład, jeśli założymy, że transformacja jest wykonywana np. Przez maszynę Turinga, to oczywiście nie ma algorytmicznego sposobu decydowania, czy jest to zwykła transdukcja.

Wydaje się jednak, że pytasz, czy istnieje jakaś „niezależna od maszyny” charakterystyka transdukcji łańcuchów (np. Myhill-Nerode).

Chociaż ogólnie nie znam takiej charakterystyki (jestem prawie pewien, że taka charakterystyka nie jest znana), istnieje taka charakterystyka przetworników strunowych z informacjami o pochodzeniu, opracowana przez Bojnaczyka.

Możesz zacząć tutaj.