Back to Search
Start Over
Optimal Regular Expressions for Permutations
- Publication Year :
- 2018
- Publisher :
- arXiv, 2018.
-
Abstract
- The permutation language $P_n$ consists of all words that are permutations of a fixed alphabet of size $n$. Using divide-and-conquer, we construct a regular expression $R_n$ that specifies $P_n$. We then give explicit bounds for the length of $R_n$, which we find to be $4^n n^{-(\lg n)/4+\Theta(1)}$, and use these bounds to show that $R_n$ has minimum size over all regular expressions specifying $P_n$.<br />Comment: 14 pages
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....c0060065b99db03e723922406434dd38
- Full Text :
- https://doi.org/10.48550/arxiv.1812.06347