Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2007 | CIAA | positive weight,throughput value,weight function,smallest mean weight,guaranteed throughput,input grammar g,finite language,context-free language,grammar g,efficient computation,mean weight,context free grammar,context free language,system performance,throughput |
Field | DocType | Volume |
Context-free language,Combinatorics,Weight function,Context-free grammar,Computer science,Network packet,Grammar,Throughput,Time complexity,Real number | Conference | 4783 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-76335-X | 3 |
PageRank | References | Authors |
0.45 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Didier Caucal | 1 | 470 | 39.15 |
| Jurek Czyzowicz | 2 | 778 | 74.35 |
| Wojciech Fraczak | 3 | 104 | 11.66 |
| Wojciech Rytter | 4 | 2290 | 181.52 |