Electronic Proceedings in Theoretical Computer Science (Oct 2012)

A Myhill-Nerode theorem for automata with advice

  • Alex Kruckman,
  • Sasha Rubin,
  • John Sheridan,
  • Ben Zax

DOI
https://doi.org/10.4204/EPTCS.96.18
Journal volume & issue
Vol. 96, no. Proc. GandALF 2012
pp. 238 – 246

Abstract

Read online

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.