Iterated Hairpin Completions of Non-crossing Words

Details Iterated Hairpin Completions of Non-crossing Words Iterated Hairpin Completions of Non-crossing Words

2011-10-04

arxiv.org/abs/1110.0760v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Iterated Hairpin Completions of Non-crossing Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Iterated Hairpin Completions of Non-crossing Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Iterated Hairpin Completions of Non-crossing Words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-269939