A Myhill Nerode theorem for automata with advice Conference Paper


Author(s): Kruckman, Alex; Rubin, Sasha; Sheridan, John; Zax, Ben
Title: A Myhill Nerode theorem for automata with advice
Title Series: EPTCS
Affiliation IST Austria
Abstract: 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.
Conference Title: GandALF: Games, Automata, Logics and Formal Verification
Volume: 96
Conference Dates: September 6 -8, 2012
Conference Location: Napoli, Italy
Publisher: Open Publishing Association  
Date Published: 2012-10-01
Start Page: 238
End Page: 246
Copyright Statement: CC BY
URL:
DOI: 10.4204/EPTCS.96.18
Open access: yes (OA journal)
IST Austria Authors
  1. Sasha Rubin
    5 Rubin
Related IST Austria Work