Polynomial size test sets for context-free languages. (English) Zbl 0834.68065

Karhumäki, Juhani; Plandowski, Wojciech; Rytter, Wojciech

J. Comput. Syst. Sci. 50, No. 1, 11-19 (1995).

Summary: We prove that each context-free language possesses a test set of size \(O (m^6)\), 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 [J. Albert, K. Culik II and J. Karhumaeki, Inf. Control 52, 172-186 (1982; Zbl 0522.68064)] and single exponential one from J. Karhumäki, W. Rytter and S. Jarominek [Theor. Comput. Sci. 116, 305-316 (1993; Zbl 0793.68090)]. On the other hand, we show that the lower bound for the problem is \(Q (m^3)\) and that the lower bound for the size of a test set for a language defined over \(n\)-letter alphabet is \(\Omega (n^3)\).

MSC:

68Q45

Formal languages and automata

Citations:

Zbl 0522.68064; Zbl 0793.68090