ON THE POWER OF TWO-WAY MULTIHEAD QUANTUM FINITE AUTOMATA

被引：6

作者：

Bhatia, Amandeep Singh ^{[1
]}

Kumar, Ajay ^{[1
]}

机构：

[1] Thapar Inst Engn & Technol, Dept Comp Sci, Patiala, Punjab, India

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2019年 / 53卷 / 1-2期

关键词：

Two-way deterministic finite automata (2DFA); two-way reversible finite automata (2RFA); two-way deterministic multihead finite automata (DMFA); two-way reversible multihead finite automata (RMFA); two-way quantum finite automata (2QFA); two-way multihead quantum finite automata (2MQFA); EQUIVALENCE; COMPLEXITY;

D O I：

10.1051/ita/2018020

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper introduces a variant of two-way quantum finite automata named two-way multihead quantum finite automata. A two-way quantum finite automaton is more powerful than classical two-way finite automata. However, the generalizations of two-way quantum finite automata have not been defined so far as compared to one-way quantum finite automata model. We have investigated the newly introduced automata from two aspects: the language recognition capability and its comparison with classical and quantum counterparts. It has been proved that a language which cannot be recognized by any one-way and multi-letter quantum finite automata can be recognized by two-way quantum finite automata. Further, it has been shown that a language which cannot be recognized by two-way quantum finite automata can be recognized by two-way multihead quantum finite automata with two heads. Furthermore, it has been investigated that quantum variant of two-way deterministic multihead finite automata takes less number of heads to recognize a language containing of all words whose length is a prime number.

引用

页码：19 / 35

页数：17

共 44 条

[1]

Amano M., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P368, DOI 10.1145/301250.301344

[2] Two-way finite automata with quantum and classical states [J].

Ambainis, A ;

Watrous, J .

THEORETICAL COMPUTER SCIENCE, 2002, 287 (01) :299-311

[3]

[Anonymous], 2 WAY DETERMINISTIC

[4]

[Anonymous], ARXIV160700811

[5]

[Anonymous], INT WORKSH REV COMP

[6]

[Anonymous], 2013, LNCS, DOI DOI 10.1007/978-3-642-36315-3_3

[7]

[Anonymous], APPL MATH IRVINE

[8]

[Anonymous], ARXIV09063051

[9]

[Anonymous], 1024 TURK CTR COMP S

[10]

[Anonymous], P 28 ANN ACM S THEOR

← 1 2 3 4 5 →