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

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., 2015, Volume 51, Issue 4, Pages 47–59 (Mi ppi2186)  

Large Systems

On regular realizability problems for context-free languages

M. N. Vyalyiabc, A. A. Rubtsovcb

a Dorodnitsyn Computing Center of the Russian Academy of Sciences, Moscow, Russia
b National Research University — Higher School of Economics, Moscow, Russia
c Moscow Institute of Physics and Technology (State University), Moscow, Russia

Abstract: We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both $\mathbf P$-complete and $\mathbf{NL}$-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.

Funding Agency Grant Number
Russian Foundation for Basic Research 12-01-00864
14-01-00641
Ministry of Education and Science of the Russian Federation НШ-4652.2012.1
Supported in part by the Russian Foundation for Basic Research, project no. 12-01-00864, and the President of the Russian Federation Council for State Support of Leading Scientific Schools, project no. NSh-4652.2012.1.
Supported in part by the Russian Foundation for Basic Research, project no. 14-01-00641.


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

English version:
Problems of Information Transmission, 2015, 51:4, 349–360

Bibliographic databases:

UDC: 621.391.1+519.7
Received: 09.09.2014
Revised: 13.05.2015

Citation: M. N. Vyalyi, A. A. Rubtsov, “On regular realizability problems for context-free languages”, Probl. Peredachi Inf., 51:4 (2015), 47–59; Problems Inform. Transmission, 51:4 (2015), 349–360

Citation in format AMSBIB
\Bibitem{VyaRub15}
\by M.~N.~Vyalyi, A.~A.~Rubtsov
\paper On regular realizability problems for context-free languages
\jour Probl. Peredachi Inf.
\yr 2015
\vol 51
\issue 4
\pages 47--59
\mathnet{http://mi.mathnet.ru/ppi2186}
\elib{http://elibrary.ru/item.asp?id=26851490}
\transl
\jour Problems Inform. Transmission
\yr 2015
\vol 51
\issue 4
\pages 349--360
\crossref{https://doi.org/10.1134/S0032946015040043}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000367604200004}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84952942225}


Linking options:
  • http://mi.mathnet.ru/eng/ppi2186
  • http://mi.mathnet.ru/eng/ppi/v51/i4/p47

    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
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:220
    Full text:17
    References:48
    First page:48

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