1,720,975 research outputs found
Threshold circuits for some matrix operations : consequences on regular and probabilistic languages
No full textGolomb rulers and difference sets for succinct quantum automata
No full textGiven a function p : N → [0,1] of period n, we study the minimal size (number of states) of a one-way quantum finite automaton (Iqfa) inducing the stochastic event ap + b, for real constants a>0, b≥0, a+b≤1. First of all, we relate the estimation of the minimal size to the problem of finding a minimal difference cover for a suitable subset of Zn. Then, by observing that the cardinality of a difference cover Δ for a set A Z n, must satisfy , we investigate the class of sets A admitting difference covers of cardinality exactly . We relate this problem with the efficient construction of Golomb rulers and difference sets. We design an algorithm which outputs each of the Golomb rulers (if any) of a given set in pseudo-polynomial time. As a consequence, we obtain an efficient algorithm that construct minimal difference covers for a non-trivial class of sets. Moreover, by using projective geometry arguments, we give an algorithm that, for any n=q2+q+1 with q prime power, constructs difference sets for Z n in quadratic time
Quantum finite automata : advances on Bertoni's ideas
No full textWe first outline main steps and achievements along Bertoni's research path in quantum finite automata theory - from the very basic definitions of the models of quantum finite automata throughout the investigation of their computational and descriptional power. Next, we choose to focus on Bertoni's studies on quantum finite automata descriptional complexity. In particular, we expand on a statistical framework for the synthesis of succinct quantum finite automata, discussing its adaptation to the case of multiperiodic events and languages. We then improve such a framework to obtain even more succinct quantum finite automata for some multiperiodic languages. Finally, we introduce some promise problems for multiperiodic inputs, showing that even on this class of problems the descriptional power of quantum finite automata greatly outperforms that of equivalent classical finite automata
The complexity of minimum difference cover
No full textAbstractThe complexity of searching minimum difference covers, both in Z+ and in Zn, is studied. We prove that these two optimization problems are NP-hard. To obtain this result, we characterize those sets—called extrema—having themselves plus zero as minimum difference cover. Such a combinatorial characterization enables us to show that testing whether sets are not extrema, both in Z+ and in Zn, is NP-complete. However, for these two decision problems we exhibit pseudo-polynomial time algorithms
Threshold circuits for iterated matrix product and powering
Full text linkThe complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension k×k matrices with integer or rational entries is studied. We call these two problems IMPk and MPOWk, respectively, for short. We prove that: (i) For k≥2, IMPk does not belong to TC0, unless TC0 = NC1. (ii) For stochastic matrices: IMP2 belongs to TC0 while, for k≥3, IMPk does not belong to TC0, unless TC0 = NC1. (iii) For any k, MPOWk belongs to TC0
On the size of one-way quantum finite automata with periodic behaviors
Full text linkWe 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√6n + 25 states inducing the event ap + b, for constants a > 0, b ≥ 0, satisfying a + b ≤ 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√6n + 26 states. Our results give added evidence of the strength of measure-once 1qfa's with respect to classical automata
On the size of unary probabilistic and nondeterministic automata
No full textWe 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
Logical description of structured and XML languages
No full textWe study first order logic definitions of structured and XML languages. We prove that bounded semilinear languages can be defined by formulas in FO[+]. Then, we exhibit meaningful classes of XML languages definable by FOC[+] formulas, and hence parsable in TC0.
Quantum automata for some multiperiodic languages
No full textAbstractWe exhibit small size measure-once one-way quantum finite automata (mo-1qfa’s) inducing multiperiodic stochastic events. Moreover, for certain classes of multiperiodic languages, we exhibit: (i) isolated cut point mo-1qfa’s whose size logarithmically depends on the periods; (ii) Monte Carlo mo-1qfa’s whose size logarithmically depends on the periods and polynomially on the inverse of the error probability
First-order logics : some characterizations and closure properties
No full textThe characterization of the class of FO[+]-definable languages by some generat- ing or recognizing device is still an open problem. We prove that, restricted to word bounded languages, this class coincides with the class of semilinear languages. We also study the clo- sure properties of the classes of languages definable in FO[+1], FO[<], FO[+] and FOC[+] under the main classical operations
- …
