Lower bounds on the size of semi-quantum finite automata

DOI10.1016/j.tcs.2015.09.031zbMath1417.68086arXiv1502.02839OpenAlexW2193399559MaRDI QIDQ264532

Lvzhou Li, Dao Wen 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)

Related Items

Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game, Application of distributed semi-quantum computing model in phase estimation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Size lower bounds for quantum automata
• Exponentially more concise quantum recognition of non-RMM regular languages
• Characterizations of one-way general quantum finite automata
• Two-way finite automata with quantum and classical states.
• On hybrid models of quantum finite automata
• One-Way Finite Automata with Quantum and Classical States
• On the Power of One-Way Automata with Quantum and Classical States
• Quantum finite automata with control language
• On the state complexity of semi-quantum finite automata