Name
Abstract | ||
|---|---|---|
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 automaton, 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.4204/EPTCS.3.4 | ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE |
Keywords | Field | DocType |
finite automata,regular expression,regular language,non deterministic finite automata,formal language,automata theory,deterministic finite automata,deterministic finite automaton | Discrete mathematics,Quantum finite automata,Two-way deterministic finite automaton,Deterministic automaton,Nondeterministic finite automaton,Deterministic finite automaton,DFA minimization,Mathematics,Probabilistic automaton,Büchi automaton | Journal |
Volume | Issue | ISSN |
3 | 3 | 2075-2180 |
Citations | PageRank | References |
2 | 0.37 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marco Almeida | 1 | 31 | 3.99 |
| Nelma Moreira | 2 | 180 | 33.98 |
| Rogério Reis | 3 | 140 | 25.74 |