We give the first deterministic polynomial time algorithm that computes the
throughput value of a given context-free language
L. The language is given by a grammar
G of size
n, together with a weight function assigning a positive weight to each symbol. The
weight of a word
w ∈
L is defined as the sum of weights of its symbols (with multiplicities), and the
mean weight is the weight of
w divided by length of
w. The
throughput of
L, denoted by
throughput(L), is the smallest real number
t, such that the mean value of each word of
L is not smaller than
t. Our approach, to compute
throughput(L), consists of two phases. In the first one we convert the input grammar
G to a grammar
G′, generating a finite language
L′, such that
throughput(L)=
throughput(L’). In the next phase we find a word of the smallest mean weight in a finite language
L′. The size of
G′ is polynomially related to the size of
G.
The problem is of practical importance in system-performance analysis, especially in the domain of network packet processing,
where one of the important parameters is the “guaranteed throughput” of a system for on-line network packet processing.
Keywords context-free grammar - push-down automaton - throughput - minimal mean weight