Clearing Restarting Automata
| Název práce v češtině: | Clearing Restarting Automata |
|---|---|
| Název v anglickém jazyce: | Clearing Restarting Automata |
| Akademický rok vypsání: | 2009/2010 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra softwaru a výuky informatiky (32-KSVI) |
| Vedoucí / školitel: | RNDr. František Mráz, CSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 12.01.2010 |
| Datum zadání: | 12.01.2010 |
| Datum a čas obhajoby: | 13.09.2010 00:00 |
| Datum odevzdání elektronické podoby: | 13.09.2010 |
| Datum proběhlé obhajoby: | 13.09.2010 |
| Oponenti: | RNDr. Petr Hoffmann, Ph.D. |
| Zásady pro vypracování |
| 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 |
| Seznam odborné literatury |
| 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. |