On the classes of languages accepted by limited context restarting automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 61-84.

In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the word w is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context of McNaughton families of languages, relating the classes of languages accepted by these automata in particular to the class GCSL of growing context-sensitive languages and to the class CRL of Church-Rosser languages.

DOI : https://doi.org/10.1051/ita/2014001
Classification : 68Q45
Mots clés : restarting automaton, contextual rewriting, mcnaughton family of languages
@article{ITA_2014__48_1_61_0,
     author = {Otto, Friedrich and \v{C}erno, Peter and Mr\'az, Franti\v{s}ek},
     title = {On the classes of languages accepted by limited context restarting automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {61--84},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {1},
     year = {2014},
     doi = {10.1051/ita/2014001},
     mrnumber = {3195789},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2014001/}
}
Otto, Friedrich; Černo, Peter; Mráz, František. On the classes of languages accepted by limited context restarting automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 61-84. doi : 10.1051/ita/2014001. http://www.numdam.org/articles/10.1051/ita/2014001/

[1] S. Basovník, Learning restricted restarting automata using genetic algorithm. Master's thesis, Charles University. Faculty of Mathematics and Physics, Prague, Czech (2010).

[2] S. Basovník and F. Mráz, Learning limited context restarting automata by genetic algorithms, in Theorietag, edited by J. Dassow and B. Truthe. Otto-von-Guericke-Universität, Magdeburg (2011) 1-4.

[3] M. Beaudry, M. Holzer, G. Niemann and F. Otto, McNaughton families of languages. Theoret. Comput. Sci. 290 (2003) 1581-1628. | MR 1937737 | Zbl 1044.68082

[4] R.V. Book and F. Otto, String-Rewriting Systems. Springer, New York (1993). | MR 1215932 | Zbl 0832.68061

[5] J.R. Büchi, Regular canonical systems. Arch. f. Math. Logik Grundlagenf. 6 (1964) 91-111. | EuDML 137766 | MR 169410 | Zbl 0129.26102

[6] G. Buntrock,Wachsende kontext-sensitive Sprachen. Habilitationsschrift. Fakultät für Mathematik und Informatik, Universität Würzburg (1996).

[7] G. Buntrock and F. Otto, Growing context-sensitive languages and Church-Rosser languages. Inf. Comput. 141 (1998) 1-36. | MR 1604216 | Zbl 0894.68093

[8] J. Čejka, Learning correctness preserving reduction analysis. BSc Project, Charles University. Faculty of Mathematics and Physics, Prague, Czech (2003).

[9] P. Černo and F. Mráz, Clearing restarting automata. Fund. Inf. 104 (2010) 17-54. | MR 2791739 | Zbl 1214.68190

[10] P. Černo and F. Mráz, Δ-clearing restarting automata and CFL, in edited by G. Mauri and A. Leporati. DLT 2011, in vol. 6795 of Lect. Notes Comput. Sci. Springer, Berlin (2011) 153-164. | Zbl 1221.68121

[11] E. Dahlhaus and M. Warmuth, Membership for growing context-sensitive grammars is polynomial. J. Comput. System Sci. 33 (1986) 456-472. | MR 869136 | Zbl 0625.68055

[12] D. Hofbauer and J. Waldmann, Deleting string rewriting systems preserve regularity. Theoret. Comput. Sci. 327 (2004) 301-317. | MR 2098310 | Zbl 1071.68034

[13] P. Hoffmann, Learning restarting automata by genetic algorithms, in SOFSEM 2002: Student Research Forum, edited by M. Bieliková. Masaryk University, Brno (2002) 15-20.

[14] P. Jančar, F. Mráz, M. Plátek and J. Vogel, Restarting automata, FCT'95, in vol. 965 of Lect. Notes Comput. Sci., edited by H. Reichel. Springer, Berlin (1995) 283-292. | MR 1627253

[15] P. Jančar, F. Mráz, M. Plátek and J. Vogel. On monotonic automata with a restart operation. J. Autom. Lang. Comb. 4 (1999) 287-311. | MR 1737858 | Zbl 0942.68064

[16] D. Knuth and P. Bendix, Simple word problems in universal algebras, in Comput. Problems in Abstract Algebra, edited by J. Leech. Pergamon Press, New York (1970) 263-297. | MR 255472 | Zbl 0188.04902

[17] P. Leupold and F. Otto, On McNaughton families of languages that are specified by some variants of monadic string-rewriting systems. Fund. Inf. 112 (2011) 219-238. | MR 2918607 | Zbl 1251.68136

[18] R. Mcnaughton, P. Narendran and F. Otto, Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach. 35 (1988) 324-344. | MR 935255 | Zbl 0652.68093

[19] F. Mráz, F. Otto and M. Plátek, Learning analysis by reduction from positive data, in ICGI 2006, in vol. 4201 of Lect. Notes Comput. Sci., edited by Y. Sakakibara, S. Kobayashi, K. Sato, T. Nishino and E. Tomita. Springer, Berlin (2006) 125-136. | MR 2333257 | Zbl 1158.68412

[20] G. Niemann and F. Otto, The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inform. Comput. 197 (2005) 1-21. | MR 2126360 | Zbl 1075.68046

[21] G. Niemann and J.R. Woinowski, The growing context-sensitive languages are the acyclic context-sensitive languages, in DLT 2002, in vol. 2295 of Lect. Notes Comput. Sci., edited by W. Kuich, G. Rozenberg and A. Salomaa. Springer, Berlin (2002) 197-205. | MR 1964172 | Zbl 1073.68050

[22] F. Otto, On deciding the confluence of a finite string-rewriting system on a given congruence class. J. Comput. System Sci. 35 (1987) 285-310. | MR 919471 | Zbl 0645.03033

[23] F. Otto, Restarting automata, Recent Advances in Formal Languages and Applications, in vol. 25 of Studies in Comput. Intelligence, edited by Z. Ésik, C. Martin-Vide and V. Mitrana. Springer, Berlin (2006) 269-303. | Zbl 1116.68044

[24] F. Otto, P. Černo and F. Mráz, Limited context restarting automata and McNaughton families of languages, in Fourth Workshop on Non-Classical Models for Automata and Applications (NCMA 2012), Proc., books@ocg.at, Band 290, edited by R. Freund, M. Holzer, B. Truthe and U. Ultes-Nitsche. Oesterreichische Computer Gesellschaft, Wien (2012) 165-180.

[25] J. Woinowski, The context-splittable normal form for Church-Rosser language systems. Inform. Comput. 183 (2003) 245-274. | MR 1995046 | Zbl 1054.68082