e-GRIDS: Computationally Efficient Gramatical Inference from Positive Examples

Petasis, Georgios ; Paliouras, Georgios ; Karkaletsis, Vangelis ; Halatsis, Constantin ; Spyropoulos, Constantine D. (2004)


In this paper we present a new computationally efficient algorithm for inducing context-free grammars that is able to learn from positive sample sentences. This new algorithm uses simplicity as a criterion for directing inference, and the search process of the new algorithm has been optimised by utilising the results of a theoretical analysis regarding the behaviour and complexity of the search operators. Evaluation results are presented on artificially generated data, while the scalability of the algorithm is tested on a large textual corpus. These results show that the new algorithm performs well and can infer grammars from large data sets in a reasonable amount of time.

© Rovira i Virgili University, Tarragona, Spain
Except where otherwise noted, this item's license is described as © Rovira i Virgili University, Tarragona, Spain