Name
Abstract | ||
|---|---|---|
We formalize the hairpin inverted repeat operation, which is known in ciliate genetics as an operation on words and languages by defining $\mathcal{HI}(w, P)$ as the set of all words xαyRαRz where w = xαyαRz and the pointer α is in P. We extend this concept to language families which results in families $\mathcal{HI}(L_{1},L_{2})$. For L1 and L2 being the families of finite, regular, context-free, context-sensitive or recursively enumerable language, respectively, we determine the hierarchy of the families $\mathcal{HI}(L_{1},L_{2})$ and compare these families with those of the Chomsky hierarchy. Furthermore, we give some results on the decidability of the membership problem, emptiness problem and finiteness problem for the families $\mathcal{HI}(L_{1},L_{2})$. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30550-7_13 | Developments in Language Theory |
Keywords | Field | DocType |
language family,recursively enumerable language,emptiness problem,hairpin inverted repeat operation,finiteness problem,chomsky hierarchy,ciliate bio-operation,ciliate genetics,membership problem,genetics,inverted repeat | Discrete mathematics,Combinatorics,Closure (mathematics),Recursively enumerable language,Chomsky hierarchy,Decidability,Regular language,Membership problem,Mathematics,Language family | Conference |
Volume | ISSN | ISBN |
3340 | 0302-9743 | 3-540-24014-4 |
Citations | PageRank | References |
2 | 0.45 | 9 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jürgen Dassow | 1 | 530 | 118.27 |