Clearing Restarting Automata

• Thesis title in Czech: Clearing Restarting Automata
• Thesis title in English: Clearing Restarting Automata
• Academic year of topic announcement: 2009/2010
• 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: 12.01.2010
• Date of assignment: 12.01.2010
• Date and time of defence: 13.09.2010 00:00
• Date of electronic submission: 13.09.2010
• Date of proceeded defence: 13.09.2010
• Opponents: RNDr. Petr Hoffmann, Ph.D.

Guidelines

Restarting automata were introduced as a model for analysis by reduction which is a linguistically motivated method for checking correctness of a sentence. The goal of the thesis is to study more restricted models of restarting automata which based on a limited context can either delete a substring of the current content of its tape or replace a substring by a special symbol which cannot be overwritten anymore, but it can be deleted later. Such restarting automata are called clearing restarting automata. The thesis will investigate the properties of clearing restarting automata, their relation to Chomsky hierarchy and possibilities for machine learning of such automata from positive and negative samples.

Keywords: analysis by reduction, clearing restarting automata, formal languages, grammatical inference

References

Cherubini, A., Reghizzi, S.C., Pietro, P.S.: Associative language descriptions, Theoretical Computer Science, 270 (2002), 463-491.

Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: H. Reichel (Ed.), FCT'95, LNCS, Vol. 965, Springer, Berlin, 1995, 283-292.

Jančar, P., Mráz, F., Plátek, M., Vogel, J.: On monotonic automata with a restart operation, Journal of Automata, Languages and Combinatorics, 4(4) (1999), 287-311.

Mateescu, A., Salomaa, A.: Aspects of classical language theory, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 1, Chapter 4, Springer, Berlin, 1997, 175-251.

Mráz, F., Otto, F., Plátek, M.: Learning analysis by reduction from positive data. In: Y. Sakakibara, S. Kobayashi, K. Sato, T. Nishino, E. Tomita (Eds.), Proceedings ICGI 2006, LNCS, Vol. 4201, Springer, Berlin, 2006, 125-136.