On the complexity of learning strings and sequences

DOI10.1016/0304-3975(93)90167-RMaRDI QIDQ688167zbMATH OpenFDO

Authors 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

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

Recommendations

• The Complexity of Learning SUBSEQ (A)
• The complexity of learning SUBSEQ(A)
• scientific article; zbMATH DE number 1336330
• On the complexity of random strings
• Adaptive learning of compressible strings
• scientific article; zbMATH DE number 5957322
• Exact bounds on the complexity of sequential string matching algorithms
• On the kernelization complexity of string problems
• On the kernelization complexity of string problems
• Complexity of strings in the class of Markov sources

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A theory of the learnable
• Computational limitations on learning from examples
• Efficient string matching
• On finding minimal length superstrings
• The Complexity of Some Problems on Subsequences and Supersequences

Cited in

(13)

• Approximating shortest superstrings with constraints
• scientific article; zbMATH DE number 6999908 (Why is no real title available?)
• scientific article; zbMATH DE number 2019606 (Why is no real title available?)
• Approximating shortest superstrings with constraints
• String Matching: Communication, Circuits, and Learning.
• On the approximation of longest common nonsupersequences and shortest common nonsubsequences
• A new graph model and algorithms for consistent superstring problems
• DNA sequencing and string learning
• The complexity of learning SUBSEQ(A)
• scientific article; zbMATH DE number 5957322 (Why is no real title available?)
• The Complexity of Learning SUBSEQ (A)
• Consistent subsequences and supersequences
• Shortest consistent superstrings computable in polynomial time

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

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