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 based on the chop operation or 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. It turns out, that in most cases we obtain exponential upper and lower bounds that are asymptotically close, for the investigated inverse language operation problems.
On inverse operations and their descriptional complexity / M.P. Bianchi, C. Mereghetti, B. Palano, G. Pighizzini, M. Holzer, S. Jakobi. - In: JOURNAL OF AUTOMATA, LANGUAGES AND COMBINATORICS. - ISSN 1430-189X. - 17:2/4(2012), pp. 61-81.
On inverse operations and their descriptional complexity
M.P. BianchiPrimo
;C. MereghettiSecondo
;B. Palano;G. Pighizzini;
2012
Abstract
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 based on the chop operation or 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. It turns out, that in most cases we obtain exponential upper and lower bounds that are asymptotically close, for the investigated inverse language operation problems.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
313.95 kB
Formato
Adobe PDF
|
313.95 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.