The Inclusion Problem for Some Subclasses of Context-Free Languages

P.R.J. Asveld, Antinus Nijholt

    Research output: Contribution to journalArticleAcademicpeer-review

    10 Citations (Scopus)
    3 Downloads (Pure)


    By a reduction to Post's Correspondence Problem we provide a direct proof of the known fact that the inclusion problem for unambiguous context-free grammars is undecidable. The argument or some straightforward modification also applies to some other subclasses of context-free languages such as linear languages, sequential languages, and DSC-languages (i.e., languages generated by context-free grammars with disjunct syntactic categories). We also consider instances of the problem ``Is $L(D_1 )\subseteq L(D_2 )^$ ?'' where $D_1$ and $D_2$ are taken from possibly different descriptor families of subclasses of context-free languages.
    Original languageUndefined
    Pages (from-to)247-256
    Number of pages10
    JournalTheoretical computer science
    Issue number1-2
    Publication statusPublished - 2000


    • EWI-6617
    • METIS-118711
    • IR-63348
    • HMI-SLT: Speech and Language Technology

    Cite this