Subregular Expressions and Their Expressive Power

Speaker: Matthias Wendland
Post thumbnail

Regular expressions are classically built using concatenation, union, and Kleene star. Since regular languages are closed under many additional operations, these operations can also be incorporated into expressions without increasing expressive power. This talk investigates how the expressive capabilities change when alternative sets of operations are used instead of the classical ones. We consider several variants of subregular expressions, obtained either by omitting standard operations or by replacing them with operations such as complementation or intersection. The talk presents an overview of recent results concerning the expressive power, structural properties, and closure behavior of the resulting language families. Particular emphasis is placed on language families defined by restricted combinations of operations, including expressions using complement and star, concatenation and complement, or intersection and star, as well as several forms of concatenation-free expressions. We discuss formal characterizations of these families, compare unary and general alphabet cases, and study hierarchies induced by the available operations. The results reveal intricate relationships between the different language classes and provide new insights into the role of individual operations in the description of regular languages.