On the complexity of learning strings and sequences

DOI10.1016/0304-3975(93)90167-RzbMath0787.68088MaRDI QIDQ688167

Tao Jiang, Ming Li

Publication date: 28 November 1993

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

zbMATH Keywords

learningNP-completeconsistent superstring problemconsisting supersequence problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (7)

DNA sequencing and string learning ⋮ Approximating shortest superstrings with constraints ⋮ A new graph model and algorithms for consistent superstring problems ⋮ Consistent subsequences and supersequences ⋮ On the approximation of longest common nonsupersequences and shortest common nonsubsequences ⋮ Shortest consistent superstrings computable in polynomial time ⋮ Approximating shortest superstrings with constraints

Cites Work

• Unnamed Item
• On finding minimal length superstrings
• A theory of the learnable
• Computational limitations on learning from examples
• Efficient string matching
• The Complexity of Some Problems on Subsequences and Supersequences

This page was built for publication: On the complexity of learning strings and sequences