Matthias Jantzen.
On twist-closed trios: a new morphic characterization of r.e. sets.
In Freksa et al. , Foundations of Computer Science: Potential - Theory - Cognition, to Wilfried Brauer on the occasion of his sixtieth birthday, pages 135-142.
We show that in conjunction with the usual trio operations the combination of twist and product can simulate any combination of intersection, reversal and $1\over 2 $. It is proved that any recursively enumerable language $\mathit{L}$ can be homomorphically represented by twisting a linear context-free language.gs by rearranging its letters $x_i\in \Sigma$: for a string $w := x_1x_2\cdots x_{n-1}x_n$ the new string is $\twist{w} := x_1x_nx_2x_{n-1}\cdots x_{\lfloor{n\over2}\rfloor+1}$.
@incollection{Jantzen+97, Author = {Jantzen, Matthias}, Crossref = {Freksa+-e-97}, Date-Modified = {2006-02-21 22:59:55 +0100}, Pages = {135--142}, Title = {On twist-closed trios: a new morphic characterization of r.e. sets}, Year = 1997, Abstract = {We show that in conjunction with the usual trio operations the combination of twist and product can simulate any combination of intersection, reversal and $1\over 2 $. It is proved that any recursively enumerable language $\mathit{L}$ can be homomorphically represented by twisting a linear context-free language.gs by rearranging its letters $x_i\in \Sigma$: for a string $w := x_1x_2\cdots x_{n-1}x_n$ the new string is $\twist{w} := x_1x_nx_2x_{n-1}\cdots x_{\lfloor{n\over2}\rfloor+1}$.} } @book{Freksa+-e-97, Address = Springer.addr, Booktitle = {Foundations of Computer Science: Potential - Theory - Cognition}, Date-Modified = {2006-02-21 23:00:17 +0100}, Editor = {Freksa, Christian and Jantzen, Matthias and Valk, R{\"u}diger}, Isbn = {3-540-63746-X}, Publisher = Springer, Series = LNCS, Title = {Foundations of Computer Science: Potential - Theory - Cognition, to Wilfried Brauer on the occasion of his sixtieth birthday}, Volume = 1337, Year = 1997 }