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)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90167-R

zbMATH Keywords

consistent superstring problemconsisting supersequence problemlearningNP-complete

Mathematics Subject Classification ID

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

Review text

It is shown that strings (sequences) are not learnable by strings (sequences) in the distribution-free (pac-) learning model proposed by Valiant. The key role in the argument is played by the results on the complexity of consistent superstring and consistent supersequence problems. The consistent superstring problem is defined as follows: given two collections of strings, called positive examples and negative examples, decide whether there exists a string containing all positive examples as substrings and no negative example as a substring. The consisting supersequence problem is defined similarly. Both problems are proved to be NP-complete.

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

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

Cited in

(13)

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