Advanced Search

We show that, for any stochastic event $p$ of period $n$, there exists a measure-once one-way quantum finite automaton (1qfa) with at most $2\sqrt{6n}+25$ states inducing the event $ap+b$, for constants $a\>0$, $b\ge 0$, satisfying $a+b\le 1$. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period $n$ can be accepted with isolated cut point by a 1qfa with no more than $2\sqrt{6n}+26$ states. Our results give added evidence of the strength of measure-once...

We show that, for any stochastic event of period , there exists a with at most $2\sqrt{6n}+25$ states inducing the event , for constants , ≥ 0, satisfying + ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period can be accepted with isolated cut point by a 1qfa with no more than $2\sqrt{6n}+26$ states. Our results give added evidence of the strength of measure-once 1qfa's with respect to classical automata.

The complexity of computing, via threshold circuits, the and of fixed-dimension $k\times k$ matrices with integer or rational entries is studied. We call these two problems ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ and ${\mathrm{𝖬𝖯𝖮𝖶}}_{𝗄}$, respectively, for short. We prove that: (i) For $k\ge 2$, ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ does not belong to ${\mathrm{TC}}^0$, unless ${\mathrm{TC}}^0={\mathrm{NC}}^1$.newline (ii) For : ${\mathrm{𝖨𝖬𝖯}}_{\mathsf{2}}$ belongs to ${\mathrm{TC}}^0$ while, for $k\ge 3$, ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ does not belong to ${\mathrm{TC}}^0$, unless ${\mathrm{TC}}^0={\mathrm{NC}}^1$. (iii) For any , ${\mathrm{𝖬𝖯𝖮𝖶}}_{𝗄}$ belongs to ${\mathrm{TC}}^0$.

Bertoni  introduced in (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called . This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular...

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family $\left\{L_m\right\}$ of cyclic languages, where $L_m=\left\{a^{km}\right|k\in \mathbb{N}\}$. 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 }_2}+\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...

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {} of cyclic languages, where = | ∈ . In particular, we show that, for any , the number of states necessary and sufficient for accepting the unary language with isolated cut point on one-way probabilistic finite automata is $p_1^{{\alpha }_1}+p_2^{{\alpha }_2}+\cdots +p_s^{{\alpha }_s}$, with $p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$ being the factorization of . To prove this result, we give a Moreover, we exhibit one-way quantum finite automata...