44 Cezar Campeanu,Nicolae Santean,and Sheng Yu L.Thus,cover automata can be used to reduce the size of automata for finite languages in practice. Intuitively,a finite automaton that accepts a finite language (exactly)can be viewed as having structures for the following two functionalities: 1.checking the patterns of the words in the language,and 2.controlling the lengths of the words. In a high-level programming language environment,the length-control function is much easier to implement by counting with an integer than by using the structures of an automaton.Furthermore,the system usually does the length- counting anyway.Therefore,a DFA accepting a finite language may leave out the structures for the length-control function and,thus,reduce its complexity. The concept of cover automata is not totally new.Similar concepts have been studied in different contexts and for different purposes.See,for example, [1,7,4,10.Most of previous work has been in the study of a descriptive complexity measure of arbitrary languages,which is called "automaticity"by Shallit et al. [10.In our study,we consider cover automata as an implementing method that may reduce the size of the automata that represent finite languages. In this paper,as our main result,we give an efficient algorithm that,for a given finite language (given as a deterministic finite automaton or a cover automaton),constructs a minimal cover automaton for the language.Note that for a given finite language,there might be several minimal cover automata that are not equivalent under a morphism.We will show that,however,they all have the same number of states. 2 Preliminaries Let T be a set.Then by #T we mean the cardinality of T.The elements of T* are called strings or words.The empty string is denoted by A.If w E T*then w is the length of z. We define Tl=wETI=1),TsI=UTi,and T<=Ti.We say =0 that x is a prefix of y,denoted rpy,if y=xz for some zT+.The relation p is a partial order on T*.If T ={t1,...,t}is an ordered set,k >0,the quasi-lexicographical order on T*,denoted <is defined by:x<y iff<ly orzl=ly and x=ztv,y=ztu,i<j,for some z,u,v∈T*and1≤i,j≤k. Denote x<y if x<y or =y. We say that x is a prefix of y,denoted xpy,if y=xz for some zET. A deterministic finite automaton (DFA)is a quintuple A=(,Q,qo,6,F), where and Q are finite nonempty sets,qo∈Q,FCQ and6:Q×D-→Q is the transition function.We can extend 6 from Qx to Qx by (s,)=s (s,aw)=(6(s,a),w). We usually denote 6 by 6.44 Cezar Cˆampeanu, Nicolae Sˆantean, and Sheng Yu L. Thus, cover automata can be used to reduce the size of automata for finite languages in practice. Intuitively, a finite automaton that accepts a finite language (exactly) can be viewed as having structures for the following two functionalities: 1. checking the patterns of the words in the language, and 2. controlling the lengths of the words. In a high-level programming language environment, the length-control function is much easier to implement by counting with an integer than by using the structures of an automaton. Furthermore, the system usually does the length￾counting anyway. Therefore, a DFA accepting a finite language may leave out the structures for the length-control function and, thus, reduce its complexity. The concept of cover automata is not totally new. Similar concepts have been studied in different contexts and for different purposes. See, for example, [1,7,4,10]. Most of previous work has been in the study of a descriptive complexity measure of arbitrary languages, which is called “automaticity” by Shallit et al. [10]. In our study, we consider cover automata as an implementing method that may reduce the size of the automata that represent finite languages. In this paper, as our main result, we give an efficient algorithm that, for a given finite language (given as a deterministic finite automaton or a cover automaton), constructs a minimal cover automaton for the language. Note that for a given finite language, there might be several minimal cover automata that are not equivalent under a morphism. We will show that, however, they all have the same number of states. 2 Preliminaries Let T be a set. Then by #T we mean the cardinality of T . The elements of T ∗ are called strings or words. The empty string is denoted by λ. If w ∈ T ∗ then |w| is the length of x. We define T l = {w ∈ T ∗ | |w| = l}, T ≤l = [ l i=0 T i , and T <l = l [−1 i=0 T i . We say that x is a prefix of y, denoted x p y, if y = xz for some z ∈ T ∗.The relation p is a partial order on T ∗. If T = {t1,... ,tk} is an ordered set, k > 0, the quasi-lexicographical order on T ∗, denoted ≺, is defined by: x ≺ y iff |x| < |y| or |x| = |y| and x = ztiv, y = ztju, i<j, for some z, u, v ∈ T ∗ and 1 ≤ i, j ≤ k. Denote x  y if x ≺ y or x = y. We say that x is a prefix of y, denoted x p y, if y = xz for some z ∈ T . A deterministic finite automaton (DFA) is a quintuple A = (Σ, Q, q0, δ, F), where Σ and Q are finite nonempty sets, q0 ∈ Q, F ⊆ Q and δ : Q × Σ −→ Q is the transition function. We can extend δ from Q × Σ to Q × Σ∗ by δ(s, λ) = s δ(s, aw) = δ(δ(s, a), w). We usually denote δ by δ