Formal Grammars
A Journal of Mathematical Research on Formal and Natural Languages

Editor-in-chief: Carlos Martín-Vide
Special issues
Introduction
Volume 7(2004)
Volume 8(2005)
Editorial board
Aims and Scope
Subscription to the Hardcopy Edition
Submission procedure


e-GRIDS: Computationally Efficient Gramatical Inference from Positive Examples

GEORGIOS PETASIS, GEORGIOS PALIOURAS, VANGELIS KARKALETSIS,
CONSTANTINE HALATSIS, CONSTANTINE SPYROPOULOS

Abstract

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.

Download:
PS file
PDF file
Copyright © 2004 GRLMC. All rights reserved.
Research Group on Mathematical Linguistics - Rovira i Virgili University
Webmaster