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) Cezar Campeanu, Andrei 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: 260

Adding this citation to "My List" will allow you to export this citation in other styles.