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
Start page 67
End page 76
Date 2003
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.

[Page generation failure. The bibliography processor requires a browser with Javascript enabled.]

Times viewed: 313

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