Search results for "Finite-state machine"
showing 10 items of 97 documents
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.
Descriptional and Computational Complexity of the Circuit Representation of Finite Automata
2018
In this paper we continue to investigate the complexity of the circuit representation of DFA—BC-complexity. We compare it with nondeterministic state complexity, obtain upper and lower bounds which differ only by a factor of 4 for a Binary input alphabet. Also we prove that many simple operations (determining if a state is reachable or if an automaton is minimal) are PSPACE-complete for DFA given in circuit representation.
An Approximate Determinization Algorithm for Weighted Finite-State Automata
2001
Nondeterministic weighted finite-state automata are a key abstraction in automatic speech recognition systems. The efficiency of automatic speech recognition depends directly on the sizes of these automata and the degree of nondeterminism present, so recent research has studied ways to determinize and minimize them, using analogues of classical automata determinization and minimization. Although, as we describe here, determinization can in the worst case cause poly-exponential blowup in the number of states of a weighted finite-state automaton, in practice it is remarkably successful. In extensive experiments in automatic speech recognition systems, deterministic weighted finite-state autom…
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.
Transition Function Complexity of Finite Automata
2019
State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.
Ultrametric Algorithms and Automata
2015
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.
Quantum Real - Time Turing Machine
2001
The principles of quantum computation differ from the principles of classical computation very much. Quantum analogues to the basic constructions of the classical computation theory, such as Turing machine or finite 1-way and 2-ways automata, do not generalize deterministic ones. Their capabilities are incomparable. The aim of this paper is to introduce a quantum counterpart for real - time Turing machine. The recognition of a special kind of language, that can't be recognized by a deterministic real - time Turing machine, is shown.
Finite Automata with Advice Tapes
2013
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, and establish the relationships between this model and the previously studied ways of providing advice to finite automata.