On regular realizability problems

被引：0
作者：
M. N. Vyalyi
机构：
[1] Computing Center of the Russian Academy of Sciences,
来源：
Problems of Information Transmission | 2011年 / 47卷
关键词：
Information Transmission; Turing Machine; Cayley Graph; Regular Language; Satisfying Assignment;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We consider the class of regular realizability problems. Any of such problems is specified by some language (filter) and consists in verifying that the intersection of a given regular language and the filter is nonempty. The main question is diversity of the computational complexity of such problems. We show that any regular realizability problem with an infinite filter is hard for a class of problems decidable in logarithmic space with respect to logarithmic reductions. We give examples of NP-complete and PSPACE-complete regular realizability problems.
引用
收藏
页码：342 / 352
页数：10
相关论文
共 50 条
  • [21] PS-regular languages
    Wang, Shou-Feng
    Guo, Yu-Qi
    Xu, Shao-Xian
    [J]. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2011, 88 (12) : 2464 - 2484
  • [22] Regular Component Splittable Languages
    H. J. Shyr
    S. S. Yu
    [J]. Acta Mathematica Hungarica, 1998, 78 : 251 - 265
  • [23] Operads, quasiorders, and regular languages
    Giraudo, Samuele
    Luque, Jean-Gabriel
    Mignot, Ludovic
    Nicart, Florent
    [J]. ADVANCES IN APPLIED MATHEMATICS, 2016, 75 : 56 - 93
  • [24] Geometricity of Binary Regular Languages
    Champarnaud, Jean-Marc
    Dubernard, Jean-Philippe
    Jeanne, Hadrien
    [J]. LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, 2010, 6031 : 178 - 189
  • [25] A characterization of local regular languages
    Yu, SS
    [J]. DISCRETE MATHEMATICS, 1998, 184 (1-3) : 195 - 203
  • [26] On Generalized Strongly Regular Graphs
    Dongdong Jia
    Landang Yuan
    Gengsheng Zhang
    [J]. Graphs and Combinatorics, 2018, 34 : 555 - 570
  • [27] Regular sets in Cayley graphs
    Yanpeng Wang
    Binzhou Xia
    Sanming Zhou
    [J]. Journal of Algebraic Combinatorics, 2023, 57 : 547 - 558
  • [28] The dissecting power of regular languages
    Yamakami, Tomoyuki
    Kato, Yuichi
    [J]. INFORMATION PROCESSING LETTERS, 2013, 113 (04) : 116 - 122
  • [29] Syntactic Complexity of Regular Ideals
    Janusz A. Brzozowski
    Marek Szykuła
    Yuli Ye
    [J]. Theory of Computing Systems, 2018, 62 : 1175 - 1202
  • [30] Shuffle decomposition of regular languages
    Ito, M
    [J]. JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 2002, 8 (02): : 257 - 259
12345