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 条
  • [21] Operational state complexity of nested word automata
    Piao, Xiaoxue
    Salomaa, Kai
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (35) : 3290 - 3302
  • [22] On the State Complexity of Star of Union and Star of Intersection
    Jiraskova, Galina
    Okhotin, Alexander
    FUNDAMENTA INFORMATICAE, 2011, 109 (02) : 161 - 178
  • [23] Time-Space Complexity Advantages for Quantum Computing
    Zheng, Shenggen
    Qiu, Daowen
    Gruska, Jozef
    THEORY AND PRACTICE OF NATURAL COMPUTING, TPNC 2017, 2017, 10687 : 305 - 317
  • [24] Complexity Bounds of Constant-Space Quantum Computation
    Yamakami, Tomoyuki
    DEVELOPMENTS IN LANGUAGE THEORY (DLT 2015), 2015, 9168 : 426 - 438
  • [25] Nondeterministic state complexity of star-free languages
    Holzer, Markus
    Kutrib, Martin
    Meckel, Katja
    THEORETICAL COMPUTER SCIENCE, 2012, 450 : 68 - 80
  • [26] Operational state complexity of unary NFAs with finite nondeterminism
    Palioudakis, Alexandros
    Salomaa, Kai
    Akl, Selim G.
    THEORETICAL COMPUTER SCIENCE, 2016, 610 : 108 - 120
  • [27] On a structural property in the state complexity of projected regular languages
    Jiraskova, Galina
    Masopust, Tomas
    THEORETICAL COMPUTER SCIENCE, 2012, 449 : 93 - 105
  • [28] Nondeterministic State Complexity of Star-Free Languages
    Holzer, Markus
    Kutrib, Martin
    Meckel, Katja
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, 2011, 6807 : 178 - 189
  • [29] State complexity of combined operations with two basic operations
    Cui, Bo
    Gao, Yuan
    Kari, Lila
    Yu, Sheng
    THEORETICAL COMPUTER SCIENCE, 2012, 437 : 82 - 102
  • [30] Combination of roots and boolean operations: An application to state complexity
    Caron, Pascal
    Hamel-de le Court, Edwin
    Luque, Jean-Gabriel
    INFORMATION AND COMPUTATION, 2022, 289
12345