Paper Info
Title
Finite Automata With Advice Tapes
Abstract
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.
Year
DOI
Venue
2013
10.1142/S012905411440019X
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
DocType
Volume
Advised computation, finite automata, random advice
Conference
25
Issue
ISSN
Citations 
8
0129-0541
2
PageRank 
References 
Authors
0.37
15
3
Name
Order
Citations
PageRank
Ugur Küçük120.37
A. C. Cem Say219326.13
Abuzer Yakaryilmaz316825.31