Deciding regularity of hairpin completions of regular languages in polynomial time

DOI10.1016/J.IC.2012.04.003zbMATH Open1279.68093arXiv1108.2427OpenAlexW2002626286MaRDI QIDQ714734FDOQ714734

Steffen Kopecki, Volker Diekert, Victor Mitrana

Publication date: 11 October 2012

Published in: Information and Computation (Search for Journal in Brave)

Abstract: The hairpin completion is an operation on formal languages that has been inspired by the hairpin formation in DNA biochemistry and by DNA computing. In this paper we investigate the hairpin completion of regular languages. It is well known that hairpin completions of regular languages are linear context-free and not necessarily regular. As regularity of a (linear) context-free language is not decidable, the question arose whether regularity of a hairpin completion of regular languages is decidable. We prove that this problem is decidable and we provide a polynomial time algorithm. Furthermore, we prove that the hairpin completion of regular languages is an unambiguous linear context-free language and, as such, it has an effectively computable growth function. Moreover, we show that the growth of the hairpin completion is exponential if and only if the growth of the underlying languages is exponential and, in case the hairpin completion is regular, then the hairpin completion and the underlying languages have the same growth indicator.

Full work available at URL: https://arxiv.org/abs/1108.2427

Recommendations

• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• On the Hairpin Completion of Regular Languages
• It is NL-complete to decide whether a hairpin completion of regular languages is regular
• Some remarks on the hairpin completion
• On the iterated hairpin completion

zbMATH Keywords

regular languagefinite automatonhairpin completionrational growthunambiguous linear language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An Introduction to Symbolic Dynamics and Coding
• Depth-First Search and Linear Graph Algorithms
• Title not available (Why is that?)
• The syntactic monoid of hairpin-free languages
• On the entropy of context-free languages
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Codes and automata.
• Two complementary operations inspired by the DNA hairpin formation: Completion and reduction
• On some algorithmic problems regarding the hairpin completion
• SOME REMARKS ON THE HAIRPIN COMPLETION
• Hairpin Lengthening and Shortening of Regular Languages
• On the Hairpin Completion of Regular Languages
• Title not available (Why is that?)
• Hairpin Lengthening
• Language theoretical properties of hairpin formations
• Hairpin Completion Versus Hairpin Reduction
• On iterated hairpin completion
• On the growth of linear languages
• Iterated Hairpin Completions of Non-crossing Words
• Bounded hairpin completion
• Hairpin Structures in DNA Words
• Title not available (Why is that?)
• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• IT IS NL-COMPLETE TO DECIDE WHETHER A HAIRPIN COMPLETION OF REGULAR LANGUAGES IS REGULAR
• Compression and entropy
• Characterizing regular languages with polynomial densities

Cited In (4)

• Non-closure under complementation for unambiguous linear grammars
• Hairpin Lengthening and Shortening of Regular Languages
• Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions
• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)

This page was built for publication: Deciding regularity of hairpin completions of regular languages in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714734)