Search publications, data, projects and authors
Iterated Hairpin Completions of Non-crossing Words

Textual materials

KeywordsTriple Keywords
Language and languages
Foreign languages
World literature
Western literature (Western countries)
Place (Literature)
Setting (Literature)


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.

Report a bug

Under construction

We're in Beta!

The GoTriple platform is still in Beta and we keep adding new features everyday. Check the project's website to see what's new and subscribe to our Mailing List.