IT IS NL-COMPLETE TO DECIDE WHETHER A HAIRPIN COMPLETION OF REGULAR LANGUAGES IS REGULAR

被引：1

作者：

Diekert, Volker ^{[1
]}

Kopecki, Steffen ^{[1
]}

机构：

[1] Univ Stuttgart, Inst Formal Methods Comp Sci, D-70569 Stuttgart, Germany

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2011年 / 22卷 / 08期

关键词：

Automata and formal languages; regular languages; finite automata; NL-complete problems; DNA-computing; hairpin completion;

D O I：

10.1142/S0129054111009057

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 decidable. In 2009 this decidability problem has been solved positively in [5] 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.

引用

页码：1813 / 1828

页数：16

共 20 条

[1] A NOTE ON LOGSPACE OPTIMIZATION [J].

ALVAREZ, C ;

JENNER, B .

COMPUTATIONAL COMPLEXITY, 1995, 5 (02) :155-166

[2]

Cheptea D., 2006, Proc. Transgressive Computing, P216

[3]

Deaton R., 1998, P DNA BASED COMPUTER, V44, P247

[4]

Diekert V, 2011, LECT NOTES COMPUT SC, V6482, P105, DOI 10.1007/978-3-642-18098-9_12

[5]

Diekert V, 2009, LECT NOTES COMPUT SC, V5684, P170, DOI 10.1007/978-3-642-03466-4_11

[6]

Garzon M, 1997, P 3 DIMACS WORKSH DN, P230

[7]

Garzon M, 1998, P 3 GEN PROGR C MAD, P684

[8]

Hopcroft J., 1979, Introduction to automata theory, languages, and computation

[9]

Ito M., 2010, INFORM COMP IN PRESS

[10]

Kari L, 2007, ACTA INFORM, V44, P153, DOI 10.1007/S00236-007-0041-4

← 1 2 →