Series Parallel Digraphs with Loops
Tóm tắt
In the conversion of finite automata to regular expressions, an exponential blowup in size can generally not be avoided. This is due to graph-structural properties of automata which cannot be directly encoded by regular expressions and cause the blowup combinatorially. In order to identify these structures, we generalize the class of arc-series-parallel digraphs beyond the acyclic case. The resulting digraphs are shown to be reversibly encoded by linear-sized regular expressions. Also, a characterization of this new class by a set of seven forbidden substructures is given. Automata that require expressions of superlinear size must contain some of these substructures.
Tài liệu tham khảo
Bodlaender, H.L., de Fluiter, B.: Parallel algorithms for series parallel graphs and graphs with treewidth two. Algorithmica 29(4), 534–559 (2001)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Monographs on Discrete Mathematics and Applications, vol. 3 (1999)
Caron, P., Ziadi, D.: Characterization of Glushkov automata. Theor. Comput. Sci. 233(1–2), 75–90 (2000)
Chrobak, M.: Finite automata and unary languages. Theor. Comput. Sci. 47, 149–158 (1986)
Diestel, R.: Graph Theory, 3th edn. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2006)
Ehrenfeucht, A., Zeiger, P.: Complexity measures for regular expressions. J. Comput. Syst. Sci. 12, 134–146 (1976)
Ellul, K., Krawetz, B., Shallit, J., Wang, M.W.: Regular expressions: new results and open problems. J. Autom. Lang. Comb. 10(4), 407–437 (2005)
Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: STACS, pp. 325–336 (2008)
Giammarresi, D., Ponty, J.L., Wood, D., Ziadi, D.: A characterization of Thompson digraphs. Discrete Appl. Math. 134, 317–337 (2004)
Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: ICALP 2008, Part II. LNCS, vol. 5126, pp. 39–50. Springer, Berlin (2008)
Gruber, H., Johannsen, J.: Optimal lower bounds on regular expression size using communication complexity. In: FOSSAC 2008. LNCS, vol. 4962, pp. 273–286 (2008)
Gulan, S., Fernau, H.: Local elimination-strategies in finite automata for shorter regular expressions. In: Theory and Practice of Computer Science: SOFSEM 2008, vol. 2, pp. 46–57 (2008)
Gulan, S., Fernau, H.: An optimal construction of finite automata from regular expressions. In: 28th FSTTCS, pp. 211–222 (2008)
Gulan, S.: On the relative descriptional complexity of regular expressions and finite automata. Ph.D. thesis, Universität Trier (2011)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)
Hromkovič, J., Seibert, S.: Translating regular expressions into small epsilon-free nondeterministic finite automata. J. Comput. Syst. Sci. 62, 565–588 (2001)
Huet, G.: Confluent reductions: abstract properties and applications to term rewriting systems. J. ACM 27(4), 797–821 (1980)
Jakoby, A., Tantau, T.: Logspace algorithms for computing shortest and longest paths in series-parallel graphs. In: 27th FSTTCS, pp. 216–227 (2007)
Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Annals of Mathematics Studies, pp. 3–41 (1956)
Korenblit, M., Levit, V.E.: On algebraic expressions of series-parallel and Fibonacci graphs. In: DMTCS 2003. LNCS, vol. 2731, pp. 215–224. Springer, Berlin (2003)
McNaughton, R.: Techniques for manipulating regular expressions. In: Systems and Computer Science, pp. 27–41. University of Toronto Press in association with the University of Western Ontario Toronto, Toronto (1967)
Moreira, N., Reis, R.: Series-parallel automata and short regular expressions. Fundam. Inform. 91(3–4), 611–629 (2009)
Newman, M.: On theories with a combinatorial definition of “equivalence”. Annals of Mathematics 43(2), 223–243 (1942)
Valdes, J.: Parsing flowcharts and series-parallel graphs. Ph.D. thesis, Stanford University (1978). STAN-CS-78-682
Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298–313 (1981)
Watson, B.W.: A taxonomy of finite automata construction algorithms. Tech. Rep. Computing Science Note 93/43, Eindhoven University of Technology (1994)