Efficient Computation of Throughput Values of Context-Free Languages

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620156
Contributor : Didier Caucal <>
Submitted on : Monday, September 30, 2013 - 7:24:42 PM
Last modification on : Friday, July 13, 2018 - 4:00:04 PM
Long-term archiving on : Tuesday, December 31, 2013 - 2:30:26 AM

File

throughput.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Didier Caucal, Jurek Czyzowicz, Wojciech Fraczak, Wojciech Rytter. Efficient Computation of Throughput Values of Context-Free Languages. 12th International Conference on Implementation and Application of Automata (CIAA'07), Jul 2007, Prague, Czech Republic. pp.203-213, ⟨10.1007/978-3-540-76336-9_20⟩. ⟨hal-00620156⟩

Share

Metrics

Record views

188

Files downloads

239