Identification of pattern languages from examples and queries (Q1097709): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1295380 |
Changed an Item |
||
Property / author | |||
Property / author: Ker-I. Ko / rank | |||
Normal rank |
Revision as of 17:41, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Identification of pattern languages from examples and queries |
scientific article |
Statements
Identification of pattern languages from examples and queries (English)
0 references
1987
0 references
Pattern languages are defined by \textit{D. Angluin} [J. Comput. Syst. Sci. 21, 46-62 (1980; Zbl 0454.68108)] as an abstract model of learning one- dimensional patterns. A pattern is defined to be a string of variables and constants, and its associated language is defined to be all constant strings obtained by substituting constant strings for variables in the pattern. The pattern-finding problem is to identify a mysterious pattern from examples of and queries about strings in the pattern language. This is a specific problem of the general theory of learning as publicized by \textit{L. G. Valiant} [Commun. ACM 27, 1134-1142 (1984; Zbl 0587.68077)]. The main difference is that this paper uses the worst-case model, while Valiant uses a probabilistic model. The main result of this paper states that the number of queries necessary to precisely identify a pattern could be bounded by a polynomial in the length of the pattern if the initial sample of strings in the pattern language satisfies certain structural properties. This property is found to be necessary also for patterns of only one variable.
0 references
inductive inference
0 references
polynomial-time
0 references
learning
0 references
pattern-finding problem
0 references
pattern language
0 references