𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The inclusion problem for some subclasses of context-free languages

✍ Scribed by Peter R.J. Asveld; Anton Nijholt

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
131 KB
Volume
230
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 modiΓΏcation 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) βŠ† L(D2)?" where D1 and D2 are taken from possibly di erent descriptor families of subclasses of context-free languages.

πŸ“œ SIMILAR VOLUMES

Almost optimal sublinear time parallel r
Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages
✍ Lawrence L. Larmore; Wojciech Rytter πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 803 KB

Sublinear time almost optimal algorithms for the recognition problem for three basic subclasses of context-free languages (unambiguous, deterministic and linear) are presented. Optimality is measured with respect to the work of the best-known sequential algorithm for a given problem.