The automatic creation of finite automata has long been a goal of the evolutionary computation community. The previous works in the evolution of finite state automata were limited to the evolution of strictly non-modular FSA. Here, a modular architecture to evolve FSA is proposed and a genetic programming procedure for evolving such structures is presented. Results on the Tomita Language benchmark indicate that the proposed procedure is indeed capable of successfully evolving modular FSA and that such modularity can result in a significantly increased rate of optimization.
References
1.
AhoA.V.SethiR., and UllmanJ.D., Compilers: Principles, Techniques, and Tools.Addison-Wesley, 1988.
2.
HopcroftJ. E.MotwaniR. and UllmanJ.D., Introduction to Automata Theory, Language, and Computation. Pearson Education.2001.
3.
KozaJ. R., Genetic Programming: On the Programming of Computers by Means of Natural Selection.Cambridge, MA, USA: MIT Press. 1992.
4.
ChellapillaK. and CzarneckiD.. “A Preliminary Investigation into Evolving Modular Finite State Machines,”In Congress on Evolutionary Computation, pages 1349–1356, 1999.
5.
ThompsonK., “Regular expression search algorithm,”Communications of the ACM11(6), 419–422. 1968.
6.
TomitaM., “Dynamic Construction Of Finite Automata From Examples Using Hill-Climbing,” In Proceedings of the Fourth Annual Conference of the Cognitive Science Society, 105–108. 1982.
7.
NipamanN. and ChongstivatanaP.. “An Improved Genetic Algorithm for The Inference of Finite State Machine,”In IEEE International Conference on Systems, Man and Cybernetics, pages 1–5, 2002.
8.
ChongstitvatanaP. and AporntewanC.. “Improving Correctness of Finite-State Machine Synthesis from Multiple Partial Input/Output Sequences,” In Workshop on Evolvable Hardware, 1999.
9.
BraveS.. “Evolving deterministic finite automata using cellular encoding,” In Genetic Programming, pages 39–441996.
10.
LukeS. & SpectorL.. “Evolving graphs and networks with edge encoding: Preliminary report”. Late-Breaking Papers of the Genetic Programming1996 Conference.
11.
LucasS. M. and ReynoldsT. J.. “Learning DFA: Evolution versus evidence driven state merging,” In Proceedings of the Congress on Evolutionary Computation (2003), 2003.
12.
JasonW. H. and LuY. H.. “Improving FSM evolution with progressive fitness functions,”Proceedings of the 14th ACM Great Lakes symposium on VLSI.2004.
