Technical Reports

The ICICS/CS Reading Room

UBC CS TR-82-03 Summary

The Complexity of Regular Expressions with Goto and Boolean Variables, March 1982 Karl Abrahamson

Regular expressions can be extended by adding gotos and Boolean variables. Although such extensions do not increase the class of expressible languages, they do permit shorter expressions for some languages. The output space complexity of eliminating Boolean variables is shown to be double exponential. The complexity of eliminating a single goto from a regular expression is shown to be \( \Omega (n \log n) \), a surprising result considering that $n$ gotos can be eliminated in single exponential space.

If you have any questions or comments regarding this page please send mail to