کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9657902 690385 2005 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Quantum versus deterministic counter automata
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Quantum versus deterministic counter automata
چکیده انگلیسی
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
نویسندگان
, , ,