We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {Lm} of cyclic languages, where Lm = {akm|k ∈ N}. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language Lm with isolated cut point on one-way probabilistic finite automata is p1α1 + p2α2 + ⋯ + psαs, with p1α1p2α2 ⋯ psαs being the factorization of m. To prove this result, we give a general state lower bound for accepting unary languages with isolated cut point on the one-way probabilistic model. Moreover, we exhibit one-way quantum finite automata that, for any m, accept Lm with isolated cut point and only two states. These results are settled within a survey on unary automata aiming to compare the descriptional power of deterministic, nondeterministic, probabilistic and quantum paradigms.
Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata / C. Mereghetti, B.S. Palano, G. Pighizzini. - In: RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS. - ISSN 0988-3754. - 35:5(2001), pp. 477-490. ((Intervento presentato al 3. convegno International Workshop on Descriptional Complexity of Complexity of Automats, Grammars and Related Structure tenutosi a Wien nel 2001.
Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata
C. MereghettiPrimo
;B.S. PalanoSecondo
;G. PighizziniUltimo
2001
Abstract
We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {Lm} of cyclic languages, where Lm = {akm|k ∈ N}. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language Lm with isolated cut point on one-way probabilistic finite automata is p1α1 + p2α2 + ⋯ + psαs, with p1α1p2α2 ⋯ psαs being the factorization of m. To prove this result, we give a general state lower bound for accepting unary languages with isolated cut point on the one-way probabilistic model. Moreover, we exhibit one-way quantum finite automata that, for any m, accept Lm with isolated cut point and only two states. These results are settled within a survey on unary automata aiming to compare the descriptional power of deterministic, nondeterministic, probabilistic and quantum paradigms.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
189 kB
Formato
Adobe PDF
|
189 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.