Abstract
We prove lower bounds on the length of regular expressions for finite languages by methods from arithmetic circuit complexity. First, we show a reduction from expression length to monotone arithmetic formula size. This yields lower bounds of \(nk^{\varOmega (\log k)}\) for the binomial language of all words with exactly k ones and \(n-k\) zeros, and of \(n^{\varOmega (\log n)}\) for the language of all Dyck words of length 2n. We also determine the blow-up of expression length when applying the operations intersection or shuffle to finite languages. Second, we adapt a lower bound method for multilinear arithmetic formulas by Hrubeš and Yehudayoff to regular expressions. With this method we give a tight lower bound of \(\varOmega (n^{-1} p^{ \log (n / \log p)-2 })\) for the language of all binary numbers with n bits that are divisible by a given odd integer p.
H. Seiwert—Partially supported by DFG grant JU 3105/1–2 (German Research Foundation).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Birget, J.-C.: Intersection and union of regular languages and state complexity. Inf. Process. Lett. 43(4), 185–190 (1992). https://doi.org/10.1016/0020-0190(92)90198-5
Chen, Y.: The Chung-Feller theorem revisited. Discrete Mathematics 308(7), 1328–1329 (2008). https://doi.org/10.1016/j.disc.2007.03.068
Ehrenfeucht, A., Zeiger, P.: Complexity measures for regular expressions. J. Comput. Syst. Sci. 12(2), 134–146 (1976). https://doi.org/10.1016/S0022-0000(76)80034-7
Ellul, K., Krawetz, B., Shallit, J., Wang, M.-W.: Regular expressions: new results and open problems. J. Autom. Lang. Comb. 9(2–3), 233–256 (2004). https://doi.org/10.25596/jalc-2004-233
Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. ACM Trans. Comput. Logic (TOCL) 13(1), 4 (2012). https://doi.org/10.1145/2071368.2071372
Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Inf. Process. Lett. 59(2), 75–77 (1996). https://doi.org/10.1016/0020-0190(96)00095-6
Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: ICALP, pp. 39–50. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_4
Gruber, H., Holzer, M.: Tight bounds on the descriptional complexity of regular expressions. In: Developments in Language Theory, pp. 276–287. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02737-6_22
Gruber, H., Johannsen, J.: Optimal lower bounds on regular expression size using communication complexity. In: FoSSaCS, pp. 273–286. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78499-9_20
Holzer, M., Kutrib, M.: The complexity of regular(-like) expressions. Int. J. Found. Comput. Sci. 22(7), 1533–1548 (2011). https://doi.org/10.1142/S0129054111008866
Hrubeš, P., Yehudayoff, A.: Homogeneous formulas and symmetric polynomials. Comput. Complexity 20(3), 559–578 (2011). https://doi.org/10.1007/s00037-011-0007-3
Jerrum, M., Snir, M.: Some exact complexity results for straight-line computations over semirings. J. ACM 29(3), 874–897 (1982). https://doi.org/10.1145/322326.322341
Jukna, S.: Boolean Function Complexity: Advances and Frontiers, vol. 27. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-24508-4
Jukna, S.: Tropical complexity, sidon sets, and dynamic programming. SIAM J. Discrete Math. 30, 2064–2085 (2016). https://doi.org/10.1137/16M1064738
Khrapchenko, V.M.: Method of determining lower bounds for the complexity of \(P\)-schemes. Math. Notes Acad. Sciences USSR 10(1), 474–479 (1971)
Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: 13th Annual Symposium on Switching and Automata Theory, pp. 125–129 (1972). https://doi.org/10.1109/SWAT.1972.29
Molina Lovett, A., Shallit, J.: Optimal regular expressions for permutations. In: ICALP, pp. 121:1–12 (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.121
Mousavi, H.: Lower bounds on regular expression size. CoRR abs/1712.00811 (2017). http://arxiv.org/abs/1712.00811
Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3–4), 207–388 (2010). https://doi.org/10.1561/0400000039
Acknowledgments
We wish to thank Mario Holldack, Stasys Jukna and Georg Schnitger for inspiring discussions and thank the anonymous referees for their kind and useful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Cseresnyes, E., Seiwert, H. (2020). Regular Expression Length via Arithmetic Formula Complexity. In: Jirásková, G., Pighizzini, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2020. Lecture Notes in Computer Science(), vol 12442. Springer, Cham. https://doi.org/10.1007/978-3-030-62536-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-62536-8_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62535-1
Online ISBN: 978-3-030-62536-8
eBook Packages: Computer ScienceComputer Science (R0)