Quantum algorithm for Dyck language with multiple types of brackets

DOI10.1007/978-3-030-87993-8_5OpenAlexW3208764542MaRDI QIDQ2152087

Dmitry Kravchenko, Kamil Khadiev

Publication date: 6 July 2022

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

zbMATH Keywords

quantum algorithmsstringsregular languagequery complexityDyck language

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Other nonclassical models of computation (68Q09) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Related Items (2)

Quantum algorithm for dynamic programming approach for DAGs and applications ⋮ Quantum bounds for 2D-grid and Dyck language

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simulation methods for quantum walks on graphs applied to formal language recognition
• Quantum-over-classical advantage in solving multiplayer games
• Quantum algorithm for dynamic programming approach for DAGs. Applications for Zhegalkin polynomial evaluation and some problems on DAGs
• On the quantum and classical complexity of solving subtraction games
• Upperbounds on the probability of finding marked connected components using quantum walks
• Quantum Computation and Quantum Information
• Testing membership in parenthesis languages
• UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY

This page was built for publication: Quantum algorithm for Dyck language with multiple types of brackets