О задачах регулярной реализуемости

Рассматривается класс задач регулярной реализуемости. Каждая такая задача определяется некоторым языком (фильтром) и состоит в проверке непустоты пересечения заданного регулярного языка с фильтром. Основной вопрос – насколько разнообразна вычислительная сложность таких задач. Показано, что всякая задача регулярной реализуемости с бесконечным фильтром трудна для класса задач, разрешимых на логарифмической памяти относительно логарифмических сводимостей. Приведены примеры NP-полных и PSPACE-полных задач регулярной реализуемости.