Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Theses and dissertations
Ad Astra association
Press releases
Funding opportunities
>> Românã

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. 995-1006, 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 upper-bound for this number and prove that in the worst case, it is n-1 for an unary alphabet, and for a non-unary alphabet. We prove that this upper-bound 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


Posted by Cezar Campeanu


© Ad Astra 2001-2013