It Is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular

Details It Is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular It Is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular

2011-01-25

arxiv.org/abs/1101.4824v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

The hairpin completion is an operation on formal languages which is inspired by the hairpin formation in biochemistry. Hairpin formations occur naturally within DNA-computing. It has been known that the hairpin completion of a regular language is linear context-free, but not regular, in general. However, for some time it is was open whether the regularity of the hairpin completion of a regular language is is decidable. In 2009 this decidability problem has been solved positively by providing a polynomial time algorithm. In this paper we improve the complexity bound by showing that the decision problem is actually NL-complete. This complexity bound holds for both, the one-sided and the two-sided hairpin completions.

Affiliated with

Also associated with

No associations

Rating

It Is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular 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 It Is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and It Is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-542632