
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.
Artificial intelligence, Complexity of computation (including implicit computational complexity), learning, Analysis of algorithms and problem complexity, Pattern recognition, speech recognition, Learning and adaptive systems in artificial intelligence, pattern-finding problem, Theoretical Computer Science, Computer Science Applications, Computational Theory and Mathematics, pattern language, inductive inference, polynomial-time, Information Systems
Artificial intelligence, Complexity of computation (including implicit computational complexity), learning, Analysis of algorithms and problem complexity, Pattern recognition, speech recognition, Learning and adaptive systems in artificial intelligence, pattern-finding problem, Theoretical Computer Science, Computer Science Applications, Computational Theory and Mathematics, pattern language, inductive inference, polynomial-time, Information Systems
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 12 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
