DocumentCode
2726088
Title
Applying prereduction to reduce the time cost of TBL algorithm
Author
Tóth, Zsolt ; Kovács, László
Author_Institution
Dept. of Inf. Technol., Univ. of Miskolc, Miskolc, Hungary
fYear
2011
fDate
21-22 Nov. 2011
Firstpage
587
Lastpage
589
Abstract
Nowadays grammar induction is an intensively investigated area and it is a NP-hard problem. TBL [1] [2] and ITBL [3] [4] algorithm provide a way to generate context-free grammar (CFG) from positive and negative sentences. However these algorithms have huge time cost. This paper suggests a prereduction method which can make these algorithm faster. The proposed method performs grammar reduction in the preprocessing step, before execution of genetic algorithm (GA).
Keywords
computational complexity; context-free grammars; genetic algorithms; CFG; NP-hard problem; TBL algorithm; context-free grammar; genetic algorithm; grammar induction; Electronic publishing; Encyclopedias; Genetic algorithms; Grammar; Internet; Production; Training; Grammar Induction; ITBL algorithm; TBL algorithm;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Intelligence and Informatics (CINTI), 2011 IEEE 12th International Symposium on
Conference_Location
Budapest
Print_ISBN
978-1-4577-0044-6
Type
conf
DOI
10.1109/CINTI.2011.6108470
Filename
6108470
Link To Document