Journal article
Degrees of non-monotonicity for restarting automata
Publication Details
Authors: | Jurdzinski, T.; Mraz, F.; Otto, F.; Platek, M. |
Publication year: | 2006 |
Journal: | Theoretical Computer Science |
Pages range : | 1-34 |
Volume number: | 369 |
ISSN: | 0304-3975 |
Abstract
In the literature various notions of monotonicity for restarting automata have been studied. Here we introduce two new variants of monotonicity for restarting automata and for two-way restarting automata: left-monotonicity and right-left-monotonicity. It is shown that for the various types of deterministic and nondeterministic (two-way) restarting automata without auxiliary symbols, these notions yield infinite hierarchies, and we compare these hierarchies to each other. Further, as a tool used to simplify some of the proofs, the shrinking restarting automaton is introduced, which is a generalization of the standard (length-reducing) restarting automaton to the weight-reducing case. Some of the consequences of this generalization are also discussed. (c) 2006 Elsevier B.V. All rights reserved.
In the literature various notions of monotonicity for restarting automata have been studied. Here we introduce two new variants of monotonicity for restarting automata and for two-way restarting automata: left-monotonicity and right-left-monotonicity. It is shown that for the various types of deterministic and nondeterministic (two-way) restarting automata without auxiliary symbols, these notions yield infinite hierarchies, and we compare these hierarchies to each other. Further, as a tool used to simplify some of the proofs, the shrinking restarting automaton is introduced, which is a generalization of the standard (length-reducing) restarting automaton to the weight-reducing case. Some of the consequences of this generalization are also discussed. (c) 2006 Elsevier B.V. All rights reserved.
Projects
