Search results for "quantum finite automata"
showing 10 items of 73 documents
On the Size Complexity of Deterministic Frequency Automata
2013
Austinat, Diekert, Hertrampf, and Petersen [2] proved that every language L that is (m,n)-recognizable by a deterministic frequency automaton such that m > n/2 can be recognized by a deterministic finite automaton as well. First, the size of deterministic frequency automata and of deterministic finite automata recognizing the same language is compared. Then approximations of a language are considered, where a language L′ is called an approximation of a language L if L′ differs from L in only a finite number of strings. We prove that if a deterministic frequency automaton has k states and (m,n)-recognizes a language L, where m > n/2, then there is a language L′ approximating L such that L′ c…
Quantum counter automata
2011
The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide gene…
Unary Probabilistic and Quantum Automata on Promise Problems
2015
We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error QFAs are more powerful than PFAs. But, in contrary to the binary problems, the computational powers of Las-Vegas QFAs and bounded-error PFAs are equivalent to deterministic finite automata (DFAs). Lastly, we present a new family of unary promise problems with two parameters such that when fixing one parameter QFAs can be exponentially more succinct than PFAs and when fixing the other parameter PFAs can be exponentially more succinct than DFAs.
Shrinking language models by robust approximation
2002
We study the problem of reducing the size of a language model while preserving recognition performance (accuracy and speed). A successful approach has been to represent language models by weighted finite-state automata (WFAs). Analogues of classical automata determinization and minimization algorithms then provide a general method to produce smaller but equivalent WFAs. We extend this approach by introducing the notion of approximate determinization. We provide an algorithm that, when applied to language models for the North American Business task, achieves 25-35% size reduction compared to previous techniques, with negligible effects on recognition time and accuracy.
Quantum Computers and Quantum Automata
2000
Quantum computation is a most challenging project involving research both by physicists and computer scientists. The principles of quantum computation differ from the principles of classical computation very much. When quantum computers become available, the public-key cryptography will change radically. It is no exaggeration to assert that building a quantum computer means building a universal code-breaking machine. Quantum finite automata are expected to appear much sooner. They do not generalize deterministic finite automata. Their capabilities are incomparable.
Quantum versus Probabilistic One-Way Finite Automata with Counter
2001
The paper adds the one-counter one-way finite automaton [6] to the list of classical computing devices having quantum counterparts more powerful in some cases. Specifically, two languages are considered, the first is not recognizable by deterministic one-counter one-way finite automata, the second is not recognizable with bounded error by probabilistic one-counter one-way finite automata, but each recognizable with bounded error by a quantum one-counter one-way finite automaton. This result contrasts the case of one-way finite automata without counter, where it is known [5] that the quantum device is actually less powerful than its classical counterpart.
Multiple Usage of Random Bits in Finite Automata
2012
Finite automata with random bits written on a separate 2-way readable tape can recognize languages not recognizable by probabilistic finite automata. This shows that repeated reading of random bits by finite automata can have big advantages over one-time reading of random bits.
Tally languages accepted by Monte Carlo pushdown automata
1997
Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.
Local automata and completion
1993
The problem of completing a finite automata preserving its properties is here investigated in the case of deterministic local automata. We show a decision procedure and give an algorithm which complete a deterministic local automaton (if the completion exists) with another one, having the same number of states.
Ultrametric Finite Automata and Turing Machines
2013
We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.