THE INCLUSION PROBLEM OF CONTEXT-FREE LANGUAGES: SOME TRACTABLE CASES
Alberto Bertoni, Christian Choffrut, Roberto Radicioni · International Journal of Foundations of Computer Science · 2011
We study the problem of testing whether a context-free language is included in a fixed set L0, where L0 is the language of words reducing to the empty word in the monoid defined by a complete string rewrite system. We prove that, if the monoid is cancellative, then our inclusion problem is polynomially reducible to the problem of testing equivalence of straight-line programs in the same monoid. As an application, we obtain a polynomial time algorithm for testing if a context-free language is included in a Dyck language (the best previous algorithm for this problem was doubly exponential).