Document Open Access Logo

Optimal Regular Expressions for Palindromes of Given Length

Authors Hermann Gruber, Markus Holzer

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.52.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Hermann Gruber
  • Knowledgepark GmbH, München, Germany
Markus Holzer
  • Institut für Informatik, University of Giessen, Germany

Acknowledgements

We would like to thank the anonymous reviewers for their valuable suggestions.

Cite As Get BibTex

Hermann Gruber and Markus Holzer. Optimal Regular Expressions for Palindromes of Given Length. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.52

Abstract

The language P_n (P̃_n, respectively) consists of all words that are palindromes of length 2n (2n-1, respectively) over a fixed binary alphabet. We construct a regular expression that specifies P_n (P̃_n, respectively) of alphabetic width 4⋅ 2ⁿ-4 (3⋅ 2ⁿ-4, respectively) and show that this is optimal, that is, the expression has minimum alphabetic width among all expressions that describe P_n (P̃_n, respectively). To this end we give optimal expressions for the first k palindromes in lexicographic order of odd and even length, proving that the optimal bound is 2n+4(k-1)-2 S₂(k-1) in case of odd length and 2n+3(k-1)-2 S₂(k-1)-1 for even length, respectively. Here S₂(n) refers to the Hamming weight function, which denotes the number of ones in the binary expansion of the number n.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Mathematics of computing → Nonlinear equations
Keywords
  • regular expression
  • descriptional complexity
  • lower bound
  • upper bound
  • recurrence
  • sum of digits

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. R. Ben-Basat, A. Gabizon, and M. Zehavi. The k-distinct language: Parameterized automata constructions. Theoretical Computer Science, 622:1-15, 2016. Google Scholar
  2. D. Chistikov, Sz. Iván, A. Lubiw, and J. Shallit. Fractional coverings, greedy coverings, and rectifier networks. In Heribert Vollmer and Brigitte Vallée, editors, Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1-23:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  3. N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113-124, 1956. Google Scholar
  4. E. Cseresnyes and H. Seiwert. Regular expression length via arithmetic formula complexity. In G. Jirásková and G. Pighizzini, editors, 22nd International Conference on Descriptional Complexity of Formal Systems, volume 12442 of LNCS, pages 26-38. Springer, 2020. Google Scholar
  5. K. Edwards and G. Farr. Improved upper bounds for planarization and series-parallelization of degree-bounded graphs. The Electronic Journal of Combinatorics, 19(2):#P25, 2012. Google Scholar
  6. A. Ehrenfeucht and H. P. Zeiger. Complexity measures for regular expressions. Journal of Computer and System Sciences, 12(2):134-146, April 1976. URL: https://doi.org/10.1016/S0022-0000(76)80034-7.
  7. K. Ellul, B. Krawetz, J. Shallit, and M.-W. Wang. Regular expressions: New results and open problems. Journal of Automata, Languages and Combinatorics, 10(4):407-437, 2005. Google Scholar
  8. Y. Gao, N. Moreira, R. Reis, and S. Yu. A survey on operational state complexity. Journal of Automata, Languages and Combinatorics, 21(4):251-310, 2016. Google Scholar
  9. W. Gelade. Succintness of regular expressions with interleaving, intersection, and counting. Theoretical Computer Science, 411(31-33):2987-2998, 2010. URL: https://doi.org/10.1016/j.tcs.2010.04.036.
  10. W. Gelade and F. Neven. Succinctness of the complement and intersection of regular expressions. ACM Transactions on Computational Logic, 13(1):No. 4, January 2012. URL: https://doi.org/10.1145/2071368.2071372.
  11. D. H. Greene and D. E. Knuth. Mathematics for the Analysis of Algorithms. Progress in Computer Science. Birkhäuser, 2nd edition, 1982. Google Scholar
  12. H. Gruber and M. Holzer. Finite automata, digraph connectivity, and regular expression size. In L. Aceto, I. Damgaard, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walkuwiewicz, editors, Proceedings of the 35th International Colloquium on Automata, Languages and Propgramming, number 5126 in LNCS, pages 39-50, Reykjavik, Iceland, July 2008. Springer. URL: https://doi.org/10.1007/978-3-540-70583-3_4.
  13. H. Gruber and M. Holzer. Tight bounds on the descriptional complexity of regular expressions. In V. Diekert and D. Nowotka, editors, Proceedings of the 13th International Conference Developments in Language Theory, number 5583 in LNCS, pages 276-287, Stuttgart, Germany, June-July 2009. Springer. URL: https://doi.org/10.1007/978-3-642-02737-6_22.
  14. H. Gruber and J. Johannsen. Tight bounds on the descriptional complexity of regular expressions. In R. Amadio, editor, Proceedings of the 11th Conference Foundations of Software Science and Computational Structures, number 4962 in LNCS, pages 273-286, Budapest, Hungary, March-April 2008. Springer. Google Scholar
  15. M. Holzer and M. Kutrib. Descriptional and computational complexity of finite automata - a survey. Information and Computation, 209(3):456-470, March 2011. URL: https://doi.org/10.1016/j.ic.2010.11.013.
  16. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. Google Scholar
  17. P. Hrubes and A. Yehudayoff. Homogeneous formulas and symmetric polynomials. Computational Complexity, 20(3):559-578, 2011. Google Scholar
  18. H.-K. Hwang and T.-H. Tsai. An asymptotic theory for recurrence relations based on minimization and maximization. Theoretical Computer Science, 290(3):1475-1501, 2003. Google Scholar
  19. S. Jukna. Extremal Combinatorics: With Applications in Computer Science. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2nd edition, 2011. Google Scholar
  20. D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, 3rd edition, 1998. Google Scholar
  21. D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, 3rd edition, 1998. Google Scholar
  22. A.-M. Legendre. Essai sur la théorie des nombres. Courcier, 2ème edition, 1808. Google Scholar
  23. A. M. Lovett and J. O. Shallit. Optimal regular expressions for permutations. In Ch. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, editors, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132 of LIPIcs, pages 121:1-121:12, Patras, Greece, July 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact