scientific article; zbMATH DE number 7561614

DOI10.4230/LIPIcs.ICALP.2019.121MaRDI QIDQ5092323

Unnamed Author, Jeffrey O. Shallit

Publication date: 21 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

regular expressionslower boundsdivide-and-conquer

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ Regular expression length via arithmetic formula complexity

Cites Work

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

This page was built for publication: