Abstract:
We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.
Supported in part by the Russian Foundation for Basic Research, project no. 12-01-00864, and the President of the Russian Federation Council for State Support of Leading Scientific Schools, project no. NSh-4652.2012.1.
Supported in part by the Russian Foundation for Basic Research, project no. 14-01-00641.