Tight bounds for NFA to DFCA transformations for ...
Description
Citation
| Section title | Tight bounds for NFA to DFCA transformations for binary alphabets |
| Section author(s) | C. Campeanu, A. Paun |
| Book title | Implementation and application of automata |
| Start page | 306 |
| End page | 307 |
| Date | 2005 |
| Abstract | In this paper we prove a lower bound for the maximum state complexity of Deterministic Finite Cover Automata (DFCAs) obtained from Non-deterministic Finite Automata (NFAs) of a given state complexity n, in case of a binary alphabet. We show, for binary alphabets, that the difference between maximum blow-up state complexity of DFA and DFCA can be as small as 2([n/2]-2) compared to the number of states of the minimal DFA. We conjecture that the lower bound given in the paper is also the upper bound. |
Using APA 6th Edition citation style.
[Page generation failure. The bibliography processor requires a browser with Javascript enabled.]
Times viewed: 78
