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

Рассматриваются задачи регулярной реализуемости, которые состоят в проверке непустоты пересечения регулярного языка на входе задачи и фиксированного языка (фильтра), который является параметром задачи. Изучается алгоритмическая сложность задач регулярной реализуемости для контекстно-свободных фильтров. Эта характеристика согласована с отношением рационального доминирования на КС-языках. Однако, как доказывается, она более грубая. Также приводятся примеры как $\mathbf P$-полных, так и $\mathbf{NL}$-полных задач регулярной реализуемости для КС-фильтров. Кроме того, приведен пример подкласса КС-языков, для фильтров из которого задачи регулярной реализуемости могут иметь промежуточную сложность. Это языки с полиномиально ограниченным рациональным индексом.