Deciding regularity of hairpin completions of regular languages in polynomial time

DOI10.1016/j.ic.2012.04.003zbMath1279.68093arXiv1108.2427OpenAlexW2002626286MaRDI QIDQ714734

Steffen Kopecki, Volker Diekert, 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

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

Related Items (2)

Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions ⋮ Non-closure under complementation for unambiguous linear grammars

Cites Work

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

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