The Inclusion Problem for Some Subclasses of Context-Free Languages

P.R.J. Asveld; Antinus Nijholt

The Inclusion Problem for Some Subclasses of Context-Free Languages

Research output: Book/Report › Report › Academic

138 Downloads (Pure)

Abstract

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 language	Undefined
Publisher	Centre for Telematics and Information Technology (CTIT)
Number of pages	7
Publication status	Published - 1997

Publication series

Name	CTIT Technical Report Series
No.	97-31
ISSN (Print)	1381-3625

Keywords

EWI-10932
METIS-118509
IR-64305
HMI-SLT: Speech and Language Technology

Access to Document

1997ctit31.trFinal published version, 48 KB

Cite this

@book{2d1d97e0cc324d68814656935109d202,

title = "The Inclusion Problem for Some Subclasses of Context-Free Languages",

abstract = "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.",

keywords = "EWI-10932, METIS-118509, IR-64305, HMI-SLT: Speech and Language Technology",

author = "P.R.J. Asveld and Antinus Nijholt",

note = "Imported from HMI",

year = "1997",

language = "Undefined",

series = "CTIT Technical Report Series",

publisher = "Centre for Telematics and Information Technology (CTIT)",

number = "97-31",

address = "Netherlands",

}

TY - BOOK

T1 - The Inclusion Problem for Some Subclasses of Context-Free Languages

AU - Asveld, P.R.J.

AU - Nijholt, Antinus

N1 - Imported from HMI

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

KW - EWI-10932

KW - METIS-118509

KW - IR-64305

KW - HMI-SLT: Speech and Language Technology

M3 - Report

T3 - CTIT Technical Report Series

BT - The Inclusion Problem for Some Subclasses of Context-Free Languages

PB - Centre for Telematics and Information Technology (CTIT)

ER -