@inproceedings{10.1007/978-3-642-02737-6_8,
    Abstract = {We study the problem of testing whether a context-free language is included in a fixed set L 0, where L 0 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).},
    Address = {Berlin, Heidelberg},
    Author = {Bertoni, Alberto and Choffrut, Christian and Radicioni, Roberto},
    BookTitle = {Developments in Language Theory},
    Editor = {Diekert, Volker and Nowotka, Dirk},
    File = {4d998887a18eb9309525ce85ccdfa96891d5 (0) - a - a - a.pdf},
    ISBN = {978-3-642-02737-6},
    Pages = {103--112},
    Publisher = {Springer Berlin Heidelberg},
    Title = {The Inclusion Problem of Context-Free Languages: Some Tractable Cases},
    Year = {2009},
    date-added = {2018-06-22 15:53:37 +0000},
    date-modified = {2018-06-22 15:53:37 +0000},
    doi = {10.1007/978-3-642-02737-6_8}
}

@inproceedings{10.1007/978-3-642-02737-6_8, Abstract = {We study the problem of testing whether a context-free language is included in a fixed set L 0, where L 0 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).}, Address = {Berlin, Heidelberg}, Author = {Bertoni, Alberto and Choffrut, Christian and Radicioni, Roberto}, BookTitle = {Developments in Language Theory}, Editor = {Diekert, Volker and Nowotka, Dirk}, File = {4d998887a18eb9309525ce85ccdfa96891d5 (0) - a - a - a.pdf}, ISBN = {978-3-642-02737-6}, Pages = {103--112}, Publisher = {Springer Berlin Heidelberg}, Title = {The Inclusion Problem of Context-Free Languages: Some Tractable Cases}, Year = {2009}, date-added = {2018-06-22 15:53:37 +0000}, date-modified = {2018-06-22 15:53:37 +0000}, doi = {10.1007/978-3-642-02737-6_8} }