Genom en minskning av Posts Korrespondensproblem ger vi ett direkt bevis på det kända faktum att integrationsproblemet för entydig kontextfri grammatik är oavgjort. Argumentet eller någon enkel ändring gäller också för vissa andra underklasser av sammanhangsfria språk såsom linjära språk, sekventiella språk och DSC-språk (dvs. språk som genereras av sammanhangsfri grammatik med olika syntaktiska kategorier). Vi tar också hänsyn till fall av problemet "Är L (D 1 ) L ( D 2 )?" där D 1 och D 2 hämtas från möjligtvis olika deskriptorfamiljer för underklasser av kontextfria språk. När vi ändrar ett sammanhangsfritt språk med t.ex. ändra sin grammatik G 1 till en ny sammanhangsfri grammatik G 2, de uppenbara frågorna är: Vad är förhållandet mellan L ( G 1 ) och L ( G 2 )? Är de jämlika? Är ett språk en (riktig) undergrupp av det andra? Är dessa två språk ojämförliga? När man besvarar frågor av denna typ spelar (avgörande för) integrationsproblemet en viktig roll. Betrakta två deskriptorer D 1 och D 2 av underklasser av kontextfria språk; t.ex., D 1 och D 2 är två särskilda typer av kontextfri grammatik eller push-down automata. Sedan inkluderar eller inneslutning problem för ( D 1, D 2 ) är frågan om för godtyckliga D 1  på D 1 och D 2 på D 2 inkluderar L ( D 1 )  på L ( D 2 ) innehar. I fallet D 1 = D 2 hänvisar vi till detta problem som integrationsproblem för D 1. Det är väl känt att integrationsproblemet för vanliga språk är avgörande, medan det är obeslutbart för kontextfria språk; jfr., t.ex., [4, 6, 8]. Under [2] har det fastställts att integrationsproblemet för enkla deterministiska språk är obeslutbart. Det är uppenbart att detta resultat innebär att integrationsproblemet är obeslutbart för otvetydiga sammanhangsfria språk.
Det har gjorts ett antal studier om integrationsproblem för underklasser av kontextfria språk (se REF för en undersökning).
The Inclusion Problem for Some Subclasses of Context-Free Languages
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}