NP-completeness of special string editing problems

DOI10.4213/MVK103MaRDI QIDQ4959092zbMATH OpenOpenAlexFDO

Authors S. S. Martynov

Publication date 15 September 2021

Published in Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/mvk103

zbMATH Keywords

NP-complete problemsblock codestring editing problems

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 8125
• Edit distance with block deletions
• scientific article; zbMATH DE number 3883626
• The shortest common nonsubsequence problem is NP-complete
• Topology of strings: median string is NP-complete

Cited in

(4)

• A Probabilistic Analysis of a String Editing Problem and its Variations
• scientific article; zbMATH DE number 714495 (Why is no real title available?)
• scientific article; zbMATH DE number 3883626 (Why is no real title available?)
• Constrained many-to-one string editing with memory

This page was built for publication: NP-completeness of special string editing problems

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