Two complementary operations inspired by the DNA hairpin formation: Completion and reduction

DOI10.1016/J.TCS.2008.09.049zbMath1160.68022OpenAlexW2058038744MaRDI QIDQ1004085

Victor Mitrana, Florin Manea, Takashi Yokomori

Publication date: 2 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.049

zbMATH Keywords

DNA computinghairpin completionmildly context-sensitive languageshairpin reduction

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Protein sequences, DNA sequences (92D20)

Related Items (16)

Iterated Hairpin Completions of Non-crossing Words ⋮ Hairpin Lengthening and Shortening of Regular Languages ⋮ A series of algorithmic results related to the iterated hairpin completion ⋮ Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions ⋮ IT IS NL-COMPLETE TO DECIDE WHETHER A HAIRPIN COMPLETION OF REGULAR LANGUAGES IS REGULAR ⋮ Hairpin completions and reductions: semilinearity properties ⋮ Testing DNA code words properties of regular languages ⋮ Language theoretical properties of hairpin formations ⋮ The pseudopalindromic completion of regular languages ⋮ Regularity of Iterative Hairpin Completions of Crossing (2, 2)-Words ⋮ On iterated hairpin completion ⋮ Bounded hairpin completion ⋮ Deciding regularity of hairpin completions of regular languages in polynomial time ⋮ SOME REMARKS ON THE HAIRPIN COMPLETION ⋮ Bounded Hairpin Completion ⋮ Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A geometric hierarchy beyond context-free languages
• Tree adjunct grammars
• Superposition based on Watson-Crick-like complementarity
• On Some Algorithmic Problems Regarding the Hairpin Completion
• SOME REMARKS ON HAIRPIN AND LOOP LANGUAGES
• HAIRPIN LANGUAGES
• Hairpin Completion Versus Hairpin Reduction
• Developments in Language Theory
• Recognition and parsing of context-free languages in time n3
• Indexed Grammars—An Extension of Context-Free Grammars
• Simple matrix languages

This page was built for publication: Two complementary operations inspired by the DNA hairpin formation: Completion and reduction