On promise problems and a great automata diversity
Along this paper, we give the basic concepts on automata theory and we introduce the way to accept or reject promise problems and decision problems, the last one through the notions of recognizability and solvability. Afterwards, we show some results concerning promise problems, oneof these is the f...
- Autores:
- Tipo de recurso:
- Trabajo de grado de pregrado
- Fecha de publicación:
- 2022
- Institución:
- Universidad Distrital Francisco José de Caldas
- Repositorio:
- RIUD: repositorio U. Distrital
- Idioma:
- spa
- OAI Identifier:
- oai:repository.udistrital.edu.co:11349/28864
- Acceso en línea:
- http://hdl.handle.net/11349/28864
- Palabra clave:
- Autómatas clásicos
Autómatas cuánticos
Problemas de promesa
Complejidad
Criptografía
Matemáticas - Tesis y disertaciones académicas
Criptografía
Teoría de las máquinas
Lingüística matemática
Notación matemática
Classic automata
Quantum automata
Promise problems
Complexity
Cryptography
- Rights
- License
- Atribución-NoComercial-SinDerivadas 4.0 Internacional
| Summary: | Along this paper, we give the basic concepts on automata theory and we introduce the way to accept or reject promise problems and decision problems, the last one through the notions of recognizability and solvability. Afterwards, we show some results concerning promise problems, oneof these is the fact that we can find an automaton recognized exactly by measure-once one-way quantum finite automata, but no deterministic automata can recognize it. Finally, we focus in some of the applications of promise problems and how these can be useful in different topics of computer science and complexity theory. |
|---|