2026-08-17T14:42:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14492 2024-03-06T10:54:09Z ddc:004 open_access

Optimal Regular Expressions for Palindromes of Given Length Gruber, Hermann Holzer, Markus regular expression descriptional complexity lower bound upper bound recurrence sum of digits 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hermann Gruber and Markus Holzer 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.52 urn:nbn:de:0030-drops-144921 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.52 eng https://creativecommons.org/licenses/by/4.0/legalcode