|
Проблемы передачи информации, 2011, том 47, выпуск 4, страницы 43–54
(Mi ppi2059)
|
|
|
|
Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)
Большие системы
О задачах регулярной реализуемости
М. Н. Вялый Вычислительный центр РАН
Аннотация:
Рассматривается класс задач регулярной реализуемости. Каждая такая задача определяется некоторым языком (фильтром) и состоит в проверке непустоты пересечения заданного регулярного языка с фильтром. Основной вопрос – насколько разнообразна вычислительная сложность таких задач. Показано, что всякая задача регулярной реализуемости с бесконечным фильтром трудна для класса задач, разрешимых на логарифмической памяти относительно логарифмических сводимостей. Приведены примеры NP-полных и PSPACE-полных задач регулярной реализуемости.
Поступила в редакцию: 08.02.2011 После переработки: 16.06.2011
Образец цитирования:
М. Н. Вялый, “О задачах регулярной реализуемости”, Пробл. передачи информ., 47:4 (2011), 43–54; Problems Inform. Transmission, 47:4 (2011), 342–352
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi2059 https://www.mathnet.ru/rus/ppi/v47/i4/p43
|
Статистика просмотров: |
Страница аннотации: | 478 | PDF полного текста: | 92 | Список литературы: | 38 | Первая страница: | 10 |
|