On the complexity of learning strings and sequences
type: Item
instance of: scholarly article
title: On the complexity of learning strings and sequences
zbMATH Open document ID: 0787.68088
DOI: 10.1016/0304-3975(93)90167-R
author: Tao Jiang
author: Ming Li
published in: Theoretical Computer Science
publication date: 1993-11-28T00:00:00Z
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.
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 440339
zbMATH Keywords: learning
zbMATH Keywords: consistent superstring problem
zbMATH Keywords: consisting supersequence problem
zbMATH Keywords: NP-complete
reviewed by: Mirosław Truszczyński
MaRDI profile type: Publication
cites work: Efficient string matching
cites work: On finding minimal length superstrings
cites work: Q4198056
cites work: The Complexity of Some Problems on Subsequences and Supersequences
cites work: Computational limitations on learning from examples
cites work: A theory of the learnable
Recommended article: The Complexity of Learning SUBSEQ (A)
Recommended article: The complexity of learning SUBSEQ(A)
Recommended article: Q4258669
Recommended article: On the complexity of random strings
Recommended article: Adaptive learning of compressible strings
Recommended article: Q3093337
Recommended article: Exact bounds on the complexity of sequential string matching algorithms
Recommended article: On the Kernelization Complexity of String Problems
Recommended article: On the kernelization complexity of string problems
Recommended article: Complexity of strings in the class of Markov sources
description: scientific article; zbMATH DE number 440339