ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED

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

Autores

Marco Almeida (Autor) Outra; Nelma Moreira (Autor) FCUP; Rogerio Reis (Autor) FCUP

Revista

Título: International Journal of Foundations of Computer Science

Vol. 20

Páginas: 669-684

ISSN: 0129-0541

Editora: World Scientific

Indexação

ISI Web of Knowledge - 6 Citações

Scopus - 2 Citações

Classificação Científica

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

Outras Informações

ID Authenticus: P-003-H2V

DOI: 10.1142/s0129054109006802

Abstract (EN): Antimirov and Mosses proposed a rewrite system for deciding the equivalence of two (extended) regular expressions. They argued that this method could lead to a better average-case algorithm than those based on the comparison of the equivalent minimal deterministic finite automata. In this paper we present a functional approach to that method, prove its correctness, and give some experimental comparative results. Besides an improved functional version of Antimirov and Mosses's algorithm, we present an alternative one using partial derivatives. Our preliminary results lead to the conclusion that, indeed, these methods are feasible and, most of the time, faster than the classical methods.

Idioma: Inglês

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

Nº de páginas: 16