Zobrazeno 1 - 10
of 39 441
pro vyhledávání: '"finite automata"'
Autor:
Petrov, Semyon, Okhotin, Alexander
This paper establishes a lower bound on the number of states necessary in the worst case to simulate an $n$-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every $n$, there
Externí odkaz:
http://arxiv.org/abs/2412.06283
Quantum fingerprinting is a technique that maps classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses less resources, making it useful in quantum algorithms, communication,
Externí odkaz:
http://arxiv.org/abs/2412.18823
Autor:
Giliberti, Jeff, Harris, David G.
One main genre of algorithmic derandomization comes from the construction of probability distributions with small support that fool a randomized algorithm. This is especially well-suited to parallelization, i.e. NC algorithms. A significant abstracti
Externí odkaz:
http://arxiv.org/abs/2411.18028