Descriptional Complexity of Chop Operations on Unary and Finite Languages
Markus Holzer, Sebastian Jakobi · Universitätsbibliothek Gießen · 2012
We continue our research on the descriptional complexity of chop operations. Informally, the chop of two words is like their concatenation with the touching letters merged if they are equal, otherwise their chop is undefined. The iterated variants chop-star and chop-plus are defined similar as the classical operations Kleene star and plus. We investigate the state complexity of chop operations on unary and/or finite languages, and obtain similar bounds as for the classical operations. Further, we also show that any chop expression, describing a unary language, can be converted into an equivalent regular expression of linear size, which nicely contrasts the general case.