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.
%0 Journal Article
%1 GRAMMARS-vol.7-Petasis
%A Petasis, Georgios
%A Paliouras, Georgios
%A Karkaletsis, Vangelis
%A Halatsis, Constantine
%A Spyropoulos, Constantine D.
%D 2004
%J GRAMMARS
%K context-free description examples grammars, grammatical inference, length, minimum positive
%P 69--110
%T E-GRIDS: Computationally Efficient Grammatical Inference from Positive Examples
%U http://www.ellogon.org/petasis/bibliography/GRAMMARS/GRAMMARS2004.pdf
%V 7
%X 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.
@article{GRAMMARS-vol.7-Petasis,
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.},
added-at = {2011-08-10T12:37:26.000+0200},
author = {Petasis, Georgios and Paliouras, Georgios and Karkaletsis, Vangelis and Halatsis, Constantine and Spyropoulos, Constantine D.},
biburl = {https://www.bibsonomy.org/bibtex/20cc6ee62ffaa45a1ec4de9bf55a3c9c6/petasis},
interhash = {7f440580ec8b73539fad41f27e1903a4},
intrahash = {0cc6ee62ffaa45a1ec4de9bf55a3c9c6},
journal = {GRAMMARS},
keywords = {context-free description examples grammars, grammatical inference, length, minimum positive},
note = {Technical Report referenced in the paper: http://www.ellogon.org/petasis/bibliography/GRAMMARS/GRAMMARS2004-SpecialIssue-Petasis-TechnicalReport.pdf},
pages = {69--110},
timestamp = {2011-08-10T12:37:27.000+0200},
title = {{E}-{GRIDS}: {C}omputationally {E}fficient {G}rammatical {I}nference from {P}ositive {E}xamples},
url = {http://www.ellogon.org/petasis/bibliography/GRAMMARS/GRAMMARS2004.pdf},
volume = 7,
year = 2004
}