Friedrich Otto

Restarting Automata (eBook, PDF)

The Standard Type of Restarting Automaton and Its Variants

• Format: PDF

Produktbeschreibung

In this unique volume, the expressive capacity of the various types of restarting automata is studied, and the resulting classes of languages are compared to each other and to the classes of an extended Chomsky hierarchy.

A restarting automaton consists of a finite-state control, a flexible tape with end-of-tape markers that initially contains the input, and a read-write window of a fixed finite size. The objective here is to collect the many results that have been obtained on the various types of restarting automata in one place and to present them in a uniform and systematic way.

Among the book's topics and features:

* Delivers a comprehensive survey of the numerous types of restarting automata and results that obtained on them

* Shows how the restarting automaton is motivated by the linguistic technique of 'analysis by reduction'

* Presents the many types of restarting automata in a uniform and systematic way

* Provides a significantly complete list of references on restarting automata

* Offers a text that is accessible to advanced undergraduate and graduate students

Accordingly, this comprehensive monograph may serve as a book of reference for researchers, as a guide to the literature on restarting automata, and as a textbook for an advanced undergraduate or graduate course in formal language and automata theory.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer Nature Switzerland
• Seitenzahl: 409
• Erscheinungstermin: 29. Oktober 2024
• Englisch
• ISBN-13: 9783031700941
• Artikelnr.: 72014282

Autorenporträt

Prof. Dr. Friedrich Otto is affiliated with the University of Kassel. He is a retired associate professor of the Department of Electrical Engineering and Computer Science.

Inhaltsangabe

Introduction.- Analysis by Reduction.- The Restarting Automaton and Its Parameters.- Descriptional Complexity.- Learnability for Restarting Automata.- Appendix A: List of Open Problems.- Appendix B: List of Example Languages.