Series-Parallel Automata and Short Regular Expressions

• Autorzy: Moreira N. , Reis R.
• Języki publikacji: EN

Abstrakty

EN

Computing short regular expressions equivalent to a given finite automaton is a hard task. In this work we present a class of acyclic automata for which it is possible to obtain in time O(n^2 log n) an equivalent regular expression of size O(n). A characterisation of this class is made using properties of the underlying digraphs that correspond to the series-parallel digraphs class. Using this characterisation we present an algorithm for the generation of automata of this class and an enumerative formula for the underlying digraphs with a given number of vertices.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 3-4
• Strony: 611--629
• Opis fizyczny: Bibliogr. 35 poz., tab., wykr.

Twórcy

autor

Moreira N.

autor

Reis R.

• DCC-FC & LIACC, Universidade do Porto R. do Campo Alegre 1021/1055, 4169-007 Porto, Portugal,

Bibliografia

• [1] Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms, and Applications, Monographs in Mathematics, Springer-Verlag, 2001.
• [2] Bodirsky,M., Gimenez, O., Kang, M., Noy, M.: Enumeration and limit laws of series-parallel graphs, European Journal on Combinatorics, 28(8), November 2007, 2091-2105.
• [3] Bodlaender, H. L., de Fluiter, B.: Parallel Algorithms for Series Parallel Graphs, European Symp. on Algorithms, 1996.
• [4] Caron, P., Ziadi, D.: Characterization of Glushkov automata, Theor. Comput. Sci., 233(1-2), 2000, 75-90.
• [5] Duffin, R. J.: Topology of Series-Parallel Networks, J. of Math. Analysis and Appl., 10, 1965, 303-318.
• [6] Ellul, K., Krawetz, B., Shallit, J.,Wang, M.: Regular Expressions: New Results and Open Problems, Journal of Automata, Languages and Combinatorics, 10(4), 2005, 407-437.
• [7] Eppstein, D.: Parallel Recognition of Series-Parallel Graphs, Inf. Comput., 98(1), 1992, 41-55.
• [8] Finch, S.: Mathematical Constants, chapter Series-parallel networks, Cambridge University Press, 2003.
• [9] Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphismproblem, Theoretical Computer Science, 10, 1980, 111-121.
• [10] Fusy, E., Kang, M., Shoilekova, B.: A Complete Grammar for Decomposing a Family of Graphs into 3-connected Components, Submitted, Nov. 2007.
• [11] Giammarresi, D., Ponty, J.-L., Wood, D., Ziadi, D.: A characterization of Thompson digraphs, Discrete Applied Mathematics, 134(1-3), 2004, 317-337.
• [12] Golinelli, O.: Asymptotic behavior of two-terminal series-parallel networks, Technical Report t97/074, CEA Sacley, Servive de Physique Théorique, 1997.
• [13] Gruber, H., Holzer, M.: Provably Shorter Regular Expressions from Deterministic Finite Automata, Proceedings of the 12th International Conference Developments in Language Theory (M. Ito, M. Toyama, Eds.), number 5257, Springer, Kyoto, September 2008.
• [14] Gulan, S., Fernau, H.: Local elimination-strategies in automata for shorter regular expressions, SOFSEM 2008, Novy Smokovec, Slovakia, 2008, Volume II - Student Research Forum (V. Geffert, J. Karhumäki, A. Bertoni, B. Preneel, P. Návrat, M. Bieliková, Eds.), 2008, ISBN 978-80-7097-697-5.
• [15] Han, Y.-S., Wood, D.: Obtaining Shorter Regular Expressions from Finite-State Automata, Theor. Comp. Science, 370, 2007, 110-120.
• [16] Harary, F.: Graph Theory, 6th edition, Addison Wesley, 1969.
• [17] He, X., Yesha, Y.: Parallel Recognitions and Decomposition of Two Terminal Series Parallel Graphs, Inf. Comput., 75(1), 1987, 15-38.
• [18] Hopcroft, J., Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, Addison Wesley, 2000.
• [19] Jiang, T., Ravikumar, B.: Minimal NFA problems are hard, SIAM Journal of Computation, 1993, 1117-1141.
• [20] Kleene, S. C.: Representation of events in nerve nets and finite automata, in: Automata Studies (C. E. Shannon, J. McCarthy, Eds.), Princeton University Press, 1956, 3-41.
• [21] Lombardy, S., Sakarovitch, J.: Corrigendum to our paper: How expressions can code for automata, Http://www.infres.enst.fr/ jsaka/PUB/pub.html.
• [22] Lombardy, S., Sakarovitch, J.: How expressions can code for automata, RAIRO- Theoret. Informatics and Appl., 39, 2005, 217-237.
• [23] Moon, J. W.: Some enumerative results on series-parallel networks, Annals Discrete Math., 1987, 199-226.
• [24] Morais, J. J.: Computing small regular expressions from finite automata., Master Thesis, DCC-FCUP, 2005.
• [25] Morais, J. J., Moreira, N., Reis, R.: Acyclic Automata with easy-to-find short regular expressions, Technical Report DCC-2005-03, DCC-FC& LIACC, Universidade do Porto, April 2005.
• [26] Morais, J. J., Moreira, N., Reis, R.: Acyclic Automata with easy-to-find short regular expressions, CIAA 2005, Tenth International Conference on Implementation and Application of Automata (I. L. Jacques Farré, S. Schmitz, Eds.), 3845, Springer-Verlag, 2005.
• [27] Reis, R.: Aut´omatos:manipulac¸ao, gerac¸ao e enumerac¸ao, Ph.D. Thesis, Faculdade de Ciencias da Universidade do Porto, 2007.
• [28] Riordan, J., Shannon, C. E.: The number of two terminal series parallel networks, J. Mathmatical Physics, 21(83-93), 1942.
• [29] Sakarovitch, J.: Élements de théorie des automates, Vuibert Informatique, 2003.
• [30] Sakarovitch, J.: The Language, the Expression, and the (Small) Automaton., Implementation and Application of Automata, 10th International Conference, CIAA 2005, 3845, Springer, 2006.
• [31] Sloane, N.: The On-line Encyclopedia of Integer Sequences, 2003, http://www.research.att.com/~njas/sequences.
• [32] Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on seriesparallel graphs, J. ACM, 29(3), 1982, 623-641, ISSN 0004-5411.
• [33] Thompson, K.: Regular expression search algorithm, Communications of the ACM, 11(6), 1968, 410-422.
• [34] Valdes, J., Tarjan, R. E., Lawler, E. L.: The recognition of Series Parallel digraphs, STOC '79: Proceedings of the eleventh annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1979.
• [35] Yu, S.: Regular languages, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), vol. 1, Springer-Verlag, 1997.