One-Way Quantum Finite Automata and Advice (Preliminary Version)

スポンサーリンク

概要

• 論文の詳細を見る

• We show containments and separations among language families defined by bounded-error one-way quantum finite automata whose computations are further helped by various types of "advice." Beside standard deterministic advice, we also study randomized advice and quantum advice. The presence of advice demands quite different approaches toward an analysis of the computational power of underlying one-way quantum finite automata. We discover new machine-independent characterizations and develop new proof techniques, which lead us to obtain the desired containments and separations.

• 一般社団法人情報処理学会の論文
• 2009-11-20

著者

• Tomoyuki Yamakami

  Department Of Information Science University Of Fukui

関連論文

• Nondeterministic Pushdown Automata with Write-Only Output Tapes and Definable Function Classes (Preliminary Report)
• Verification Procedures of Assisted Proofs by One-Way Finite Automata
• One-Way Quantum Finite Automata and Advice (Preliminary Version)

スポンサーリンク