Grammatical Inference of some Probabilistic Context-Free Grammars from Positive Data using Minimum Satisfiability

[edit]

James Scicluna, Colin Higuera ;
The 12th International Conference on Grammatical Inference, PMLR 34:139-152, 2014.

Abstract

Recently, different theoretical learning results have been found for a variety of context-free grammar subclasses through the use of distributional learning (Clark, 2010b). However, these results are still not extended to probabilistic grammars. In this work, we give a practical algorithm, with some proven properties, that learns a subclass of probabilistic grammars from positive data. A minimum satisfiability solver is used to direct the search towards small grammars. Experiments on typical context-free languages and artificial natural language grammars give positive results.

Related Material