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. (eds.), Foundations of Computer Science: Potential - Theory - Cognition, to Wilfried Brauer on the occasion of his sixtieth birthday, pages 135-142.

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

BibTeX entry

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

Copyright Notice

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.