Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10216/94982
Autor(es): | Marco Almeida Nelma Moreira Rogério Reis |
Título: | Testing equivalence of regular languages |
Data de publicação: | 2010 |
Resumo: | The minimal deterministic finite automaton is generally used to determine regular languages equality. Using Brzozowski's notion of derivative, Antimirov and Mosses proposed a rewrite system for deciding regular expressions equivalence of which Almeida et al. presented an improved variant. Hopcroft and Karp proposed an almost linear algorithm for testing the equivalence of two deterministic finite automata that avoids minimisation. In this paper we improve this algorithm's best-case running time, present an extension to non-deterministic finite automata, and establish a relationship with the one proposed in Almeida et al., for which we also exhibit an exponential lower bound. We also present some experimental comparative results. |
Assunto: | Ciência de computadores, Ciências da computação e da informação Computer science, Computer and information sciences |
Áreas do conhecimento: | Ciências exactas e naturais::Ciências da computação e da informação Natural sciences::Computer and information sciences |
URI: | https://repositorio-aberto.up.pt/handle/10216/94982 |
Tipo de Documento: | Artigo em Revista Científica Internacional |
Condições de Acesso: | restrictedAccess |
Aparece nas coleções: | FCUP - Artigo em Revista Científica Internacional |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
49294.pdf Restricted Access | Artigo | 247.84 kB | Adobe PDF | Request a copy from the Author(s) |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.