iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-540-27812-2_11
On NFA Reductions | SpringerLink
Skip to main content
Springer Nature Link
Log in

On NFA Reductions

  • Chapter
Theory Is Forever

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 3113))

Abstract

We give faster algorithms for two methods of reducing the number of states in nondeterministic finite automata. The first uses equivalences and the second uses preorders. We develop restricted reduction algorithms that operate on position automata while preserving some of its properties. We show empirically that these reductions are effective in largely reducing the memory requirements of regular expression search algorithms, and compare the effectiveness of different reductions.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Brüggemann-Klein, A.: Regular expressions into finite automata. Theoret. Comput. Sci. 120, 197–213 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  2. Champarnaud, J.-M., Coulon, F.: NFA reduction algorithms by means of regular inequalities. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 194–205. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  3. Glushkov, V.M.: The abstract theory of automata. Russian Math. Surveys 16, 1–53 (1961)

    Article  Google Scholar 

  4. Hagenah, C., Muscholl, A.: Computing ε -free NFA from regular expressions in O(n log 2(n)) time. Theor. Inform. Appl. 34(4), 257–277 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  5. Hopcroft, J.: An n log n algorithm for minimizing states in a finite automaton. In: Proc. Internat. Sympos. Theory of machines and computations, Technion, Haifa, pp. 189–196. Academic Press, New York (1971)

    Google Scholar 

  6. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)

    MATH  Google Scholar 

  7. Hromkovic, J., Seibert, S., Wilke, T.: Translating regular expressions into small ε-free nondeterministic finite automata. J. Comput. System Sci. 62(4), 565–588 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  8. Ilie, L., Yu, S.: Algorithms for computing small nFAs. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 328–340. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  9. Ilie, L., Yu, S.: Reducing NFAs by invariant equivalences. Theoret. Comput. Sci. 306, 373–390 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  10. Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput. 22(6), 1117–1141 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  11. Kameda, T., Weiner, P.: On the state minimization of nondeterministic finite automata. IEEE Trans. Computers C-19(7), 617–627 (1970)

    Article  MathSciNet  Google Scholar 

  12. McNaughton, R., Yamada, H.: Regular expressions and state graphs for automata. IEEE Trans. on Electronic Computers 9(1), 39–47 (1960)

    Article  Google Scholar 

  13. Melnikov, B.F.: A new algorithm of the state-minimization for the nondeterministic finite automata. Korean J. Comput. Appl. Math. 6(2), 277–290 (1999)

    MATH  MathSciNet  Google Scholar 

  14. Melnikov, B.F.: Once more about the state-minimization of the nondeterministic finite automata. Korean J. Comput. Appl. Math. 7(3), 655–662 (2000)

    MATH  MathSciNet  Google Scholar 

  15. Navarro, G.: NR-grep: a Fast and Flexible Pattern Matching Tool. Software Practice and Experience 31, 1265–1312 (2001)

    Article  MATH  Google Scholar 

  16. Navarro, G., Raffinot, M.: Fast Regular Expression Search. In: Vitter, J.S., Zaroliagis, C.D. (eds.) WAE 1999. LNCS, vol. 1668, pp. 198–212. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  17. Navarro, G., Raffinot, M.: Compact DFA Representation for Fast Regular Expression Search. In: Brodal, G.S., Frigioni, D., Marchetti-Spaccamela, A. (eds.) WAE 2001. LNCS, vol. 2141, pp. 1–12. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  18. Navarro, G., Raffinot, M.: Flexible Pattern Matching in Strings. Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge University Press, Cambridge (2002)

    MATH  Google Scholar 

  19. Paige, R., Tarjan, R.E.: Three Partition Refinement Algorithms. SIAM J. Comput. 16(6), 973–989 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  20. Thompson, K.: Regular expression search algorithm. Comm. ACM 11(6), 419–422 (1968)

    Article  MATH  Google Scholar 

  21. Wu, S., Mamber, U.: Fast text searching allowing errors, Comm. Comm. ACM 35(10), 83–91 (1992)

    Article  Google Scholar 

  22. Yu, S.: Regular Languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, pp. 41–110. Springer, Berlin (1997)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada

    Lucian Ilie & Sheng Yu

  2. Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago, Chile

    Gonzalo Navarro

Authors
  1. Lucian Ilie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gonzalo Navarro
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sheng Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics and Turku Centre for Computer Science TUCS, University of Turku, 20014, Turku, Finland

    Juhani Karhumäki

  2. Institute for Information Systems and Computer Media (IICM), Graz University of Technology, A-8010, Graz, Austria

    Hermann Maurer

  3. Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700, BucureÅŸti, Romania

    Gheorghe Păun

  4. Leiden Center of Advanced Computer Science (LIACS), Leiden University, Niels Bohrweg 1, 2333, Leiden, CA, The Netherlands

    Grzegorz Rozenberg

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Ilie, L., Navarro, G., Yu, S. (2004). On NFA Reductions. In: Karhumäki, J., Maurer, H., Păun, G., Rozenberg, G. (eds) Theory Is Forever. Lecture Notes in Computer Science, vol 3113. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27812-2_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-27812-2_11

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-22393-1

  • Online ISBN: 978-3-540-27812-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation