Learning picture languages using restarting automata

• Thesis title in Czech: Učení jazykových obrázků pomocí restartovacích automatů
• Thesis title in English: Learning picture languages using restarting automata
• Key words: picture language, grammatical inference, restarting automaton
• English key words: picture language, grammatical inference, restarting automaton
• Academic year of topic announcement: 2013/2014
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Software and Computer Science Education (32-KSVI)
• Supervisor: RNDr. František Mráz, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 04.12.2013
• Date of assignment: 18.12.2013
• Confirmed by Study dept. on: 20.12.2013
• Date and time of defence: 27.05.2014 00:00
• Date of electronic submission: 11.04.2014
• Date of submission of printed version: 11.04.2014
• Date of proceeded defence: 27.05.2014
• Opponents: RNDr. Daniel Průša, Ph.D.

Guidelines

The goal is to propose a new model of restarting automaton working on two-dimensional inputs - pictures - together with an algorithm for learning such automata from positive and negative samples of pictures. The proposed model of automata will be compared to some other models for picture language recognition like sgraffito automaton or restarting tiling automaton. Further, the proposed learning algorithm will be implemented and evaluated experimentally.

References

[1] Basovnik, S.: Learning Restricted Restarting Automata using Genetic Algorithm, Master's thesis, Charles University, Faculty of Mathematics and Physics, 2010.

[2] Průša, D., Mráz, F.: Restarting tiling automata. Proceedings of the CIAA 2012 17th International Conference on Implementation and Application of Automata (Porto, Portugal), 2012, LNCS, Vol. 7381, Springer, Berlin, 289-300.

[3] Mráz, F., Otto, F.: Extended Two-Way Ordered Restarting Automata for Picture Languages, LATA 2014, LNCS, Springer, 2014, to appear.

[4] Mráz, F., Otto, F.: Ordered Restarting Automata for Picture Languages. In: V. Geffert et al. (Eds.): SOFSEM 2014, LNCS 8327, pp. 431--442. Springer International Publishing Switzerland (2014).

[5] Průša, D., Mráz, F.: Two-dimensional Sgraffito automata. Proceedings of the DLT 2012 16th International Conference on Developments in Language Theory (Taipei, Taiwan), 2012, LNCS, Vol. 7410, pp. 251-262, Berlin: Springer.