Name
Title | ||
|---|---|---|
Language Families Defined By A Ciliate Bio-Operation: Hierarchies And Decision Problems |
Abstract | ||
|---|---|---|
We formalize the hairpin inverted repeat excision, which is known in ciliate genetics as an operation on words and languages by defining HI(w, P) as the set of all words xay(R)alpha(R)z where w = x alpha y alpha e(R)z and the pointer alpha is in P. We extend this concept to language families which results in families HI(L-1, L-2). For L-1 and L-2 be the families of finite, regular, context-free, context-sensitive or recursively enumerable language, respectively, we determine the hierarchy of the families HI(L-2, L-2) and compare these families with those of the Chomsky hierarchy. Furthermore, we present the status of decidability of the membership problem, emptiness problem and finiteness problem for the families HI(L-1,L-2). |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1142/S0129054105003212 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
hairpin operations, language families of Chomsky hierarchy, decision problems | Pointer (computer programming),Discrete mathematics,Combinatorics,Decision problem,Recursively enumerable language,Chomsky hierarchy,Decidability,Emptiness,Membership problem,Hierarchy,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 4 | 0129-0541 |
Citations | PageRank | References |
4 | 0.46 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jürgen Dassow | 1 | 530 | 118.27 |
| Markus Holzer | 2 | 193 | 21.51 |