On minimizing regular expressions without Kleene star

DOI10.1007/978-3-030-86593-1_17MaRDI QIDQ2140503zbMATH OpenOpenAlexFDO

Authors Hermann Gruber, Markus Holzer, Simon Wolfsteiner

Publication date 20 May 2022

Full work available at URL https://doi.org/10.1007/978-3-030-86593-1_17

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Minimizing nfa's and regular expressions
• STACS 2005
• Simplifying regular expressions. A quantitative perspective
• On a generalization of regular expressions
• Extended regular expressions: succinctness and decidability
• Extended Regular Expressions: Succinctness and Decidability
• Implementation and Application of Automata
• On classes of tractable unrestricted regular expressions
• State elimination heuristics for short regular expressions
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3557270 (Why is no real title available?)
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• Enumerating regular expressions and their languages
• Hardness results for intersection non-emptiness
• If the current clique algorithms are optimal, so is Valiant's parser
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Language operations with regular expressions of polynomial size
• Lower bounds based on the exponential time hypothesis
• Minimizing nfa's and regular expressions
• Nearly tight approximability results for minimum biclique cover and partition
• On minimal grammar problems for finite languages
• On some fine-grained questions in algorithms and complexity
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
• On the compressibility of finite languages and formal proofs
• Problems on finite automata and the exponential time hypothesis
• Regular expressions: new results and open problems
• Two-dimensional pattern matching against basic picture languages
• Which problems have strongly exponential complexity?

Cited in

(3)

• STACS 2005
• scientific article; zbMATH DE number 1134629 (Why is no real title available?)
• On pumping preserving homomorphisms and the complexity of the pumping problem (extended abstract)

This page was built for publication: On minimizing regular expressions without Kleene star

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