There are a number of different models for defining transformations between languages. Finite state transducers and MSO-definable graph transformations over string graphs are the two that I am best acquainted with. We know that 2-way finite state transducers (which are more expressive than their 1-way counterparts) and MSO-definable string transformations capture the same set of transformations along with some other less well-known models that use combinators. This class of transformations is considered regular, and so it is easy to show then that a transformation is regular if you can provide a description of it with one of these models.

Is there a straight-forward way to say that a transformation is outside of this class? Something akin to the pumping lemma for regular languages or the Myhill-Nerode theorem but for string transformations is the sort of thing I am looking for.


Your question is not entirely well defined: how are you given the transformation you start with? For example, if you assume the transformation is given by e.g. a Turing machine, then clearly there is no algorithmic way of deciding whether it's a regular transduction.

However, it seems that what you're asking is whether there is some "machine-independent" characterization of string transductions (e.g., Myhill-Nerode).

While I don't know of such a characterization in general (I'm pretty sure no such characterization is known), there is such a characterization for string transducers with origin information, developed by Bojnaczyk.

You can start here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.