Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1010.68068
Mereghetti, Carlo; Palano, Beatrice; Pighizzini, Giovanni
Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata. (English)
[J] Theor. Inform. Appl. 35, No.5, 477-490 (2001). ISSN 0988-3754; ISSN 1290-385X/e

Summary: We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family $\{L_m\}$ of cyclic languages, where $L_m= \{a^{km} \mid k\in \bbfN\}$. In particular, we show that, for any $m$, the number of states necessary and sufficient for accepting the unary language $L_m$ with isolated cut point on one-way probabilistic finite automata is $p_1^{\alpha_1} +p_2^{\alpha_s}+\cdots+p_s^{\alpha_s}$, with $p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_s^{\alpha_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 $L_m$ 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.

MSC 2000:: *68Q10 Modes of computation
68Q19 Descriptive complexity and finite models
68Q45 Formal languages

Keywords: unary automata; cyclic languages

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]