Then let τ be de- where True is any unary predicate that is always true for models in S. In this transduction, ϕ P b (x) is only true for input positions labeled b that do not follow another b; conversely, ϕ P c (x) is only true for input positions labeled b that do follow another b.
for example, the output under τ for the string model for abba from Figure 2 is a model for abca as shown in Figure 3.