Testing equivalence of regular languages

• Tipo: Artigo em Revista Científica Internacional
• Data: 2010

Autores

Marco Almeida (Autor) FCUP; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Revista

Título: Journal of Automata, Languages and Combinatorics

ISSN: 1430-189X

Editora: Institut fur Informatik, Justus-Liebig-Universitat Giessen

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

CORDIS: Ciências Físicas > Ciência de computadores

Outras Informações

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Notas: Accepted to publication. - 2010.