caa a22 4500 467953120 CHVBK 20180323165703.0 cr unu---uuuuu 170328e19870301xx s 000 0 eng 10.1023/A:1022812926936 doi (NATIONALLICENCE)springer-10.1023/A:1022812926936 (NATIONALLICENCE)springer-10.1007/BF00058754 A Version Space Approach to Learning Context-free Grammars [Elektronische Daten] [Kurt Vanlehn, William Ball] In principle, the version space approach can be applied to any induction problem. However, in some cases the representation language for generalizations is so powerful that (1) some of the update functions for the version space are not effectively computable, and (2) the version space contains infinitely many generalizations. The class of context-free grammars is a simple representation that exhibits these problems. This paper presents an algorithm that solves both problems for this domain. Given a sequence of strings, the algorithm incrementally constructs a data structure that has nearly all the beneficial properties of a version space. The algorithm is fast enough to solve small induction problems completely, and it serves as a framework for biases that permit the solution of larger problems heuristically. The same basic approach may be applied to representations that include context-free grammars as special cases, such as And-Or graphs, production systems, and Horn clauses. Kluwer Academic Publishers, 1987 Induction nationallicence grammatical inference nationallicence version space nationallicence context-free grammars nationallicence learning from examples nationallicence Vanlehn Kurt Department of Psychology, Carnegie-Mellon University, 15213, Pittsburgh, PA, USA aut Ball William Department of Psychology, Carnegie-Mellon University, 15213, Pittsburgh, PA, USA aut Machine Learning Kluwer Academic Publishers-Plenum Publishers 2/1(1987-03-01), 39-74 0885-6125 2:1<39 1987 2 10994 https://doi.org/10.1023/A:1022812926936 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1022812926936 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Vanlehn Kurt Department of Psychology, Carnegie-Mellon University, 15213, Pittsburgh, PA, USA aut NATIONALLICENCE 700 1- Ball William Department of Psychology, Carnegie-Mellon University, 15213, Pittsburgh, PA, USA aut NATIONALLICENCE 773 0- Machine Learning Kluwer Academic Publishers-Plenum Publishers 2/1(1987-03-01), 39-74 0885-6125 2:1<39 1987 2 10994 NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00058754 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Vanlehn Kurt Department of Psychology, Carnegie-Mellon University, 15213, Pittsburgh, PA, U.S.A aut NATIONALLICENCE 700 1- Ball William Department of Psychology, Carnegie-Mellon University, 15213, Pittsburgh, PA, U.S.A aut NATIONALLICENCE 773 0- Machine Learning Kluwer Academic Publishers 2/1(1987-03-01), 39-74 0885-6125 2:1<39 1987 2 10994 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE NATIONALLICENCE NL-springer