From quantum query complexity to state complexity

被引：6
作者：
Zheng, Shenggen [1 ]
Qiu, Daowen [2 ]
机构：
[1] Faculty of Informatics, Masaryk University, Brno
[2] Department of Computer Science, Sun Yat-sen University, Guangzhou
来源：
Qiu, Daowen | 1600年 / Springer Verlag卷 / 8808期
基金：
中国国家自然科学基金;
关键词：
Finite automata;
D O I：
10.1007/978-3-319-13350-8_18
中图分类号：
学科分类号：
摘要：
State complexity of quantum finite automata is one of the interesting topics in studying the power of quantum finite automata. It is therefore of importance to develop general methods how to show state succinctness results for quantum finite automata. One such method is presented and demonstrated in this paper. In particular, we show that state succinctness results can be derived out of query complexity results. © Springer International Publishing Switzerland 2014.
引用
收藏
页码：231 / 245
页数：14
相关论文
共 50 条
  • [1] STATE COMPLEXITY AND APPROXIMATION
    Gao, Yuan
    Yu, Sheng
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2012, 23 (05) : 1085 - 1098
  • [2] State complexity of power
    Domaratzki, Michael
    Okhotin, Alexander
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (24-25) : 2377 - 2392
  • [3] State complexity of cyclic shift
    不详
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2008, 42 (02): : 335 - 360
  • [4] State complexity of inversion operations
    Cho, Da-Jung
    Han, Yo-Sub
    Ko, Sang-Ki
    Salomaa, Kai
    THEORETICAL COMPUTER SCIENCE, 2016, 610 : 2 - 12
  • [5] State complexity of prefix distance
    Ng, Timothy
    Rappaport, David
    Salomaa, Kai
    THEORETICAL COMPUTER SCIENCE, 2017, 679 : 107 - 117
  • [6] Nondeterminism Growth and State Complexity
    Keeler, Chris
    Salomaa, Kai
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2019, 2019, 11612 : 210 - 222
  • [7] KLEENE CLOSURE AND STATE COMPLEXITY
    Palmovsky, Matus
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2016, 50 (03): : 251 - 261
  • [8] State Complexity and Limited Nondeterminism
    Palioudakis, Alexandros
    Salomaa, Kai
    Akl, Selim G.
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2012, 2012, 7386 : 252 - 265
  • [9] UNCOUNTABLE CLASSICAL AND QUANTUM COMPLEXITY CLASSES
    Dimitrijevs, Maksims
    Yakarylmaz, Abuzer
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2018, 52 (2-4): : 111 - 126
  • [10] On the State Complexity of Scattered Substrings and Superstrings
    Okhotin, Alexander
    FUNDAMENTA INFORMATICAE, 2010, 99 (03) : 325 - 338
12345