Regular language induction with genetic programming

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

  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
  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