Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-19T04:29:59.012Z Has data issue: false hasContentIssue false

On the classes of languages accepted by limited contextrestarting automata∗∗∗∗∗∗

Published online by Cambridge University Press:  10 February 2014

Friedrich Otto
Affiliation:
Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany. otto@theory.informatik.uni-kassel.de
Peter Černo
Affiliation:
Charles University, Faculty of Mathematics and Physics, Department of Computer Science, Malostranské nám. 25, 11800 Praha 1, Czech Republic; petercerno@gmail.com; mraz@ksvi.ms.mff.cuni.cz
František Mráz
Affiliation:
Charles University, Faculty of Mathematics and Physics, Department of Computer Science, Malostranské nám. 25, 11800 Praha 1, Czech Republic; petercerno@gmail.com; mraz@ksvi.ms.mff.cuni.cz

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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