As the inference of a finite state machine from samples of its behaviour is NP-hard, heuristic search algorithms need to be applied. In this article we propose a methodology based on applying a new gravitationally-inspired heuristic search algorithm for the inference of Moore machines. Binary representation of a Moore machine, an evaluation function, and the required parameters of the algorithm are presented. The experimental results show that this method has a lot of potential.
1. Angluin, D. and Smith, C. H. Inductive inference: theory and methods. ACM Comput. Surv., 1983, 15, 237–269.
http://dx.doi.org/10.1145/356914.356918
2. Gold, E. M. Complexity of automaton identification from given data. Inform. Control, 1978, 37(3), 302–320.
http://dx.doi.org/10.1016/S0019-9958(78)90562-4
3. Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation. International Edition (2nd edn). Addison-Wesley, 2003.
4. Fogel, L. J., Owens, A. J., and Walsh, M. J. Artificial Intelligence Through Simulated Evolution. Wiley, Chichester, UK, 1966.
5. Chellapilla, K. and Czarnecki, D. A preliminary investigation into evolving modular finite state machines. In Proceedings of the 1999 Congress on Evolutionary Computation. Vol. 2. IEEE Press, 1999, 1349–1356.
6. Benson, K. A. Evolving finite state machines with embedded genetic programming for automatic target detection within SAR imagery. In Proceedings of the 2000 Congress on Evolutionary Computation CEC00. IEEE Press, 2000, 1543–1549.
7. Ngom, L., Baron, C., and Geffroy, J. Genetic simulation for finite state machine identification. In SS ’99: Proceedings of the Thirty-Second Annual Simulation Symposium. IEEE Computer Society, Washington, DC, USA, 1999, 118.
8. Tongchim, S. and Chongstitvatana, P. Parallel genetic algorithm for finite state machine synthesis from input/output sequences. In Evolutionary Computation and Parallel Processing (Cantu-Paz, E. and Punch, B., eds). Las Vegas, Nevada, USA, 2000, 20–25.
9. Lucas, S. M. Evolving finite state transducers: some initial explorations. In EuroGP. 2003, 130–141.
10. Lucas, S. M. and Reynolds, T. J. Learning finite state transducers: evolution versus heuristic state merging. IEEE T. Evolut. Comput., 2007, 7, 308–325.
http://dx.doi.org/10.1109/TEVC.2006.880329
11. Niparnan, N. and Chongstitvatana, P. An improved genetic algorithm for the inference of finite state machine. In GECCO ’02: Proceedings of the Genetic and Evolutionary Computation Conference. Morgan Kaufmann Publishers, San Francisco, CA, USA, 2002, 189.
12. Chongstitvatana, P. and Aporntewan, C. Improving correctness of finite-state machine synthesis from multiple partial input/output sequences. In Proceedings of the 1st NASA/DoD Workshop on Evolvable Hardware. 1999, 262–266.
13. Horihan, J. W. and Lu, Y.-H. Improving fsm evolution with progressive fitness functions. In GLSVLSI ’04: Proceedings of the 14th ACM Great Lakes Symposium on VLSI. ACM Press, New York, NY, USA, 2004, 123–126.
http://dx.doi.org/10.1145/988952.988983
14. Cerruti, U., Giacobini, M., and Liardet, P. Prediction of binary sequences by evolving finite state machines. In Selected Papers from the 5th European Conference on Artificial Evolution. Springer-Verlag, London, UK, 2002, 42–53.
15. Rashedi, E., Nezamabadi-pour, H., Saryazdi, S., and Farsangi, M. M. Allocation of static var compensator using gravitational search algorithm. In First Joint Congress on Fuzzy and Intelligent Systems, Ferdowsi University of Mashhad, Iran, 29–31 August, 2007}, 29–31.
16. Formato, R. A. Central force optimization: a new metaheuristic with applications in applied electromagnetics. PIER, 2007, 77, 425–491.
http://dx.doi.org/10.2528/PIER07082403
17. Hsiao, Y.-T., Chuang, C.-L., Jiang, J.-A., and Chien, C.-C. A novel optimization algorithm: space gravitational optimization. In IEEE International Conference on Systems, Man and Cybernetics, 2005, Vol. 3. 2005, 2323–2328.
18. Webster, B. and Bernhard, P. J. A local search optimization algorithm based on natural principles of gravitation. Technical Report CS-2003-10, Florida Institute of Technology, 2003.
19. Webster, B. Solving Combinatorial Optimization Problems Using a New Algorithm Based on Gravitational Attraction. PhD thesis, Florida Institute of Technology, Melbourne, FL, USA, 2004.
20. Rashedi, E., Nezamabadi-pour, H., and Saryazdi, S. GSA: a gravitational search algorithm. Inform. Sciences}, 2009, 179(13), 2232–2248.
http://dx.doi.org/10.1016/j.ins.2009.03.004
21. Rashedi, E., Nezamabadi-pour, H., and Saryazdi, S. Filter modeling using gravitational search algorithm. Eng. Appl. Artif. Intell., 2011, 24, 117–122.
http://dx.doi.org/10.1016/j.engappai.2010.05.007
22. Balachandar, S. R. and Kannan, K. A meta-heuristic algorithm for set covering problem based on gravity. International Journal of Computational and Mathematical Sciences, 2010, 4(5), 223–228.
23. Chatterjee, A., Mahanti, G. K., and Pathak, N. Comparative performance of gravitational search algorithm and modified particle swarm optimization algorithm for synthesis of thinned scanned concentric ring array antenna. PIER B, 2010, 25, 331–348.
http://dx.doi.org/10.2528/PIERB10080405
24. Zibanezhad, B., Zamanifar, K., Nematbakhsh, N., and Mardukhi, F. An approach for web services composition based on QoS and gravitational search algorithm. In Proceedings of the 6th International Conference on Innovations in Information Technology, IIT’09. IEEE Press, Piscataway, NJ, USA, 2009, 121–125.
25. Rashedi, E., Nezamabadi-pour, H., and Saryazdi, S. BGSA: binary gravitational search algorithm. Nat. Comp., 2010, 9, 727–745.
http://dx.doi.org/10.1007/s11047-009-9175-3
http://dx.doi.org/10.1109/DSD.2006.28
