Autori: CEZAR CÂMPEANU, ANDREI PÃUN

Editorial: World Scientific Publishing Company, International Journal of Foundations of Computer Science, 14, No. 6, p.995-1006, 2003.

Rezumat:

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.

Cuvinte cheie: Finite languages; Deterministic Finite Automata; Cover Language; Deterministic Cover Automata; Minimization

URL: http://www.worldscinet.com/ijfcs/14/1406/S0129054103002138.html