Succinct representation of regular sets using gotos and boolean variables

摘要

Regular expressions can be extended by gotos and Boolean variables. Although such extensions do not increase the class of expressible languages, they do permit shorter expressions for some languages. This paper investigates the relative economies of extended and ordinary regular expressions. It is shown that there is a size n expression with Boolean variables which is not equivalent to any ordinary regular expression of size less than a double exponential function of n. It is also shown that there is a size n expression containing a single goto and no variables which is equivalent to no ordinary regular expression of size less than cn log n, for some constant c.