Testing equivalence of regular languages

• Type: Article in International Scientific Journal
• Date: 2010

Authors

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

Journal

Title: Journal of Automata, Languages and Combinatorics

ISSN: 1430-189X

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

Scientific classification

FOS: Natural sciences > Computer and information sciences

CORDIS: Physical sciences > Computer science

Other information

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.

Language: English

Type (Professor's evaluation): Scientific

Notes: Accepted to publication. - 2010.