2012/10/09 by Alex Kruckman, Sasha Rubin, John Sheridan +1
Computer Science · #cs.FL #cs.LO
paper · pdf · doi:10.4204/eptcs.96.18
published as EPTCS 96, 2012, pp. 238-246 · In Proceedings GandALF 2012, arXiv:1210.2028
arxiv created 2012/10/09 · arxiv updated 2012/10/10
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.