Konferenzpaper

Herausgeberliste: Felice, CD; Restivo, R

Jahr der Veröffentlichung: 2005

Seiten: 168-179

Zeitschrift: Lecture notes in computer science

Bandnummer: 3572

ISSN: 0302-9743

ISBN: 3-540-26546-5

eISSN: 1611-3349

Konferenz: 9th International Conference on Developments in Language Theory

Verlag: Springer

Serientitel: Lecture Notes in Computer Science

Abstract: 
We introduce and investigate revolving-input finite automata , which are nondeterministic finite automata with the additional ability to shift the remaining part of the input. We consider three different modes of shifting, namely revolving to the left, revolving to the right, and circular interchanging. We show that the latter operation does not increase the computational power of finite automata, even if the number of revolving operations is unbounded. The same result is obtained for the former two operations in case of an arbitrary but constant number of applications allowed. An unbounded number of these operations leads to language families that are properly contained in the family of context-sensitive languages, are incomparable with the family of context-free Ianguages, and are strictly more powerful than regular languages. Moreover, we show that right revolving can be simulated by left revolving, when considering the mirror image of the input.

Harvard-Zitierstil: Bordihn, H., Holzer, M. and Kutrib, M. (2005) Revolving-input finite automata, Lecture notes in computer science (Schriftenreihe), 3572, pp. 168-179

APA-Zitierstil: Bordihn, H., Holzer, M., & Kutrib, M. (2005). Revolving-input finite automata. Lecture notes in computer science (Schriftenreihe). 3572, 168-179.