Power of S-kR-RRWW-automata

• Autorzy: Hoffmann P.

Identyfikatory

DOI

10.3233/FI-2015-1145

• Języki publikacji: EN

Abstrakty

EN

Single k-reversible restarting automata are a special version of restarting automata which can be effectively learned from samples. We show that their power lies between GCSL and CSL. We show that their subclasses form an infinite hierarchy of classes of languages with respect to the reversibility level k and we also show that limiting types of allowed rewrites lowers the power of the model. Finally, we study their relation to strictly locally testable restarting automata.

Słowa kluczowe

EN

mathematical models; simulation methods; simulation model; machine theory; robots

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 1/2
• Strony: 85--112
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Hoffmann P.

• Faculty of Mathematics and Physics Charles University in Prague, Malostransk´e n´am. 25, 118 00, Praha 1, Czech Republic

Bibliografia

• [1] Amar, V., Putzolu, G.: On a family of linear grammars, Information and Control, 7, 1964, 283–291.
• [2] Angluin, D.: Inference of reversible languages, JACM, 29(3), 1982, 741–765.
• [3] Buntrock, G.: Wachsende kontextsensitive Sprachen, Habilitation thesis, Universität Würzburg, 1996.
• [4] Dahlhaus, E.,Warmuth, M. K.: Membership for growing context-sensitive grammars is polynomial, Journal of Computer System Sciences, 33(3), 1986, 456–472.
• [5] Hoffmann, P.: Machine learning of analysis by reduction, Phd-thesis, Charles University in Prague, 2013, Available from www: <https://is.cuni.cz/webapps/zzp/detail/42351>.
• [6] Hopcroft, J. E., Ullman, J. D., Motwani, R.: Introduction to automata theory, languages, and computation, 2nd edition, Reading : Addison-Wesley, 2001, ISBN 0201441241.
• [7] Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata, FCT’95, Proceedings (H. Reichel, Ed.), 965, Springer, 1995.
• [8] 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.
• [9] Kobayashi, S., Yokomori, T.: Learning concatenations of locally testable languages from positive data, AII ’94, ALT ’94, Proceedings (S. Arikawa, K. P. Jantke, Eds.), 872, Springer, 1994.
• [10] Lautemann, C.: One pushdown and a small tape, Dirk Siefkes zum 50. Geburtstag (K. W. Wagner, Ed.), Technische Universität Berlin and Universität Augsburg, 1988.
• [11] Linz, P.: An introduction to formal languages and automata, Lexington : D. C. Heath, 1990.
• [12] Lopatková,M., Plátek,M., Kuboˇn, V.: Modelling syntax of free word-order languages: Dependency analysis by reduction, TSD 2005, Proceedings (V. Matoušek, P. Mautner, T. Pavelka, Eds.), 3658, Springer, 2005.
• [13] McNaughton, R.: The loop complexity of pure-group events, Information and Control, 11(1–2), 1967, 167–176.
• [14] Mráz, F., Otto, F., Plátek, M.: Learning analysis by reduction from positive data, ICGI 2006, Proceedings (Y. Sakakibara, S. Kobayashi, K. Sato, T. Nishino, E. Tomita, Eds.), 4201, Springer, 2006.
• [15] Mráz, F., Plátek, M., Procházka, M.: On Special Forms of Restarting Automata, Grammars, 2(3), 1999, 223–233.
• [16] Otto, F.: Restarting automata and their relation to the Chomsky hierarchy, DLT 2003, Proceedings (Z. Esik, Z. Fülöp, Eds.), 2710, Springer, 2003.
• [17] Otto, F.: Restarting automata, in: Recent Advances in Formal Languages and Applications (Z. Esik, C. Martín-Vide, V. Mitrana, Eds.), vol. 25 of Studies in Computational Intelligence, Springer, Berlin, 2006, 269–303.
• [18] Plátek, M., Lopatková, M., Oliva, K.: Restarting automata: motivations and applications, Workshop ’Petrinetze’ and 13. Theorietag ’Formale Sprachen und Automaten’, Proceedings (M. Holzer, Ed.), Institut für Informatik, Technische Univ. München, 2003.
• [19] Sempere, J., Garca, P.: Learning Locally Testable Even Linear Languages from Positive Data, in: Grammatical Inference: Algorithms and Applications (P. Adriaans, H. Fernau, M. Zaanen, Eds.), vol. 2484 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2002, ISBN 978-3-540-44239-4, 225–236.
• [20] Yokomori, T., Kobayashi, S.: Learning local languages and their application to DNA sequence analysis, IEEE Transactions on Pattern Analysis Machine Intelligence, 20(10), 1998, 1067–1079.