1,721,052 research outputs found
Some formal methods for analyzing quantum automata
No full textWe survey some formal methods useful in the analysis of (measure-once) 1-way quantum automata (lqfa's). We settle isolated cut point Rabin's theorem in the context of compact monoids; this explains why languages accepted with isolated cut point by several lqfa's models are regular. We recall a nice method in quantum automata theory pointed out by Blondel et al. [9] based on compact groups theory. As an application, we show that it is decidable to test whether two languages accepted by lqfa's are disjoint. Then we discuss some problems on quantum descriptional complexity. In the unary case, we give an exponential time algorithm for computing the descriptional complexity of periodic languages and we present a probabilistic method to construct lqfa's exponentially succinct in the period
Behaviours of Unary Quantum Automata
No full textWe study the stochastic events induced by MM-qfa's working on unary alphabets. We give two algorithms for unary MM-qfa's: the first computes the dimension of the ergodic and transient components of the non halting subspace, while the second tests whether the induced event is d-periodic. These algorithms run in polynomial time whenever the MM-qfa given in input has complex amplitudes with rational components. We also characterize the recognition power of unary MM-qfa's, by proving that any unary regular language can be accepted by a MM-qfa with constant cut point and isolation. Yet, the amount of states of the resulting MM-qfa is linear in the size of the corresponding minimal dfa. We also single out families of unary regular languages for which the size of the accepting MM-qfa's can be exponentially decreased
The parallel complexity of deterministic and probabilistic automata
No full textA deterministic (probabilistic) automaton is said to be in TC0 whenever its transitions (stochastic event) can be computed by threshold circuits of polynomial size and constant depth. Here, we prove that: The class of deterministic automata in TC0 is closed under homomorphism, sub-automaton, and alpha0-product operations. The class of k-state deterministic (probabilistic) automata is contained in TC0 if and only if k les 4 (k les 2), unless TC0 = NC1. Moreover, the possibility of ranking regular languages in TC0 is related to the group-structure of their syntactic monoid
A regularity condition for context-free grammars
No full textWe define a complexity measure on context-free grammars called end. Roughly speaking, for a context-free grammar G, endG(n) measures the distance of variables from the ends of sentential forms along the derivations of words in L(G) of length n. We prove in a constructive way the regularity of L(G) whenever endG(n) is constant. Yet, we improve on this by showing that if L(G) is nonregular then endG(n) = Ω∞(log n). Finally, the optimality of such a lower bound is established
Events and Languages on Unary Quantum Automata
No full textWe prove that any unary regular language can be accepted with constant cut point and isolation by a MM-qfa with an amount of states which is linear in the size of the corresponding dfa. This gives a characterization of the recognition power of unary MM-qfa’s. We also single out families of unary languages for which the size of the accepting MM-qfa’s can be exponentially decreased. Then, we give an algorithm for testing the d-periodicity of the events induced by unary MM-qfa’s. Finally, we show how to compute the dimension of the “ergodic” and “transient” subspaces of unary MM-qfa’s. These algorithms run in polynomial time on unary MM-qfa’s having complex amplitudes with rational components
On leftmost = rewriting systems
No full textWe introduce and study the leftmost variant of the - rewriting systems (RS's) [10]. We first show that any leftmost RS generates a context- free language. Then, we exhibit a context-free language which can be generated by a RS, but cannot be generated by any leftmost RS. On the other hand, we prove that by restricting to letter bounded languages leftmost RS's exactly describe context-free languages. Moreover, we investigate the generative power of finite index vs. infinite index leftmost RS
Size lower bounds for quantum automata
No full textWe compare the descriptional power of quantum finite automata with control language (QFCS) and deterministic finite automata (DFAS). By suitably adapting Rabin's technique, we show how to convert any given qfc to an equivalent dfa, incurring in an at most exponential size increase. This enables us to state a lower bound on the size of qfcs, which is logarithmic in the size of equivalent minimal dfas. In turn, this result yields analogous size lower bounds for several models of quantum finite automata in the literature
On the Power of One-Way Automata with Quantum and Classical States
No full textWe consider the model of one-way automata with quantum and classical states (QCFAs) introduced in [28]. We show, by a direct approach, that QCFAs with isolated cut-point accept regular languages only, thus characterizing their computational power. Concerning descriptional power, we quickly overview a size lower bound for QCFAs accepting regular languages, and address its optimality. Then, we explicitly build QCFAs accepting the word quotients and inverse homomorphic images of languages accepted by given QCFAs with isolated cut-point, maintaining the same cut-point, isolation, and only polynomially increasing the size
- …
