Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Reducing Simple Grammars: Exponential Against Highly-Polynomial Time in Practice

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 4094))

  • 436Accesses

Abstract

The simple grammar reduction is an important component in the implementation of Concatenation State Machines (a hardware version of stateless pushdown automata designed for wire-speed network packet classification). We present a comparison and experimental analysis of the best-known algorithms for the grammar reduction. There are two classes of algorithms: the ones that process compressed strings without decompression (polynomial time) and the ones which process strings explicitely. The second category, though exponential time in pessimistic case, is more efficient in the considered practical scenario. There are two approaches to this problem: one processing compressed strings without decompression and another one which processes strings explicitely. 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.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bastien, C., Czyzowicz, J., Fraczak, W., Rytter, W.: Prime normal form and equivalence of simple grammars. In: Farré, J., Litovsky, I., Schmitz, S. (eds.) CIAA 2005. LNCS, vol. 3845, pp. 78–89. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  2. Bastien, C., Czyzowicz, J., Fraczak, W., Rytter, W.: Equivalence of Functions Represented by Simple Context-Free Grammars with Output. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 71–82. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  3. Caucal, D.: A fast algorithm to decide on simple grammars equivalence. In: Djidjev, H.N. (ed.) Optimal Algorithms. LNCS, vol. 401, pp. 66–85. Springer, Heidelberg (1989)

    Google Scholar 

  4. Debski, W., Fraczak, W.: Concatenation state machines and simple functions. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 113–124. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  5. Harrison, M.A.: Introduction to formal language theory. Addison Wesley, Reading (1978)

    MATH  Google Scholar 

  6. Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theoretical Computer Science 158(1-2), 143–159 (1996)

    Article MATH MathSciNet  Google Scholar 

  7. Korenjak, A.J., Hopcroft, J.E.: Simple deterministic languages. In: Proc. IEEE 7th Annual Symposium on Switching and Automata Theory, IEEE Symposium on Foundations of Computer Science, pp. 36–46 (1966)

    Google Scholar 

  8. Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching for strings in terms of straight-line programs. Journal of Discrete Algorithms 1(1), 187–204 (2000)

    MathSciNet  Google Scholar 

  9. Rytter, W.: Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 15–27. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dépt d’informatique, Université du Québec en Outaouais, Gatineau, PQ, Canada

    Cédric Bastien, Jurek Czyzowicz & Wojciech Fraczak

  2. IDT Canada Inc., Ottawa, ON, Canada

    Wojciech Fraczak

  3. Inst. of Informatics, Warsaw University, Warsaw, Poland

    Wojciech Rytter

Authors
  1. Cédric Bastien

    You can also search for this author inPubMed Google Scholar

  2. Jurek Czyzowicz

    You can also search for this author inPubMed Google Scholar

  3. Wojciech Fraczak

    You can also search for this author inPubMed Google Scholar

  4. Wojciech Rytter

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of California, Santa Barbara

    Oscar H. Ibarra

  2. Dept. of Computer Science, Kainan University, Taoyuan, Taiwan, R.O.C.

    Hsu-Chun Yen

Rights and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bastien, C., Czyzowicz, J., Fraczak, W., Rytter, W. (2006). Reducing Simple Grammars: Exponential Against Highly-Polynomial Time in Practice. In: Ibarra, O.H., Yen, HC. (eds) Implementation and Application of Automata. CIAA 2006. Lecture Notes in Computer Science, vol 4094. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11812128_10

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp