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, M. Holzer, S. Jakobi, G. Pighizzini - In: Descriptional complexity of formal systems : 14th International Workshop, DCFS 2012, Braga, Portugal, July 23-25, 2012. Proceedings / [a cura di] M. Kutrib, N. Moreira, R. Reis. - New York : Springer, 2012. - ISBN 9783642316227. - pp. 89-102 (( Intervento presentato al 14. convegno International Workshop Descriptional Complexity of Formal Systems (DCFS) tenutosi a Braga nel 2012.

On Inverse Operations and Their Descriptional Complexity

M. P. Bianchi
Primo
;
G. Pighizzini
Ultimo
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.
Settore INF/01 - Informatica
2012
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/202238
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 1
social impact