Two language operations that can be expressed by suitably combining complement with concatenation and star, respectively, are introduced. The state complexity of those operations on regular languages is investigated. In the deterministic case, optimal exponential state gaps are proved for both operations. In the nondeterministic case, for one operation an optimal exponential gap is also proved, while for the other operation an exponential upper bound is obtained.
Universal Disjunctive Concatenation and Star / N. Moreira, G. Pighizzini, R. Reis (LECTURE NOTES IN COMPUTER SCIENCE). - In: Descriptional Complexity of Formal Systems / [a cura di] J. Shallit, A. Okhotin. - [s.l] : Springer, 2015. - ISBN 9783319192246. - pp. 197-208 (( Intervento presentato al 17. convegno International Workshop DCFS tenutosi a Waterloo nel 2015 [10.1007/978-3-319-19225-3_17].
Universal Disjunctive Concatenation and Star
G. Pighizzini;
2015
Abstract
Two language operations that can be expressed by suitably combining complement with concatenation and star, respectively, are introduced. The state complexity of those operations on regular languages is investigated. In the deterministic case, optimal exponential state gaps are proved for both operations. In the nondeterministic case, for one operation an optimal exponential gap is also proved, while for the other operation an exponential upper bound is obtained.
| File | Dimensione | Formato | |
|---|---|---|---|
|
krkonos01.pdf
accesso riservato
Descrizione: Articolo
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
301.02 kB
Formato
Adobe PDF
|
301.02 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.
