Loading [MathJax]/jax/output/SVG/config.js
Проблемы передачи информации
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Проблемы передачи информации, 2015, том 51, выпуск 4, страницы 47–59 (Mi ppi2186)  
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)

Большие системы

О задачах регулярной реализуемости для контекстно-свободных языков

М. Н. Вялыйabc, А. А. Рубцовcb

a Вычислительный центр им. А. А. Дородницына РАН
b Национальный исследовательский университет "Высшая школа экономики"
c Московский физико-технический институт (государственный университет)
PDF полного текста (230 kB) Список цитирования (6)
Список литературы:
PDF
HTML
Аннотация: Рассматриваются задачи регулярной реализуемости, которые состоят в проверке непустоты пересечения регулярного языка на входе задачи и фиксированного языка (фильтра), который является параметром задачи. Изучается алгоритмическая сложность задач регулярной реализуемости для контекстно-свободных фильтров. Эта характеристика согласована с отношением рационального доминирования на КС-языках. Однако, как доказывается, она более грубая. Также приводятся примеры как $\mathbf P$-полных, так и $\mathbf{NL}$-полных задач регулярной реализуемости для КС-фильтров. Кроме того, приведен пример подкласса КС-языков, для фильтров из которого задачи регулярной реализуемости могут иметь промежуточную сложность. Это языки с полиномиально ограниченным рациональным индексом.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 12-01-00864
14-01-00641
Министерство образования и науки Российской Федерации НШ-4652.2012.1
Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (номер проекта 12-01-00864) и Совета по поддержке научных школ при Президенте РФ (номер проекта НШ-4652.2012.1).
Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (номер проекта 14-01-00641).
Поступила в редакцию: 09.09.2014
После переработки: 13.05.2015
Англоязычная версия:
Problems of Information Transmission, 2015, Volume 51, Issue 4, Pages 349–360
DOI: https://doi.org/10.1134/S0032946015040043
Реферативные базы данных:
Тип публикации: Статья
УДК: 621.391.1+519.7
Образец цитирования: М. Н. Вялый, А. А. Рубцов, “О задачах регулярной реализуемости для контекстно-свободных языков”, Пробл. передачи информ., 51:4 (2015), 47–59; Problems Inform. Transmission, 51:4 (2015), 349–360
Цитирование в формате AMSBIB
\RBibitem{VyaRub15}
\by М.~Н.~Вялый, А.~А.~Рубцов
\paper О задачах регулярной реализуемости для контекстно-свободных языков
\jour Пробл. передачи информ.
\yr 2015
\vol 51
\issue 4
\pages 47--59
\mathnet{http://mi.mathnet.ru/ppi2186}
\elib{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000367604200004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84952942225}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ppi2186
  • https://www.mathnet.ru/rus/ppi/v51/i4/p47
    • Эта публикация цитируется в следующих 6 статьяx:
    1. Wolf P., “From Decidability to Undecidability By Considering Regular Sets of Instances”, Theor. Comput. Sci., 899 (2022), 25–38  crossref  mathscinet  zmath  isi  scopus
    2. Volker Diekert, Henning Fernau, Petra Wolf, “Properties of graphs specified by a regular language”, Acta Informatica, 59:4 (2022), 357  crossref
    3. Petra Wolf, “On the decidability of finding a positive ILP-instance in a regular set of ILP-instances”, Acta Informatica, 59:4 (2022), 505  crossref
    4. Dmitry Chistikov, Rupak Majumdar, Philipp Schepper, “Subcubic certificates for CFL reachability”, Proc. ACM Program. Lang., 6:POPL (2022), 1  crossref
    5. Volker Diekert, Henning Fernau, Petra Wolf, Lecture Notes in Computer Science, 12811, Developments in Language Theory, 2021, 117  crossref
    6. Petra Wolf, Lecture Notes in Computer Science, 11612, Descriptional Complexity of Formal Systems, 2019, 272  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Проблемы передачи информации Problems of Information Transmission
    Статистика просмотров:
    Страница аннотации:405
    PDF полного текста:92
    Список литературы:84
    Первая страница:48
     
      Обратная связь:
    math-net2025_04@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025