State Elimination Heuristics for Short Regular Expressions

• Autorzy: Han Y-S.
• Języki publikacji: EN

Abstrakty

EN

State elimination is an intuitive and easy-to-implement algorithm that computes a regular expression from a finite-state automaton (FA). It is very hard to compute the shortest regular expression for a given FA in general and we cannot avoid the exponential blow-up. This implies that state elimination cannot avoid the exponential blow-up either. Nevertheless, since the size of a regular expression by state elimination depends on the state removal sequence, we can have a shorter regular expression if we choose a better removal sequence for state elimination. This observation motivates us to examine state elimination heuristics based on the structural properties of the input FA and implement state elimination using the heuristics that run in polynomial time. We demonstrate the effectiveness of our algorithm by experiment results.

Słowa kluczowe

EN

finite-state automata; heuristics; regular expressions; state elimination

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 128, nr 4
• Strony: 445--462
• Opis fizyczny: Bibliogr. 27 poz., rys., tab., wykr.

Twórcy

autor

Han Y-S.

• Department of Computer Science, Yonsei University, Seoul 120-794, Republic of Korea

Bibliografia

• [1] M. Almeida, N. Moreira, and R. Reis. Enumeration and generation with a string automata representation. Theoretical Computer Science, 387(2):93-102, 2007.
• [2] M. Almeida, N. Moreira, and R. Reis. On the performance of automata minimization algorithms. Technical Report DCC-2007-03, DCC - FC & LIACC, Universidade do Porto, June 2007.
• [3] A. Briiggemann-Klein and D. Wood. The validation of SGML content models. Mathematical and Computer Modelling, 25:73-84, 1997.
• [4] A. Briiggemann-Klein and D. Wood. One-unambiguous regular languages. Information and Computation, 140:229-253, 1998.
• [5] J. Brzozowski and E. McCluskey, Jr. Signal flow graph techniques for sequential circuit state diagrams. IEEE Transactions on Electronic Computers, EC-12:67-76, 1963.
• [6] J.-M. Champarnaud, G. Hansel, T. Paranthoen, and D. Ziadi. Random generation models for nfas. Journal of Automata, Languages and Combinatorics, 9(2/3):203-216, 2004.
• [7] M. Delgado and J. Morais. Approximation to the smallest regular expression for a given regular language. In Proceedings of CIAA ’04, Lecture Notes in Computer Science 3317, 312-314, 2004.
• [8] S. Eilenberg. Automata, Languages, and Machines, volume A. Academic Press, New York, NY, 1974.
• [9] K. Ellul, B. Krawetz, J. Shallit, and M.-W. Wang. Regular expressions: New results and open problems. Journal of Automata, Languages and Combinatorics, 10:407-437, 2005.
• [10] D. Giammarresi and R. Montalbano. Deterministic generalized automata. Theoretical Computer Science, 215:191-208, 1999.
• [11] V Glushkov. On a synthesis algorithm for abstract automata. Ukr.Matem. Zhurnal, 12(2):147-156, 1960. In Russian.
• [12] H. Gruber and M. Holzer Provably shorter regular expressions from deterministic finite automata. In Proceedings ofDLT’08, Lecture Notes in Computer Science 5257, 383-395, 2008.
• [13] S. Gulan and H. Fernau. Local elimination-strategies in automata for shorter regular expressions. In Proceedings of SOFSEM’08, 46-57, 2008.
• [14] Y.-S. Han and D. Wood. The generalization of generalized automata: Expression automata. International Journal of Foundations of Computer Science, 16(3):499-510, 2005.
• [15] Y.-S. Han and D. Wood. Obtaining shorter regular expressions from finite-state automata. Theoretical Computer Science, 370(1-3): 110-120, 2007.
• [16] J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 2 edition, 1979.
• [17] L. Ilie and S. Yu. Follow automata. Information and Computation, 186(1):140-162,2003.
• [18] T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117-1141, 1993.
• [19] S. Kleene. Representation of events in nerve nets and finite automata. In C. Shannon and J. McCarthy, editors, Automata Studies, 3-42, Princeton, NJ, 1956. Princeton University Press.
• [20] T. K. S. Leslie. Efficient approaches to subset construction. Master’s thesis, Waterloo, Ontario, Canada, 1995.
• [21] R. McNaughton and H. Yamada. Regular expressions and state graphs for automata. IEEE Transactions on Electronic Computers, 9:39-47, 1960.
• [22] A. Meyer and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential time. In Proceedings of the Thirteenth Annual IEEE Symposium on Switching and Automata Theory, 125-129, 1972.
• [23] N. Moreira and R. Reis. Series-parallel automata and short regular expressions. Fundamenta Informaticae, 91(3-4):611-629, 2009.
• [24] D. Raymond and D. Wood. Grail: Engineering automata in C++. Technical Report 345, Department of Computer Science, University of Western Ontario, London, Ontario, Canada, 1993.
• [25] S. H. Rodger and T. W. Finley. JFLAP: An Interactive Formal Languages and Automata Package. Jones & Bartlett Pub, 2006.
• [26] K. Thompson. Regular expression search algorithm. Communications of the ACM, 11:419-422, 1968.
• [27] D. Wood. Theory of Computation. John Wiley & Sons, Inc., New York, NY, 1987.