Testing the Equivalence of Regular Languages

Details Testing the Equivalence of Regular Languages Testing the Equivalence of Regular Languages

2009-07-29

arxiv.org/abs/0907.5058v1

EPTCS 3, 2009, pp. 47-57

Computer Science

Formal Languages and Automata Theory

Scientific paper

10.4204/EPTCS.3.4

The minimal deterministic finite automaton is generally used to determine regular languages equality. 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 the best-case running time, present an extension of this algorithm to non-deterministic finite automata, and establish a relationship between this algorithm and the one proposed in Almeida et al. We also present some experimental comparative results. All these algorithms are closely related with the recent coalgebraic approach to automata proposed by Rutten.

Affiliated with

Also associated with

No associations

Rating

Testing the Equivalence of Regular Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing the Equivalence of Regular Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing the Equivalence of Regular Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521376