The validity problem for extended regular expressions
Daniele Micciancio · 1996
The study of regular expressions, possibly extended with operators other than the usual union, concatenation and star, has traditionally focused on closed expressions, i.e. expressions not containing free language variables. In this thesis we consider open expressions (i.e. expressions that may contain language variables) and the problem of deciding valid equations between them. In particular, we study constant-free shuffle-intersection regular expressions, that is, expressions containing only language variables and using the shuffle and intersection operators in addition to the usual union, concatenation and star. We prove the decidability of valid equations and in-equations between such expressions. This result is achieved introducing a new semantics for constant-free shuffleintersection regular expressions. We prove that our semantics is correct and fully abstract. We then reduce the problem of deciding if two expressions have the same semantics to the equivalence problem of finite ...