2018/12/15 by Lovett, Antonio Molina, Shallit, Jeffrey
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1812.06347
The permutation language Pn consists of all words that are permutations of a fixed alphabet of size n. Using divide-and-conquer, we construct a regular expression Rn that specifies Pn. We then give explicit bounds for the length of Rn, which we find to be 4n n-(\lg n)/4+Θ(1), and use these bounds to show that Rn has minimum size over all regular expressions specifying Pn.