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

block codeNP-complete problemsstring editing problems

Mathematics Subject Classification ID

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

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

(5)

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

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)