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

DOI10.1142/S0129054111009057zbMath1255.68070OpenAlexW2963981206MaRDI QIDQ3224950

Volker Diekert, Steffen Kopecki

Publication date: 13 March 2012

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054111009057

zbMATH Keywords

automatafinite automataformal languagesregular languageshairpin completionDNA-computingNL-complete problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Deciding regularity of hairpin completions of regular languages in polynomial time

Cites Work

• Unnamed Item
• On iterated hairpin completion
• Two complementary operations inspired by the DNA hairpin formation: Completion and reduction
• On some algorithmic problems regarding the hairpin completion
• A note on logspace optimization
• The syntactic monoid of hairpin-free languages
• SOME REMARKS ON THE HAIRPIN COMPLETION

This page was built for publication: IT IS NL-COMPLETE TO DECIDE WHETHER A HAIRPIN COMPLETION OF REGULAR LANGUAGES IS REGULAR