Special Issue: Implementation and Application of Automata: Contributed PapersNo Access

REDUCING SIMPLE GRAMMARS: EXPONENTIAL AGAINST HIGHLY-POLYNOMIAL TIME IN PRACTICE

CÉDRIC BASTIEN

Dépt d'informatique, Université du Québec en Outaouais, Gatineau PQ, Canada

Search for more papers by this author

JUREK CZYZOWICZ

Dépt d'informatique, Université du Québec en Outaouais, Gatineau PQ, Canada

Search for more papers by this author

WOJCIECH FRACZAK

IDT Canada Inc., Ottawa ON, Canada

Dépt d'informatique, Université du Québec en Outaouais, Gatineau PQ, Canada

Search for more papers by this author

, and

WOJCIECH RYTTER

Instytut Informatyki, Universytet Warszawski, Warsaw, Poland

Department of Mathematics and Informatics, Copernicus University, Torun, Poland

Search for more papers by this author

https://doi.org/10.1142/S0129054107004930Cited by:0 (Source: Crossref)

Abstract

Simple grammar reduction is an important component in the implementation of Concatenation State Machines (a hardware version of stateless push-down automata designed for wire-speed network packet classification). We present a comparison and experimental analysis of the best-known algorithms for grammar reduction. There are two approaches to this problem: one processing compressed strings without decompression and another one which processes strings explicitly. It turns out that the second approach is more efficient in the considered practical scenario despite having worst-case exponential time complexity (while the first one is polynomial). The study has been conducted in the context of network packet classification, where simple grammars are used for representing the classification policies.

References

Cédric Bastienet al., Prime normal form and equivalence of simple grammars, CIAA 2005, LNCS 3845, eds. I. Litovsky, J. Farré and S. Schmitz (Springer, 2006) pp. 78–89. Google Scholar
Cédric Bastienet al., Equivalence of Functions Represented by Simple Context-Free Grammars with Output, Developments in Language Theory, DLT 2006, LNCS 4036 (Springer, 2006) pp. 71–82. Google Scholar
Didier Caucal, Optimal Algorithms, LNCS 401 (Springer, 1989) pp. 66–85. Crossref, Google Scholar
Wojciech Debski and Wojciech Fraczak, Concatenation state machines and simple functions, Implementation and Application of Automata, CIAA 2004, LNCS 3317 (Springer, 2004) pp. 113–124. Google Scholar
M. A. Harrison , Introduction to formal language theory ( Addison Wesley , 1978 ) . Google Scholar
Yoram Hirshfeld, Mark Jerrum and Faron Moller, Theoretical Computer Science 158(1–2), 143 (1996), DOI: 10.1016/0304-3975(95)00064-X. Crossref, Web of Science, Google Scholar
A. J. Korenjak and J. E. Hopcroft. Simple deterministic languages. In Proc. IEEE 7th Annual Symposium on Switching and Automata Theory, IEEE Symposium on Foundations of Computer Science, pages 36–46, 1966 . Google Scholar
Masamichi Miyazaki, Ayumi Shinohara and Masayuki Takeda, Journal of Discrete Algorithms 1(1), 187 (2000). Google Scholar
Wojciech Rytter, Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input, ICALP 2004, LNCS 3142 (Springer, 2004) pp. 15–27. Google Scholar