
CEZAR CAMPEANU, ANDREI PAUN. COUNTING THE NUMBER OF MINIMAL DFCA OBTAINED BY MERGING STATES. International Journal of Foundations of Computer Science, 14, No. 6, pp. 9951006, 2003.
Abstract:
Finite Deterministic Cover Automata (DFCA) can be obtained from Deterministic Finite Automata (DFA) using the similarity relation and a method of merging similar states. The DFCA minimization procedure can yield different results depending on the order of merging the similar states, because the minimal DFCA for a finite language is in general not unique.
We count the number of minimal DFCA that can be obtained from a given minimal DFA with n states by merging the similar states in the given DFA. We compute an upperbound for this number and prove that in the worst case, it is n1 for an unary alphabet, and for a nonunary alphabet. We prove that this upperbound is reached, i.e., for any given positive integer n one can construct a minimal DFA with n states, which has the number of minimal DFCA obtained by merging similar states equal to this maximum expression.
Keywords:
Finite languages; Deterministic Finite Automata; Cover Language; Deterministic Cover Automata; Minimization
URL:
http://www.worldscinet.com/ijfcs/14/1406/S0129054103002138.html
Posted by
Cezar Campeanu
Back
