LIPIcs.ICALP.2019.121.pdf
- Filesize: 435 kB
- 12 pages
Document
Optimal Regular Expressions for Permutations (Track B: Automata, Logic, Semantics, and Theory of Programming)
Authors
Antonio Molina Lovett 
,
Jeffrey Shallit
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
File
Document Identifiers
Author Details
Cite As Get BibTex
Antonio Molina Lovett and Jeffrey Shallit. Optimal Regular Expressions for Permutations (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 121:1-121:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.121
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Formal languages and automata theory
Keywords
- regular expressions
- lower bounds
- divide-and-conquer
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Rakesh Agrawal, Giuseppe Psaila, Edward L. Wimmers, and Mohamed Zait. Querying Shapes of Histories. Technical Report RJ 9962 (87921), IBM Almaden Research Center, June 26 1995.
-
P. R. J. Asveld. Generating all permutations by context-free grammars in Chomsky normal form. Theoret. Comput. Sci., 354:118-130, 2006.
-
P. R. J. Asveld. Generating all permutations by context-free grammars in Greibach normal form. Theoret. Comput. Sci., 409:565-577, 2008.
-
D. Chistikov, S. Ivan, A. Lubiw, and J. Shallit. Fractional Coverings, Greedy Coverings, and Rectifier Networks. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of LIPIcs, pages 23:1-23:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
- Da Jung Cho, Daniel Goč, Yo-Sub Han, Sang Ki Ko, Alexandros Palioudakis, and Kai Salomaa. State complexity of permutation on finite languages over a binary alphabet. Theoretical Computer Science, 682:67-78, June 2017. URL: http://dx.doi.org/10.1016/j.tcs.2017.03.007.
-
A. Ehrenfeucht and P. Zeiger. Complexity measures for regular expressions. J. Comput. System Sci., 12:134-146, 1976.
-
K. Ellul, B. Krawetz, J. Shallit, and M.-w. Wang. Regular expressions: new results and open problems. J. Autom. Lang. Combin., 10:407-437, 2005.
-
Y. Filmus. Lower bounds for context-free grammars. Info. Proc. Letters, 111:895-898, 2011.
-
G. Gramlich and G. Schnitger. Minimizing nfa’s and regular expressions. J. Comput. System Sci., 73:908-923, 2007.
- J. L. W. V. Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Math., 30:175-193, 1906. URL: http://dx.doi.org/10.1007/BF02418571.
-
T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM J. Comput., 22:1117-1141, 1993.
-
A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proc. 13th Ann. IEEE Symp. on Switching and Automata Theory, pages 125-129. IEEE, 1972.
- H. Mousavi. Lower bounds on regular expression size. Preprint available at https://arxiv.org/abs/1712.00811, 2017.
-
H. Robbins. A Remark on Stirling’s Formula. Amer. Math. Monthly, 62:26-29, 1955.
- N. J. A. Sloane et al. The On-Line Encyclopedia of Integer Sequences. Available at https://oeis.org, 2018.