Regular language induction with genetic programming
Created by W.Langdon from
gp-bibliography.bib Revision:1.8028
- @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