State Complexity of Overlap Assembly

DOI10.1142/S012905412042006XzbMath1458.68091OpenAlexW3112841049MaRDI QIDQ5859665

Lila Kari, Marek Szykuła, Bai Li, Janusz A. Brzozowski

Publication date: 19 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905412042006x

zbMATH Keywords

regular languagestate complexityoverlap assemblytight upper bound

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Protein sequences, DNA sequences (92D20)

Cites Work

• Further remarks on DNA overlap assembly
• On iterated hairpin completion
• Algorithmic applications of XPCR
• Self-assembly of strings and languages
• On some algorithmic problems regarding the hairpin completion
• Minimality in template-guided recombination
• The state complexities of some basic operations on regular languages
• Tissue P systems.
• State complexity of overlap assembly
• On the overlap assembly of strings and languages
• The chop of languages
• Computing by polymerase chain reaction
• A Formal Language Model of DNA Polymerase Enzymatic Activity
• State Complexity of Chop Operations on Unary and Finite Languages
• Generalized periodicity and primitivity for words
• DNA Recombination by XPCR
• Chop Operations and Expressions: Descriptional Complexity Considerations
• Theoretical Computer Science
• IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
• Hairpin Completion Versus Hairpin Reduction
• DNA Computing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item