The number of similarity relations and the number of ...
|Section title||The number of similarity relations and the number of minimal deterministic finite cover automata|
|Section author(s)||Cezar Campeanu, Andrei Paun|
|Book title||Implementation and application of automata|
|Abstract||Finite Deterministic Cover Automata (DFCA) can be obtained from Deterministic Finite Automata (DFA) using the similarity relation-Since the similarity relation is not an equivalence relation, the minimal DFCA for a finite language is usually not unique. We count the number of minimal DFCA that can be obtained from a given mini-mal 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 (for a non-unary alphabet) it is [GRAPHICS] We prove that this upper bound is reached, i.e. for any given positive integer n we find a minimal DFA with n states, which has the number of minimal DFCA obtained by merging similar states equal to this maximum.|
Using APA 6th Edition citation style.
Times viewed: 155