A Myhill-Nerode theorem for automata with advice
  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. 
Alex Kruckman (Berkeley University), Sasha Rubin (TU Vienna and IST   Austria), John Sheridan, Ben Zax
cs.FL cs.LO