Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with regular expressions:
TR20-079 | 15th May 2020
Hermann Gruber , Markus Holzer, Simon Wolfsteiner

On Minimizing Regular Expressions Without Kleene Star

Finite languages lie at the heart of literally every regular expression. Therefore, we investigate the approximation complexity of minimizing regular expressions without Kleene star, or, equivalently, regular expressions describing finite languages. On the side of approximation hardness, given such an expression of size~$s$, we prove that it is impossible to ... more >>>

ISSN 1433-8092 | Imprint