6533b870fe1ef96bd12cf055
RESEARCH PRODUCT
Quantum Algorithm for Dyck Language with Multiple Types of Brackets
Kamil KhadievDmitry Kravchenkosubject
CombinatoricsQuantum queryRegular languageNesting (computing)Dyck languageQuantum algorithmConstant (mathematics)Binary logarithmUpper and lower boundsMathematicsdescription
We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity \(O(\sqrt{n}(\log n)^{0.5k})\), where n is the length of input and k is the maximal nesting depth of brackets. Additionally, we show the lower bound for this problem which is \(\varOmega (\sqrt{n}c^{k})\) for some constant c.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2021-01-01 |