• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Regular Realizability Problems and Context- Free Languages

P. 256-267.

We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse measure of context-free languages com- plexity. This characteristic is compatible with rational dominance. We present examples of P-complete RR problems as well as examples of RR problems in the class NL. Also we discuss RR problems with context- free filters that might have intermediate complexity. Possible candidates are the languages with polynomially bounded rational indices. 

In book

Vol. 9118. Switzerland: Springer, 2015.