headerpos: 12198
 
 
 

Proceedings of the Estonian Academy of Sciences

ISSN 1736-7530 (electronic)   ISSN 1736-6046 (print)
Formerly: Proceedings of the Estonian Academy of Sciences, series Physics & Mathematics and  Chemistry
Published since 1952

Proceedings of the Estonian Academy of Sciences

ISSN 1736-7530 (electronic)   ISSN 1736-6046 (print)
Formerly: Proceedings of the Estonian Academy of Sciences, series Physics & Mathematics and  Chemistry
Published since 1952
Publisher
Journal Information
» Editorial Board
» Editorial Policy
» Archival Policy
» Article Publication Charges
» Copyright and Licensing Policy
Guidelines for Authors
» For Authors
» Instructions to Authors
Guidelines for Reviewers
» For Reviewers
» Review Form
List of Issues
» 2017
» 2016
» 2015
» 2014
» 2013
Vol. 62, Issue 4
Vol. 62, Issue 3
Vol. 62, Issue 2
Vol. 62, Issue 1
» 2012
» 2011
» 2010
» 2009
» 2008
» Back Issues Phys. Math.
» Back Issues Chemistry
» Back issues (full texts)
  in Google. Phys. Math.
» Back issues (full texts)
  in Google. Chemistry
» Back issues (full texts)
  in Google Engineering
» Back issues (full texts)
  in Google Ecology
» Back issues in ETERA Füüsika, Matemaatika jt
Subscription Information
» Prices
Internet Links
Support & Contact
Publisher
» Staff
» Other journals

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


Authors

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.

Keywords

finite state machine, gravitational search algorithm, system identification.

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

Current Issue: Vol. 66, Issue 2 in Press, 2017




Publishing schedule:
No. 1: 20 March
No. 2: 20 June
No. 3: 20 September
No. 4: 20 December