Existe-t-il une méthode pour prouver la non-régularité des transformations de chaînes?

Il existe un certain nombre de modèles différents pour définir les transformations entre les langues. Les transducteurs à états finis et les transformations de graphes définissables par MSO sur des graphes à cordes sont les deux que je connais le mieux. Nous savons que les transducteurs à états finis à 2 voies (qui sont plus expressifs que leurs homologues à 1 voie) et les transformations de chaîne définissables par MSO capturent le même ensemble de transformations avec d'autres modèles moins connus qui utilisent des combinateurs. Cette classe de transformations est considérée comme régulière, et il est donc facile de montrer qu'une transformation est régulière si vous pouvez en fournir une description avec l'un de ces modèles.

Existe-t-il un moyen simple de dire qu'une transformation est en dehors de cette classe? Quelque chose de semblable au lemme de pompage pour les langages réguliers ou au théorème de Myhill-Nerode mais pour les transformations de chaînes est le genre de chose que je recherche.

Votre question n'est pas entièrement bien définie: comment vous donne-t-on la transformation avec laquelle vous commencez? Par exemple, si vous supposez que la transformation est donnée par exemple par une machine de Turing, alors il n'y a clairement aucun moyen algorithmique de décider s'il s'agit d'une transduction régulière.

Cependant, il semble que ce que vous demandez, c'est s'il existe une caractérisation "indépendante de la machine" des transductions de cordes (par exemple, Myhill-Nerode).

Bien que je ne connaisse pas une telle caractérisation en général (je suis sûr que cette caractérisation n'est pas connue), il existe une telle caractérisation pour les transducteurs de chaîne avec des informations d'origine, développée par Bojnaczyk.

Vous pouvez commencer ici.