Bibliography

On twist-closed trios: a new morphic characterization of r.e. sets

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}$.

BibTeX

@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
}