Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)

DOI10.1007/978-3-642-18098-9_12zbMath1297.68122OpenAlexW1554469734MaRDI QIDQ3073627

Steffen Kopecki, Volker Diekert

Publication date: 11 February 2011

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-18098-9_12

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Iterated Hairpin Completions of Non-crossing Words ⋮ Hairpin Lengthening and Shortening of Regular Languages ⋮ Unnamed Item ⋮ Deciding regularity of hairpin completions of regular languages in polynomial time ⋮ Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the growth of linear languages
• Two complementary operations inspired by the DNA hairpin formation: Completion and reduction
• The syntactic monoid of hairpin-free languages
• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• On the Hairpin Completion of Regular Languages
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Hairpin Structures in DNA Words
• A note on undecidable properties of formal languages
• On the entropy of context-free languages

This page was built for publication: Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)