Contribution in edited book
Restarting automata and their relations to the Chomsky hierarchy



Publication Details
Authors:
Otto, F.
Editor:
Esik, Z. and Fülöp, Z.
Publisher:
Springer
Place:
Berlin
Publication year:
2003
Pages range:
55-74
Book title:
Developments in Language Theory, Proceedings DLT 2003
Title of series:
Lecture Notes in Computer Science 2710

Abstract
The restarting automaton, introduced by Jancar et al in 1995, is motivated by the so-called 'analysis by reduction,' a technique from linguistics. By now there are many different models of restarting automata, and their investigation has proved very fruitful in that they offer an opportunity to study the influence of various kinds of resources on their expressive power. Here a survey on the various models and their properties is given, their relationships to the language classes of the Chomsky hierarchy are described, and some open problems are presented.


Authors/Editors

Last updated on 2019-25-07 at 11:10