.png){kind=icon}
Return
Learning context-free grammars using tabular representations
.png){kind=icon}
PRE
AI
DOI：10.1016/j.patcog.2004.03.021.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficient parsing algorithms for context-free grammars such as Cocke-Younger-Kasami algorithm. By employing this representation method, the problem of learning context-free grammars from examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem. Further, we incorporate partially structured examples to improve the efficiency of our learning algorithm, where a structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of the unknown grammar. We demonstrate some experimental results using these algorithms and theoretically analyse the completeness of the search space using the tabular method for context-free grammars. (c) 2005 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.
Keywords:
grammatical inference
context-free grammar
genetic algorithm
structured example
dynamic programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.6
Papers:
1.3W
Citations:
4.5W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveExpansions on a computerized operant laboratory: Considerations for combining teaching and research
OAAI
OAAIShareSaveShareSaveShareSave
View more