Lower bounds on the size of semi-quantum finite automata

DOI10.1016/J.TCS.2015.09.031MaRDI QIDQ264532zbMATH OpenOpenAlexFDO

Authors Lvzhou Li, Daowen Qiu

Publication date 31 March 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

descriptional complexityquantum finite automatasemi-quantum finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: In the literature, there exist several interesting hybrid models of finite automata which have both quantum and classical states. We call them semi-quantum automata. In this paper, we compare the descriptional power of these models with that of DFA. Specifically, we present a uniform method that gives a lower bound on the size of the three existing main models of semi-quantum automata, and this bound shows that semi-quantum automata can be at most exponentially more concise than DFA. Compared with a recent work (Bianchi, Mereghetti, Palano, Theoret. Comput. Sci., 551(2014), 102-115), our method shows the following two advantages: (i) our method is much more concise; and (ii) our method is universal, since it is applicable to the three existing main models of semi-quantum automata, instead of only a specific model.

Recommendations

• Size lower bounds for quantum automata
• Size lower bounds for quantum automata
• On the state complexity of semi-quantum finite automata
• On the state complexity of semi-quantum finite automata
• On hybrid models of quantum finite automata

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 2040892 (Why is no real title available?)
• Characterizations of one-way general quantum finite automata
• Exponentially more concise quantum recognition of non-RMM regular languages
• On hybrid models of quantum finite automata
• On the power of one-way automata with quantum and classical states
• On the state complexity of semi-quantum finite automata
• One-way finite automata with quantum and classical states
• Quantum finite automata with control language
• Size lower bounds for quantum automata
• Two-way finite automata with quantum and classical states.

Cited in

(9)

• On the state complexity of semi-quantum finite automata
• On the state complexity of semi-quantum finite automata
• Size lower bounds for quantum automata
• Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game
• On hybrid models of quantum finite automata
• Lower Bounds for Generalized Quantum Finite Automata
• Size lower bounds for quantum automata
• Application of distributed semi-quantum computing model in phase estimation
• scientific article; zbMATH DE number 2044497 (Why is no real title available?)

This page was built for publication: Lower bounds on the size of semi-quantum finite automata

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