RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Probl. Peredachi Inf.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Probl. Peredachi Inf., 2011, Volume 47, Issue 4, Pages 43–54 (Mi ppi2059)  

This article is cited in 2 scientific papers (total in 2 papers)

Large Systems

On regular realizability problems

M. N. Vyalyi

Dorodnitsyn Computing Centre of the Russian Academy of Sciences

Abstract: 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.

Full text: PDF file (170 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2011, 47:4, 342–352

Bibliographic databases:

UDC: 621.391.1+519.7
Received: 08.02.2011
Revised: 16.06.2011

Citation: M. N. Vyalyi, “On regular realizability problems”, Probl. Peredachi Inf., 47:4 (2011), 43–54; Problems Inform. Transmission, 47:4 (2011), 342–352

Citation in format AMSBIB
\Bibitem{Vya11}
\by M.~N.~Vyalyi
\paper On regular realizability problems
\jour Probl. Peredachi Inf.
\yr 2011
\vol 47
\issue 4
\pages 43--54
\mathnet{http://mi.mathnet.ru/ppi2059}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2933441}
\transl
\jour Problems Inform. Transmission
\yr 2011
\vol 47
\issue 4
\pages 342--352
\crossref{https://doi.org/10.1134/S003294601104003X}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000299373700003}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84856820549}


Linking options:
  • http://mi.mathnet.ru/eng/ppi2059
  • http://mi.mathnet.ru/eng/ppi/v47/i4/p43

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. M. N. Vyalyi, “On expressive power of regular realizability problems”, Problems Inform. Transmission, 49:3 (2013), 276–291  mathnet  crossref  isi  elib
    2. M. N. Vyalyi, A. A. Rubtsov, “On regular realizability problems for context-free languages”, Problems Inform. Transmission, 51:4 (2015), 349–360  mathnet  crossref  isi  elib
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:355
    Full text:62
    References:27
    First page:10

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020