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

• Ano de defesa: 2008
• Autor(a) principal: ISIDRO, Cheyenne Ribeiro Guedes.
• 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
• Palavras-chave em Português: Teoria da Computação; Computação Quântica; Expressão Regular; Autômato Finito; Computer Theory; Quantum Computation; Regular Expression; Finite Automaton; Ciência da Computação
• Link de acesso: http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/10572

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.