Regular language induction with genetic programming
作者： B.D. Dunay , F.E. Petry , B.P. Buckles
关键词: Context-sensitive language 、 Genetic programming 、 DFA minimization 、 Regular language 、 Nondeterministic algorithm 、 Computer science 、 Theoretical computer science 、 Formal language 、 Deterministic finite automaton 、 Low-level programming language
摘要: In this research, inductive inference is done with an informant on the class of regular languages. The approach to evolve formal language accepters which are consistent a set sample strings from language, and known not be in language. Deterministic finite automata (DFA) were chosen as alleviate computational difficulties nondeterministic constructs such rewrite grammars. Genetic programming (GP) offers two significant improvements for induction over genetic algorithms. First, GP allows size solution (the DFA) determined at run time response population pressure. Second, GP's potential assuring correct dependencies complex individuals can exploited assure that all states DFA reachable start state. contribution research effective translation DFAs S-expressions, application renumbering, editing problem induction. or transition tables form basis many problems. By using techniques found paper, these problems directly translated into domain programming. >
sci-hub.se 参考文章(5)
E Mark Gold, Language identification in the limit Information & Computation. ,vol. 10, pp. 447- 474 ,(1967) , 10.1016/S0019-9958(67)91165-5
C. L. Giles, C. B. Miller, D. Chen, H. H. Chen, G. Z. Sun, Y. C. Lee, Learning and extracting finite state automata with second-order recurrent neural networks Neural Computation. ,vol. 4, pp. 393- 405 ,(1992) , 10.1162/NECO.1992.4.3.393
Stephen Wolfram, Computation theory of cellular automata Communications in Mathematical Physics. ,vol. 96, pp. 15- 57 ,(1984) , 10.1007/BF01217347
Hsing-Hen Chen, C. Lee Giles, Guo-Zheng Sun, Dong Chen, Yee-Chun Lee, Higher Order Recurrent Networks and Grammatical Inference neural information processing systems. ,vol. 2, pp. 380- 387 ,(1989)
Raymond L. Watrous, Gary M. Kuhn, Induction of finite-state languages using second-order recurrent networks Neural Computation. ,vol. 4, pp. 406- 414 ,(1992) , 10.1162/NECO.1992.4.3.406