Optimal regular expressions for permutations

DOI10.4230/LIPICS.ICALP.2019.121MaRDI QIDQ5092323zbMATH OpenFDO

Authors Jeffrey Shallit

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1812.06347

zbMATH Keywords

divide-and-conquerlower boundsregular expressions

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Regular expression length via arithmetic formula complexity
• Regular expression length via arithmetic formula complexity
• State complexity of permutation on finite languages over a binary alphabet
• The membership problem for linear and regular permutation languages
• The state complexity of permutations on finite languages over binary alphabets

Cites work

• Complexity measures for regular expressions
• Fractional coverings, greedy coverings, and rectifier networks
• Generating all permutations by context-free grammars in Chomsky normal form
• Generating all permutations by context-free grammars in Greibach normal form
• Lower bounds for context-free grammars
• Minimal NFA Problems are Hard
• Minimizing nfa's and regular expressions
• Regular expressions: new results and open problems
• State complexity of permutation on finite languages over a binary alphabet

Cited in

(3)

• scientific article; zbMATH DE number 7559421 (Why is no real title available?)
• Regular expression length via arithmetic formula complexity
• Optimal regular expressions for palindromes of given length

This page was built for publication: Optimal regular expressions for permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092323)