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 条
  • [31] State Complexity of Unary Language Operations for NFAs with Limited Nondeterminism
    Palioudakis, Alexandros
    Salomaa, Kai
    Akl, Selim G.
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2014, 2014, 8614 : 330 - 341
  • [32] State complexity of union and intersection of star on k regular languages
    Gao, Yuan
    Kari, Lila
    Yu, Sheng
    THEORETICAL COMPUTER SCIENCE, 2012, 429 : 98 - 107
  • [33] State Complexity of Star and Square of Union of k Regular Languages
    Gao, Yuan
    Kari, Lila
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2012, 2012, 7386 : 155 - 168
  • [34] State Complexity of Combined Operations with Union, Intersection, Star and Reversal
    Gao, Yuan
    Yu, Sheng
    FUNDAMENTA INFORMATICAE, 2012, 116 (1-4) : 79 - 92
  • [35] State complexity of permutation on finite languages over a binary alphabet
    Cho, Da-Jung
    Goc, Daniel
    Han, Yo-Sub
    Ko, Sang-Ki
    Palioudakis, Alexandros
    Salomaa, Kai
    THEORETICAL COMPUTER SCIENCE, 2017, 682 : 67 - 78
  • [36] On the complexity of coordination
    Gossner, O
    Hernández, P
    MATHEMATICS OF OPERATIONS RESEARCH, 2003, 28 (01) : 127 - 140
  • [37] State complexity of union and intersection of square and reversal on k regular languages
    Gao, Yuan
    Kari, Lila
    Yu, Sheng
    THEORETICAL COMPUTER SCIENCE, 2012, 454 : 164 - 171
  • [38] State Complexity of Permutation and Related Decision Problems on Alphabetical Pattern Constraints
    Hoffmann, Stefan
    IMPLEMENTATION AND APPLICATION OF AUTOMATA (CIAA 2021), 2021, 12803 : 115 - 126
  • [39] State complexity of star of union and square of union on k regular languages
    Gao, Yuan
    Kari, Lila
    THEORETICAL COMPUTER SCIENCE, 2013, 499 : 38 - 50
  • [40] State Complexity of Basic Operations on Non-Returning Regular Languages
    Eom, Hae-Sung
    Han, Yo-Sub
    Jiraskova, Galina
    FUNDAMENTA INFORMATICAE, 2016, 144 (02) : 161 - 182
12345