Deciding regularity of hairpin completions of regular languages in polynomial time

DOI10.1016/J.IC.2012.04.003MaRDI QIDQ714734zbMATH OpenOpenAlexFDO

Authors Volker Diekert, Steffen Kopecki, Victor Mitrana

Publication date 11 October 2012

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5722790 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1241377 (Why is no real title available?)
• scientific article; zbMATH DE number 1342097 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• An Introduction to Symbolic Dynamics and Coding
• Bounded hairpin completion
• Characterizing regular languages with polynomial densities
• Codes and automata.
• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• Compression and entropy
• Depth-First Search and Linear Graph Algorithms
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Hairpin Completion Versus Hairpin Reduction
• Hairpin Lengthening
• Hairpin Lengthening and Shortening of Regular Languages
• Hairpin Structures in DNA Words
• It is NL-complete to decide whether a hairpin completion of regular languages is regular
• Iterated hairpin completions of non-crossing words
• Language theoretical properties of hairpin formations
• On iterated hairpin completion
• On some algorithmic problems regarding the hairpin completion
• On the Hairpin Completion of Regular Languages
• On the entropy of context-free languages
• On the growth of linear languages
• Some remarks on the hairpin completion
• The syntactic monoid of hairpin-free languages
• Two complementary operations inspired by the DNA hairpin formation: Completion and reduction

Cited in

(6)

• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• Non-closure under complementation for unambiguous linear grammars
• It is NL-complete to decide whether a hairpin completion of regular languages is regular
• Two-sided derivatives for regular expressions and for hairpin expressions
• Hairpin Lengthening and Shortening of Regular Languages
• On the Hairpin Completion of Regular Languages

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)