On the Complexity of 2-Monotone Restarting Automata |
| |
Authors: | Tomasz Jurdziński Friedrich Otto Franti?ek Mráz Martin Plátek |
| |
Affiliation: | 1.Institute of Computer Science,University of Wroc?aw,Wroc?aw,Poland;2.Fachbereich Elektrotechnik/Informatik,Universit?t Kassel,Kassel,Germany;3.Department of Computer Science, Faculty of Mathematics and Physics,Charles University,Praha 1,Czech Republic |
| |
Abstract: | The
-automaton is the weakest form of the nondeterministic version of the restarting automaton that was introduced by Jančar et al. to model the so-called analysis by reduction. Here it is shown that the class ℒ(R) of languages that are accepted by
-automata is incomparable under set inclusion to the class
of Church-Rosser languages and to the class
of growing context-sensitive languages. In fact this already holds for the class
of languages that are accepted by 2-monotone
-automata. In addition, we prove that already the latter class contains
-complete languages, showing that already the 2-monotone
-automaton has a surprisingly large expressive power.
The results of this paper have been announced at DLT 2004 in Auckland, New Zealand.
This work was mainly carried out while T. Jurdziński was visiting the University of Kassel, supported by a grant from the
Deutsche Forschungsgemeinschaft (DFG).
F. Mráz and M. Plátek were partially supported by the Grant Agency of the Czech Republic under Grant-No. 201/04/2102 and by
the program ‘Information Society’ under project 1ET100300517. F. Mráz was also supported by the Grant Agency of Charles University
in Prague under Grant-No. 358/2006/A-INF/MFF. |
| |
Keywords: | Restarting automaton Monotonicity " target="_blank">gif" alt="$\mathsf{NP}$" align="middle" border="0"> -completeness Growing context-sensitive language |
本文献已被 SpringerLink 等数据库收录! |
|