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 条
  • [1] On regular realizability problems
    Vyalyi, M. N.
    PROBLEMS OF INFORMATION TRANSMISSION, 2011, 47 (04) : 342 - 352
  • [2] On expressive power of regular realizability problems
    M. N. Vyalyi
    Problems of Information Transmission, 2013, 49 : 276 - 291
  • [3] On regular realizability problems for context-free languages
    M. N. Vyalyi
    A. A. Rubtsov
    Problems of Information Transmission, 2015, 51 : 349 - 360
  • [4] Regular component decomposition of regular languages
    Liu, YJ
    THEORETICAL COMPUTER SCIENCE, 2003, 299 (1-3) : 743 - 749
  • [5] On G-arc-regular dihedrants and regular dihedral maps
    Kovacs, Istvan
    Marusic, Dragan
    Muzychuk, Mikhail
    JOURNAL OF ALGEBRAIC COMBINATORICS, 2013, 38 (02) : 437 - 455
  • [6] On G-arc-regular dihedrants and regular dihedral maps
    István Kovács
    Dragan Marušič
    Mikhail Muzychuk
    Journal of Algebraic Combinatorics, 2013, 38 : 437 - 455
  • [7] On a generalization of regular expression
    A. L. Gomozov
    L. I. Stanevichene
    Programming and Computer Software, 2000, 26 : 258 - 267
  • [8] Undecidability in ω-regular languages
    Halava, Vesa
    Harju, Tero
    Karhumäki, Juhani
    FUNDAMENTA INFORMATICAE, 2006, 73 (1-2) : 119 - 125
  • [9] On the entropy of regular languages
    Ceccherini-Silberstein, T
    Machi, A
    Scarabotti, F
    THEORETICAL COMPUTER SCIENCE, 2003, 307 (01) : 93 - 102
  • [10] On a generalization of regular expressions
    Gomozov, AL
    Stanevichene, LI
    PROGRAMMING AND COMPUTER SOFTWARE, 2000, 26 (05) : 258 - 267
12345