<p>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.</p>

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

<p>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. </p>

<p>You can <a href="https://arxiv.org/pdf/1309.6124.pdf" rel="nofollow noreferrer">start here.</a></p>

CC BY-SA 4.0
2018-11-17T14:39:15.820Z
2018-11-17T14:39:15.820Z
Shaull
<p>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.</p>

<p>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.</p>

<fl.formal-languages>
Is there a method for proving non-regularity of string transformations?
Taylor Dohmen
# Is there a method for proving non-regularity of string transformations?

(Asked by: username_0 on 2018-11-16)

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.

**Tags:** fl.formal-languages

---

## 1 answers

### Answer by username_1 on 2018-11-17. Score: 2

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.](https://arxiv.org/pdf/1309.6124.pdf)


---

