On the Power of One-Way Automata with Quantum and Classical States

DOI10.1142/S0129054115400055zbMath1330.68144OpenAlexW2228422837MaRDI QIDQ5744127

Maria Paola Bianchi, Beatrice Palano, Carlo Mereghetti

Publication date: 17 February 2016

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

Full work available at URL: https://doi.org/10.1142/s0129054115400055

zbMATH Keywords

regular languagesquantum automatadescriptional complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68)

Cites Work

• Size lower bounds for quantum automata
• Superiority of exact quantum automata for promise problems
• Characterizations of one-way general quantum finite automata
• Quantum automata and quantum grammars
• Two-way finite automata with quantum and classical states.
• Algebraic results on quantum automata
• Quantum automata for some multiperiodic languages
• Small size quantum automata recognizing some regular languages
• Some formal tools for analyzing quantum automata.
• Characterizations of 1-Way Quantum Finite Automata
• On the definition of a family of automata
• Quantum finite automata with control language
• Trace monoids with idempotent generators and measure-only quantum automata

This page was built for publication: On the Power of One-Way Automata with Quantum and Classical States