𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Polynomial Size Test Sets For Context-Free Languages

✍ Scribed by J. Karhumaki; W. Plandowski; W. Rytter

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
648 KB
Volume
50
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that each context-free language possesses a test set of size (O\left(m^{6}\right)), where (m) is the number of productions in a grammar-producing the language. A context-free grammar generating the test set can be found in polynomial time by a sequential algorithm. It improves the doubly exponential upper bound from [2] and single exponential one from J. KarhumΓ€ki, W. Rytter, and S. Jarominek (Theoret. Comput. Sci. (116(1993), 305-316)). On the other hand, we show that the lower bound for the problem is (\Omega\left(\mathrm{m}^{3}\right)) and that the lower bound for the size of a test set for a language defined over (n)-letter alphabet is (\Omega\left(n^{3}\right)). c. 1995 Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

The Set of Minimal Words of a Context-fr
The Set of Minimal Words of a Context-free Language is Context-free
✍ Jean Berstel; L. Boasson πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 360 KB

Let A be a finite, totally ordered alphabet, and let P be the lexicographic ordering on A\*. Let X be a subset of A\*. The language of minimal words of X is the subset of X composed of the lexicographically minimal word of X for each length: The aim of this paper is to prove that if L is a context-