We compare the descriptional power of quantum finite automata with control language (QFCS) and deterministic finite automata (DFAS). By suitably adapting Rabin's technique, we show how to convert any given qfc to an equivalent dfa, incurring in an at most exponential size increase. This enables us to state a lower bound on the size of qfcs, which is logarithmic in the size of equivalent minimal dfas. In turn, this result yields analogous size lower bounds for several models of quantum finite automata in the literature.
Size lower bounds for quantum automata / M.P. Bianchi, C. Mereghetti, B. Palano. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 551:C(2014 Sep 25), pp. 102-115. [10.1016/j.tcs.2014.07.004]
Size lower bounds for quantum automata
M.P. BianchiPrimo
;C. Mereghetti
;B. PalanoUltimo
2014
Abstract
We compare the descriptional power of quantum finite automata with control language (QFCS) and deterministic finite automata (DFAS). By suitably adapting Rabin's technique, we show how to convert any given qfc to an equivalent dfa, incurring in an at most exponential size increase. This enables us to state a lower bound on the size of qfcs, which is logarithmic in the size of equivalent minimal dfas. In turn, this result yields analogous size lower bounds for several models of quantum finite automata in the literature.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
478.53 kB
Formato
Adobe PDF
|
478.53 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.