We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa's which, in turn, are smaller than deterministic automata.
On the size of unary probabilistic and nondeterministic automata / M.P. Bianchi, C. Mereghetti, B.S. Palano, G. Pighizzini. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - 112:2-3(2011), pp. 119-135.
On the size of unary probabilistic and nondeterministic automata
M.P. BianchiPrimo
;C. Mereghetti
;B.S. PalanoPenultimo
;G. PighizziniUltimo
2011
Abstract
We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa's which, in turn, are smaller than deterministic automata.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
167.54 kB
Formato
Adobe PDF
|
167.54 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.