Campeanu, C., & Paun, A. (2005). Tight bounds for NFA to DFCA transformations for binary alphabets. In Implementation and application of automata (pp. 306-307). Springer Verlag.

Details

Title

Tight bounds for NFA to DFCA transformations for binary alphabets

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 Show moreIn 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. Show less