๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Context-free complexity of finite languages

โœ Scribed by W. Bucher; H.A. Maurer; K. Culik II

Book ID
107948495
Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
1003 KB
Volume
28
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On the context-free production complexit
On the context-free production complexity of finite languages
โœ Zsolt Tuza ๐Ÿ“‚ Article ๐Ÿ“… 1987 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 696 KB

The following problem is investigated. Let L be a given finite language, LcL,= {ub: I ~o,bsn, of/~}. Determine the minimal natural number c(L) such that L can be generated by c(L) context-free productions. Among others, max c(L) = O(n'/log n) is proved, and languages satisfying c(L) = IL) are charac