|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
О задачах регулярной реализуемости для контекстно-свободных языковстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
- Авторы: Вялый Михаил Николаевич, Рубцов Александр Александрович
- Журнал: Проблемы передачи информации
- Том: 51
- Номер: 4
- Год издания: 2015
- Первая страница: 47
- Последняя страница: 59
- Аннотация: Рассматриваются задачи регулярной реализуемости, которые состоят в проверке непустоты пересечения регулярного языка на входе задачи и фиксированного языка (фильтра), который является параметром задачи. Изучается алгоритмическая сложность задач регулярной реализуемости для контекстно-свободных фильтров. Эта характеристика согласована с отношением рационального доминирования на КС-языках. Однако, как доказывается, она более грубая. Также приводятся примеры как P-полных, так и NL-полных задач регулярной реализуемости для КС-фильтров. Кроме того, приведен пример подкласса КС-языков, для фильтров из которого задачи регулярной реализуемости могут иметь промежуточную сложность. Это языки с полиномиально ограниченным рациональным индексом.
- Добавил в систему: Золин Евгений Евгеньевич