文章基本信息

标题：Optimal Regular Expressions for Permutations
本地全文：下载
作者：Antonio Molina Lovett ; Jeffrey Shallit
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-12
DOI：10.4230/LIPIcs.ICALP.2019.121
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：regular expressions; lower bounds; divide-and-conquer