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

DOI10.1016/J.TCS.2008.09.049MaRDI QIDQ1004085zbMATH OpenOpenAlexFDO

Authors Florin Manea, Victor Mitrana, 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) Protein sequences, DNA sequences (92D20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• scientific article; zbMATH DE number 5722790
• Hairpin Completion Versus Hairpin Reduction
• Language theoretical properties of hairpin formations
• Bounded hairpin completion
• On the hairpin incompletion

Cites work

• scientific article; zbMATH DE number 5722790 (Why is no real title available?)
• scientific article; zbMATH DE number 1241377 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1836412 (Why is no real title available?)
• A geometric hierarchy beyond context-free languages
• Developments in Language Theory
• Hairpin Completion Versus Hairpin Reduction
• Hairpin languages
• Indexed Grammars—An Extension of Context-Free Grammars
• On Some Algorithmic Problems Regarding the Hairpin Completion
• Recognition and parsing of context-free languages in time n3
• SOME REMARKS ON HAIRPIN AND LOOP LANGUAGES
• Simple matrix languages
• Superposition based on Watson-Crick-like complementarity
• Tree adjunct grammars

Cited in

(22)

• STRING OPERATIONS SUGGESTED BY DNA BIOCHEMISTRY: THE BALANCED CUT OPERATION
• Hairpin Finite Automata
• Hairpin Lengthening and Shortening of Regular Languages
• Some remarks on the hairpin completion
• On the hairpin incompletion
• Language theoretical properties of hairpin formations
• Bounded Hairpin Completion
• On iterated hairpin completion
• On decidability and closure properties of language classes with respect to bio-operations
• Hairpin Completion Versus Hairpin Reduction
• Testing DNA code words properties of regular languages
• Iterated hairpin completions of non-crossing words
• Bounded hairpin completion
• A series of algorithmic results related to the iterated hairpin completion
• scientific article; zbMATH DE number 5722790 (Why is no real title available?)
• 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
• Deciding regularity of hairpin completions of regular languages in polynomial time
• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• Hairpin completions and reductions: semilinearity properties
• Regularity of iterative hairpin completions of crossing \((2, 2)\)-words
• The pseudopalindromic completion of regular languages

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

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