@inproceedings{c98f8b1fd2c24e9895bd51ab50f8f89e,
title = "Quantum Algorithm for Dyck Language with Multiple Types of Brackets",
abstract = "We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity O(n(logn)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 Ω(nck) for some constant c. Interestingly, classical algorithms solving the Dyck Language for multiple types of brackets substantially differ from the algorithm solving the original Dyck language. At the same time, quantum algorithms for solving both kinds of the Dyck language are of similar nature and requirements.",
keywords = "Dyck language, Quantum algorithms, Query complexity, Regular language, Strings",
author = "Kamil Khadiev and Dmitry Kravchenko",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.",
year = "2021",
language = "English",
isbn = "9783030879921",
volume = "12984 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "68--83",
booktitle = "Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings",
address = "Germany",
}