Tight bounds for NFA to DFCA transformations for ...
|Section title||Tight bounds for NFA to DFCA transformations for binary alphabets|
|Section author(s)||Cezar Campeanu, Andrei Paun|
|Book title||Implementation and application of automata|
|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.
Times viewed: 249