Clearing Restarting Automata

• Autorzy: Černo P. , Mráz F.
• Języki publikacji: EN

Abstrakty

EN

Restarting automata were introduced as a model for analysis by reduction, which is a linguistically motivated method for checking correctness of a sentence. We propose a new restricted version of restarting automata called clearing restarting automata with a very simple definition but simultaneously with interesting properties with respect to their possible applications. The new model can be learned very efficiently from positive examples and its stronger version can be used to learn effectively a large class of languages. We relate the class of languages recognized by clearing restarting automata to the Chomsky hierarchy.

Słowa kluczowe

EN

analysis by reduction; clearing restarting automata; formal languages; grammatical inference problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 1/2
• Strony: 17--54
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Černo P.

autor

Mráz F.

• Department of Computer Science, Charles University, Faculty of Mathematics and Physics, Malostranskénam. 25, 118 00 PRAHA 1, Czech Republic,

Bibliografia

• [1] Cherubini, A., Reghizzi, S. C., Pietro, P. S.: Associative language descriptions, Theoretical Computer Science, 270(1-2), 2002, 463-492.
• [2] Greibach, S. A.: The hardest context-free language, SIAM Journal on Computing, 2(4), 1973, 304-310.
• [3] Hofbauer, D., Waldmann, J.: Deleting string rewriting systems preserve regularity, Theoretical Computer Science, 327(3), 2004, 301-317.
• [4] Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting Automata, Fundamentals of Computation Theory, FCT 1995, Proc. (H. Reichel, Ed.), LNCS 965, Springer, 1995, 283-292.
• [5] Jančar, P., Mráz, F., Plátek, M., Vogel, J.: On Restarting Automata with Rewriting, New Trends in Formal Languages (G. Paun, A. Salomaa, Eds.), LNCS 1218, Springer, 1997, 119-136.
• [6] 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-312.
• [7] Kutrib, M., Messerschmidt, H., Otto, F.: On stateless two-pushdown automata and restarting automata, Automata and Formal Languages, AFL, Proc. (E. Csuhaj-Varj´u, Z. ´ Esik, Eds.), Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, 2008), 257-268.
• [8] Lopatková, M., Plátek, M., Kubon, V.: Modeling Syntax of Free Word-Order Languages: Dependency Analysis by Reduction, Text, Speech and Dialogue, TSD 2005, Proceedings (V. Matoušek, P. Mautner, T. Pavelka, Eds.), LNCS 3658, Springer, 2005, 140-147.
• [9] Marcus, S.: Contextual Grammars, Revue Roum. Mathy. Pures Appl., 14(10), 1969, 1525-1534.
• [10] Maurer, H. A., Salomaa, A. K., Wood, D.: Pure grammars, Information and Control, 44(1), 1980, 47-72.
• [11] McNaughton, R., Narendran, P., Otto, F.: Church-Rosser Thue systems and formal languages, Journal of the ACM (JACM), 35(2), 1988, 324-344.
• [12] Mráz, F., Otto, F., Plátek, M.: Learning Analysis by Reduction from Positive Data, Grammatical Inference: Algorithms and Applications, ICGI 2006, Proc. (Y. Sakakibara, S. Kobayashi, K. Sato, T. Nishino, E. Tomita, Eds.), LNCS 4201, Springer, 2006, 125-136.
• [13] Otto, F.: Restarting Automata and Their Relations to the Chomsky Hierarchy, Developments in Language Theory, DLT 2003, Proc. (Z. ´ Esik, Z. Fül¨op, Eds.), LNCS 2710, Springer, 2003, 55-74.
• [14] Pǎun, G.: Marcus Contextual Grammars, vol. 67 of Studies in Linguistics and Philosophy, Springer, 1998.
• [15] Rozenberg, G., Salomaa, A., Eds.: Handbook of Formal Languages, Volume I, Berlin: Springer, 1997.