On Inverse Operations and Their Descriptional Complexity
Maria Paola Bianchi, Markus Holzer, Sebastian Jakobi, Carlo Mereghetti, Palano, Betrice, Giovanni Pighizzini · Universitätsbibliothek Gießen · 2012
We investigate the descriptional complexity of some inverse language operations applied to languages accepted by finite automata. For instance, the inverse Kleene star operation for a language $L$ asks for the smallest language $S$ such that $S^*$ is equal to $L$, if it exists [J. Brzozowski. Roots of star events. J. ACM 14, 1967]. Other inverse operations, for example based on insertion/deletion operations, can be defined appropriately. We present a general framework, that allows us to give an easy characterization of inverse operations, whenever simple conditions on the originally considered language operation are fulfilled. Concerning the state complexity of some inverse operations, in most cases we obtain exponential upper and lower bounds, while for unary languages tight linear bounds are obtained.