| Autor: |
Kari, Lila, Kopecki, Steffen, Seki, Shinnosuke |
| Rok vydání: |
2011 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
Iterated hairpin completion is an operation on formal languages that is inspired by the hairpin formation in DNA biochemistry. Iterated hairpin completion of a word (or more precisely a singleton language) is always a context-sensitive language and for some words it is known to be non-context-free. However, it is unknown whether regularity of iterated hairpin completion of a given word is decidable. Also the question whether iterated hairpin completion of a word can be context-free but not regular was asked in literature. In this paper we investigate iterated hairpin completions of non-crossing words and, within this setting, we are able to answer both questions. For non-crossing words we prove that the regularity of iterated hairpin completions is decidable and that if iterated hairpin completion of a non-crossing word is not regular, then it is not context-free either. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
