Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

The Inclusion Problem for Some Subclasses of Context-Free Languages

Share/Save/Bookmark

Asveld, Peter R.J. and Nijholt, Anton (1997) The Inclusion Problem for Some Subclasses of Context-Free Languages. [Report]

[img]
Preview
PDF
47Kb
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.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/64305
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 118509