کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426481 686082 2014 27 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
One-way reversible and quantum finite automata with advice
ترجمه فارسی عنوان
اتوماتای ​​محدود با یک روش برگشت پذیر و کوانتومی با مشاوره
کلمات کلیدی
اتوماتیک محدود برگشت پذیر، اتوماتیک محدود کوانتومی، زبان منظم، زبان بدون محتوا، مشاوره تصادفی مشاوره کوانتومی، نوار قابل بازنویسی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We examine the characteristic features of reversible and quantum computations in the presence of supplementary external information, known as advice. In particular, we present a simple, algebraic characterization of languages recognized by one-way reversible finite automata augmented with deterministic advice. With a further elaborate argument, we prove a similar but slightly weaker result for bounded-error one-way quantum finite automata with advice. Immediate applications of those properties lead to containments and separations among various language families when they are assisted by appropriately chosen advice. We further demonstrate the power and limitation of randomized advice and quantum advice when they are given to one-way quantum finite automata.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 239, December 2014, Pages 122–148
نویسندگان
,