ESTONIAN ACADEMY
PUBLISHERS
eesti teaduste
akadeemia kirjastus
PUBLISHED
SINCE 1952
 
Proceeding cover
proceedings
of the estonian academy of sciences
ISSN 1736-7530 (Electronic)
ISSN 1736-6046 (Print)
Impact Factor (2020): 1.045

An approach to the inference of finite state machines based on a gravitationally-inspired search algorithm; pp. 39–46

Full article in PDF format | doi: 10.3176/proc.2013.1.05

Author
Margarita Spichakova

Abstract

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.


References

  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

26. Fabera, V., Janes, V., and Janesova, M. Automata construct with genetic algorithm. In DSD ’06: Proceedings of the 9th EUROMICRO Conference on Digital System Design. IEEE Computer Society, Washington, DC, USA, 2006, 460–463.
http://dx.doi.org/10.1109/DSD.2006.28


Back to Issue