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 条
  • [41] State Complexity of Projection on Languages Recognized by Permutation Automata and Commuting Letters
    Hoffmann, Stefan
    DEVELOPMENTS IN LANGUAGE THEORY, DLT 2021, 2021, 12811 : 192 - 203
  • [42] The complexity of interacting automata
    Gossner, Olivier
    Hernandez, Penelope
    Peretz, Ron
    INTERNATIONAL JOURNAL OF GAME THEORY, 2016, 45 (1-2) : 461 - 496
  • [43] Energy Complexity of Computation
    Say, Ahmet Celal Cem
    REVERSIBLE COMPUTATION, RC 2023, 2023, 13960 : 3 - 11
  • [44] Complexity and effective prediction
    Neyman, Abraham
    Spencer, Joel
    GAMES AND ECONOMIC BEHAVIOR, 2010, 69 (01) : 165 - 168
  • [45] State Complexity of Union and Intersection for Two-Way Nondeterministic Finite Automata
    Kunc, Michal
    Okhotin, Alexander
    FUNDAMENTA INFORMATICAE, 2011, 110 (1-4) : 231 - 239
  • [46] State complexity of transforming graph-walking automata to halting, returning and reversible
    Martynova, Olga
    Okhotin, Alexander
    INFORMATION AND COMPUTATION, 2023, 291
  • [47] State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages
    Okhotin, Alexander
    Sazhneva, Elizaveta
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2019, 2019, 11612 : 248 - 259
  • [48] EVOLUTION AND THE COMPLEXITY OF FINITE AUTOMATA
    Kilani, Moez
    INTERNATIONAL GAME THEORY REVIEW, 2007, 9 (04) : 731 - 743
  • [49] Transition Complexity of Incomplete DFAs
    Gao, Yuan
    Salomaa, Kai
    Yu, Sheng
    FUNDAMENTA INFORMATICAE, 2011, 110 (1-4) : 143 - 158
  • [50] On Inverse Operations and Their Descriptional Complexity
    Bianchi, Maria Paola
    Holzer, Markus
    Jakobi, Sebastian
    Pighizzini, Giovanni
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2012, 2012, 7386 : 89 - 102
12345