A Myhill-Nerode theorem for automata with advice

Alex Kruckman
(Berkeley University) 		Sasha Rubin
(TU Vienna and IST Austria) 		John Sheridan
Ben Zax

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.

In Marco Faella and Aniello Murano: Proceedings Third International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2012), Napoli, Italy, September 6-8, 2012, Electronic Proceedings in Theoretical Computer Science 96, pp. 238–246.
Published: 7th October 2012.
ArXived at: https://dx.doi.org/10.4204/EPTCS.96.18 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org