zbMATH — the first resource for mathematics

Automata that take advice. (English) Zbl 1193.68152
Wiedermann, Jiří (ed.) et al., Mathematical foundations of computer science 1995. 20th international symposium, MFCS ’95, Prague, Czech Republic, August 28-September 1, 1995. Proceedings. Berlin: Springer-Verlag (ISBN 3-540-60246-1). Lect. Notes Comput. Sci. 969, 149-158 (1995).
Summary: Karp and Lipton introduced advice-taking Turing machines to capture nonuniform complexity classes. We study this concept for automata-like models and compare it to other nonuniform models studied in connection with formal languages in the literature. Based on this we obtain complete separations of the classes of the Chomsky hierarchy relative to advices.
For the entire collection see [Zbl 0847.00052].

68Q45 Formal languages and automata
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI