Uma abordagem quântica para o uso de expressões regulares.

Detalhes bibliográficos
Ano de defesa: 2008
Autor(a) principal: ISIDRO, Cheyenne Ribeiro Guedes.
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Campina Grande
Brasil
Centro de Engenharia Elétrica e Informática - CEEI
PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
UFCG
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/10572
Resumo: As expressões regulares (ER) são conceitos abstratos da Teoria da Computação amplamente utilizados nas tarefas de processamento de texto e casamento de padrão que são aplicadas em diversas áreas, tais como, biologia computacional, processamento de sinais, recuperação de textos, reconhecimento de escrita a mão, reconhecimento de padrões, entre outras. As abordagens clássicas existentes para sua utilização possuem duas fases: i) a transformação da expressão regular em autômato finito, determinístico (AFD) ou não-determinístico (AFN); e ii) a implementação (codificação e simulação) do autômato em hardware clássico. No entanto, essas abordagens são ineficientes na execução de uma de suas fases, seja em relação ao tempo ou ao espaço utilizados. Este trabalho propõe uma abordagem quântica alternativa às abordagens clássicas para o uso de expressões regulares. Na abordagem proposta, a fase de transformação é dividida em duas: a transformação ER-AFN clássica é mantida e introduzse a transformação do AFN em um autômato finito quântico (AFQ) através da aplicação do algoritmo desenvolvido e apresentado neste trabalho. Esse algoritmo utiliza um modelo de AFQ que reconhece a classe das linguagens regulares (AFQ Ancilla). A transformação é feita em tempo polinomial e preserva o número de estados do AFN, eliminando tanto a ineficiência no uso da memória que resultava da transformação clássica AFN-AFD, quanto a posterior necessidade de minimização. Para a fase de implementação do autômato, é proposto um arcabouço para descrever um autômato finito quântico através da linguagem de circuitos quânticos, utilizando um número de portas polinomialmente proporcional à quantidade de estados do autômato e ao tamanho da palavra de entrada. Assim, a abordagem quântica é computacionalmente eficiente pois ambas as fases possuem complexidade polinomial, tanto de tempo quanto de espaço.