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
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;
Conference_Titel :
Computational Intelligence and Informatics (CINTI), 2011 IEEE 12th International Symposium on
Conference_Location :
Budapest
Print_ISBN :
978-1-4577-0044-6
DOI :
10.1109/CINTI.2011.6108470
