Academic Journals Database
Disseminating quality controlled scientific knowledge

A Myhill-Nerode theorem for automata with advice

Author(s): Alex Kruckman | Sasha Rubin | John Sheridan | Ben Zax

Journal: Electronic Proceedings in Theoretical Computer Science
ISSN 2075-2180

Volume: 96;
Issue: Proc. GandALF 2012;
Start page: 238;
Date: 2012;
Original page

An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.
RPA Switzerland

Robotic Process Automation Switzerland


Tango Jona
Tangokurs Rapperswil-Jona