|
28th Annual Conference on Current
Trends in
Theory and Practice of Informatics
|
|
November 24 - December 1, 2001
|
|
Two-way Restarting Automata and j-Monotonicity
by Martin Platek
Abstract:
We introduce in this paper restarting automata as two-way automata in order
to obtain a more general model which is closer to our linguistic
motivations. To show the advantages of this model we study the notion of
j-monotonicity. We show that the j-monotonicity can be considered as a
degree of non-context-freeness and that it is a robust notion due to the
considered models of restarting automata. Some other aspects of two-way
restarting automata are mentioned.