Beitrag in einem Sammelband
Restarting automata and their relations to the Chomsky hierarchy
Details zur Publikation
Autor(inn)en: | Otto, F. |
Herausgeber: | Esik, Z. and Fülöp, Z. |
Verlag: | Springer |
Verlagsort / Veröffentlichungsort: | Berlin |
Publikationsjahr: | 2003 |
Seitenbereich: | 55-74 |
Buchtitel: | Developments in Language Theory, Proceedings DLT 2003 |
Titel der Buchreihe: | Lecture Notes in Computer Science 2710 |
Zusammenfassung, 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.
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.
Projekte
