کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657902 | 690385 | 2005 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Quantum versus deterministic counter automata
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
This paper focuses on quantum analogues of various models of counter automata, and almost completely proves the relation between the classes of languages recognizable by bounded error quantum ones and classical deterministic ones in every model of counter automata. It is proved that (i) there are languages that can be recognized by two-way quantum one-counter automata with bounded error, but cannot be recognized by two-way deterministic one-counter automata, (ii) under some reasonable restriction, every language that can be recognized by two-way deterministic one-counter automata can also be recognized by two-way reversible one-counter automata (and hence by bounded error two-way quantum one-counter automata), and (iii) for any fixed k, quantum ones and deterministic ones are incomparable in one-way k-counter automata.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 334, Issues 1â3, 15 April 2005, Pages 275-297
Journal: Theoretical Computer Science - Volume 334, Issues 1â3, 15 April 2005, Pages 275-297
نویسندگان
Tomohiro Yamasaki, Hirotada Kobayashi, Hiroshi Imai,