Regular language induction with genetic programming

Created by W.Langdon from gp-bibliography.bib Revision:1.7642

@InProceedings{Dunay:1994:rliGP,

• author = "Bertrand Daniel Dunay and Frederick E. Petry and Bill P Buckles",
• title = "Regular language induction with genetic programming",
• booktitle = "Proceedings of the 1994 IEEE World Congress on Computational Intelligence",
• year = "1994",
• pages = "396--400",
• volume = "1",
• address = "Orlando, Florida, USA",
• month = "27-29 " # jun,
• publisher = "IEEE Press",
• keywords = "genetic algorithms, genetic programming S-expressions, computational difficulties, deterministic finite automata, editing, formal language accepters, inductive inference, informant, population pressure, reachable states, regular language induction, renumbering, run-time determined solution size, sample strings, transition tables, translation, deterministic automata, finite automata, formal languages, inference mechanisms",
• DOI = "doi:10.1109/ICEC.1994.349918",
• size = "5 pages",
• abstract = "In this research, inductive inference is done with an informant on the class of regular languages. The approach is to evolve formal language accepters which are consistent with a set of sample strings from the language, and a set of sample strings known not to be in the language. Deterministic finite automata (DFA) were chosen as the formal language accepters to alleviate the computational difficulties of nondeterministic constructs such as rewrite grammars. Genetic programming (GP) offers two significant improvements for regular language induction over genetic algorithms. First, GP allows the size of the solution (the DFA) to be determined at run time in response to population pressure. Second, GP's potential for assuring correct dependencies in complex individuals can be exploited to assure that all states in a DFA are reachable from the start state. The contribution of this research is the effective translation of DFAs to S-expressions, the application of renumbering, and of editing to the problem of language induction. DFAs or transition tables form the basis of many problems. By using the techniques found in this paper, many of these problems can be directly translated into the domain of genetic programming",
• notes = "Considers two classes of regular language (NB series and Tomita) which can be recognised or accpeted by deterministic finite automata (Finite state machines). Can translate from DFA to tree structure. Trees are not executable programs but represent languages. crossover on trees defined. GP able to define a language given examples of it. Works on simplier examples but has difficulties with 8b, 9b, 10b and TL5.",

}

Genetic Programming entries for Bertrand Daniel Dunay Frederic E Petry Bill Buckles

Citations