Please use this identifier to cite or link to this item:
Author(s): Marco Almeida
Nelma Moreira
Rogério Reis
Title: Testing equivalence of regular languages
Issue Date: 2010
Abstract: 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.
Subject: Ciência de computadores, Ciências da computação e da informação
Computer science, Computer and information sciences
Scientific areas: Ciências exactas e naturais::Ciências da computação e da informação
Natural sciences::Computer and information sciences
Document Type: Artigo em Revista Científica Internacional
Rights: restrictedAccess
Appears in Collections:FCUP - Artigo em Revista Científica Internacional

Files in This Item:
File Description SizeFormat 
  Restricted Access
Artigo247.84 kBAdobe PDF    Request a copy from the Author(s)

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.