Some languages recognized by two-way finite automata with quantum and classical states

DOI10.1142/S0129054112500141MaRDI QIDQ4902896zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Shenggen Zheng, Lvzhou Li, Daowen Qiu

Publication date 18 January 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.2844

zbMATH Keywords

quantum finite automatacomputing modelsprobabilistic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: {it Two-way finite automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous, and it was shown that 2QCFA have superiority over {it two-way probabilistic finite automata} (2PFA) for recognizing some non-regular languages such as the language $L_{eq}=a^n{b}^{n}midninmathbfN$ and the palindrome language $L_{pal}=omegain{a,b}^{\ast }midomega=omeg{a}^R$, where $x^R$ is $x$ in the reverse order. It is interesting to find more languages like these that witness the superiority of 2QCFA over 2PFA. In this paper, we consider the language $L_m=xcymidSigma=a,b,c,x,yin{a,b}^{\ast },cinSigma,|x|=|y|$ that is similar to the middle language $L_{middle}=xaymidx,yinSigm{a}^{\ast },ainSigma,|x|=|y|$. We prove that the language $L_m$ can be recognized by 2QCFA with one-sided error in polynomial expected time. Also, we show that $L_m$ can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus $L_m$ is another witness of the fact that 2QCFA are more powerful than their classical counterparts.

Recommendations

• Two-way finite automata with quantum and classical states.
• State succinctness of two-way finite automata with quantum and classical states
• Two-tape finite automata with quantum and classical states
• Succinctness of two-way probabilistic and quantum finite automata
• scientific article; zbMATH DE number 1512863

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3255204 (Why is no real title available?)
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• A lower bound for probabilistic algorithms for finite state machines
• A note on quantum sequential machines
• Algebraic results on quantum automata
• Characterizations of 1-Way Quantum Finite Automata
• Determining the equivalence for one-way quantum finite automata
• Efficient probability amplification in two-way quantum finite automata
• Finite state verifiers I
• Hierarchy and equivalence of multi-letter quantum finite automata
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum automata and quantum grammars
• Two-tape finite automata with quantum and classical states
• Two-way finite automata with quantum and classical states.
• Unbounded-error quantum computation with small space bounds

Cited in

(9)

• State succinctness of two-way finite automata with quantum and classical states
• Two-tape finite automata with quantum and classical states
• From quantum query complexity to state complexity
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Two-way finite automata with quantum and classical states.
• Potential of quantum finite automata with exact acceptance
• scientific article; zbMATH DE number 6533717 (Why is no real title available?)
• On the power of two-way multihead quantum finite automata
• Application of distributed semi-quantum computing model in phase estimation

This page was built for publication: Some languages recognized by two-way finite automata with quantum and classical states

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4902896)