Incremental construction of minimal deterministic finite cover automata |
| |
| Authors: | Cezar Câ mpeanu,Andrei Păun,Jason R. Smith |
| |
| Affiliation: | 1. Department of Computer Science and Information Technology, University of Prince Edward Island, Charlottetown, P.E.I., Canada C1A 4P3;2. Department of Computer Science/Institute for Micromanufacturing, College of Engineering and Science, Louisiana Tech University, Ruston, P.O. Box 10348, Louisiana, LA-71272 USA |
| |
| Abstract: | We present a fast incremental algorithm for constructing minimal Deterministic Finite Cover Automata (DFCA) for a given language. Since it was shown that the minimal DFCA for a language L has less states than the minimal Deterministic Finite Automata (DFA) for the same language L, this technique seems to be the best choice for incrementally building the automaton for a large language, especially when the number of states in the DFCA is significantly less than the number of states in the corresponding minimal DFA. We have implemented the proposed algorithm and have tested it against the best-known DFCA minimization technique. |
| |
| Keywords: | Deterministic Finite Cover Automata (DFCA) DFA DFCA minimization Incremental construction |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
