Context-free complexity of finite languages

W Bucher, HA Maurer, K Culik II - Theoretical computer science, 1983 - Elsevier
W Bucher, HA Maurer, K Culik II
Theoretical computer science, 1983Elsevier
In this paper the investigation of the theory of grammatical complexity as started by Bucher
(1981) and Bucher, Culik II, Maurer and Wotschke (1981) is continued. The basic question
we are concerned with is the following: Given some finite language L, what is the smallest
number of context-free productions needed to generate L, the so-called (context-free)
complexity of L. We strengthen some of the results given by Bucher et al.(1981), the main
result being a necessary condition for certain sequences of finite languages to be of …
Abstract
In this paper the investigation of the theory of grammatical complexity as started by Bucher (1981) and Bucher, Culik II, Maurer and Wotschke (1981) is continued. The basic question we are concerned with is the following: Given some finite language L, what is the smallest number of context-free productions needed to generate L, the so-called (context-free) complexity of L. We strengthen some of the results given by Bucher et al. (1981), the main result being a necessary condition for certain sequences of finite languages to be of sublinear complexity.
Elsevier