On the classes of languages accepted by limited context restarting automata

Friedrich Otto; Peter Černo; František Mráz

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

  • Volume: 48, Issue: 1, page 61-84
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Otto, Friedrich, Černo, Peter, and 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 48.1 (2014): 61-84. <http://eudml.org/doc/273071>.

@article{Otto2014,
abstract = {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.},
author = {Otto, Friedrich, Černo, Peter, Mráz, František},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {restarting automaton; contextual rewriting; mcnaughton family of languages},
language = {eng},
number = {1},
pages = {61-84},
publisher = {EDP-Sciences},
title = {On the classes of languages accepted by limited context restarting automata},
url = {http://eudml.org/doc/273071},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Otto, Friedrich
AU - Černo, Peter
AU - Mráz, František
TI - On the classes of languages accepted by limited context restarting automata
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 1
SP - 61
EP - 84
AB - 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.
LA - eng
KW - restarting automaton; contextual rewriting; mcnaughton family of languages
UR - http://eudml.org/doc/273071
ER -

References

top
  1. [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. [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. [3] M. Beaudry, M. Holzer, G. Niemann and F. Otto, McNaughton families of languages. Theoret. Comput. Sci.290 (2003) 1581–1628. Zbl1044.68082MR1937737
  4. [4] R.V. Book and F. Otto, String-Rewriting Systems. Springer, New York (1993). Zbl0832.68061MR1215932
  5. [5] J.R. Büchi, Regular canonical systems. Arch. f. Math. Logik Grundlagenf. 6 (1964) 91–111. Zbl0129.26102MR169410
  6. [6] G. Buntrock,Wachsende kontext-sensitive Sprachen. Habilitationsschrift. Fakultät für Mathematik und Informatik, Universität Würzburg (1996). 
  7. [7] G. Buntrock and F. Otto, Growing context-sensitive languages and Church-Rosser languages. Inf. Comput.141 (1998) 1–36. Zbl0894.68093MR1604216
  8. [8] J. Čejka, Learning correctness preserving reduction analysis. BSc Project, Charles University. Faculty of Mathematics and Physics, Prague, Czech (2003). 
  9. [9] P. Černo and F. Mráz, Clearing restarting automata. Fund. Inf.104 (2010) 17–54. Zbl1214.68190MR2791739
  10. [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. Zbl1221.68121
  11. [11] E. Dahlhaus and M. Warmuth, Membership for growing context-sensitive grammars is polynomial. J. Comput. System Sci.33 (1986) 456–472. Zbl0625.68055MR869136
  12. [12] D. Hofbauer and J. Waldmann, Deleting string rewriting systems preserve regularity. Theoret. Comput. Sci.327 (2004) 301–317. Zbl1071.68034MR2098310
  13. [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. [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. MR1627253
  15. [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. Zbl0942.68064MR1737858
  16. [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. Zbl0188.04902MR255472
  17. [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. Zbl1251.68136MR2918607
  18. [18] R. McNaughton, P. Narendran and F. Otto, Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach.35 (1988) 324–344. Zbl0652.68093MR935255
  19. [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. Zbl1158.68412MR2333257
  20. [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. Zbl1075.68046MR2126360
  21. [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. Zbl1073.68050MR1964172
  22. [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. Zbl0645.03033MR919471
  23. [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. Zbl1116.68044
  24. [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. [25] J. Woinowski, The context-splittable normal form for Church-Rosser language systems. Inform. Comput.183 (2003) 245–274. Zbl1054.68082MR1995046

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.