Exponentially more concise quantum recognition of non-RMM regular languages

作者：

Highlights：

• We introduce one-way quantum finite automata together with classical states (1QFAC).

• We prove that 1QFAC are at most exponentially more concise than DFA.

• We give a polynomial-time algorithm for determining the equivalence of 1QFAC.

• We show that the state minimization of 1QFAC is decidable within EXPSPACE.

摘要

•We introduce one-way quantum finite automata together with classical states (1QFAC).•We prove that 1QFAC are at most exponentially more concise than DFA.•We give a polynomial-time algorithm for determining the equivalence of 1QFAC.•We show that the state minimization of 1QFAC is decidable within EXPSPACE.

论文关键词：Quantum finite automata,Equivalence,Regular languages,Deterministic finite automata,Decidability,State complexity

论文评审过程：Received 2 June 2012, Accepted 4 June 2014, Available online 27 June 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.06.008