幺半环上模糊自动机的研究与应用
|
摘要
模糊自动机是自动机研究领域的一个重要方向,它在自动控制、计算机科学等许多领域均有广泛的应用.目前人们主要基于代数拓扑、多值逻辑、剩余逻辑、模糊逻辑及格半群意义下来研究模糊自动机.本文主要采用代数的方法研究了模糊识别器与有穷自动机的等价性,幺半环上的模糊有限状态机在同态下的交换性质、连通性、分离性,幺半环上几类模糊自动机的关系以及幺半环上一类有限自动机的约简性.
本文分为六个部分,第一部分是引言,第二至第五部分中每一部分为一章,是本文的核心,最后部分是结束语.
引言部分主要介绍本文的研究背景、研究依据、理论来源和研究的意义以及本文的主要研究成果.
第一章针对模糊识别器与有穷自动机的关系,证明了当输入字母表相同时,任给一个模糊识别器,必然存在一个有穷自动机,使得模糊识别器的行为与有穷自动机所接受的语言相同;反之,任给一个有穷自动机,必然存在一个模糊识别器,使得有穷自动机所接受的语言与模糊识别器的行为相同,从而得出它们之间在识别语言功能上的等价性.主要结果有:
定理1.2.3设L ?Σ?,则下列陈述等价:
(ⅰ)L是正则语言;
(ⅱ)存在一个DFA A 1,使得A1 = L;
(ⅲ)存在一个NFA A 2,使得A2 = L;
(ⅳ)存在一个ε? NFAA 3,使得A3 = L;
(ⅴ)存在一个模糊Σ?识别器M ,使得M = L.
第二章给出了幺半环上模糊有限状态机的概念,对状态之间的等价进行了定义,引入了同态的概念,得到同态定理和满同态分解定理,讨论了幺半环上模糊有限状态机在同态下的交换性质和连通性以及子状态机的可分离性,主要结果有:
定理2.2.1(同态定理)设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,若(α,β): M→M'是一个满同态,则由满同态(α,β): M→M'可导出一个RFM M ,且M ? M'.
定理2.2.2(满同态分解定理)设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM , (α,β): M→M'是一个满同态,由α决定Q上的划分为πα,由β决定Σ上的划分为πβ,若π是Q上的一个划分且π≤πα,τ是Σ上的一个划分且τ≤πβ,则
(ⅰ)由π,τ导出一个RFM M '',且存在一个满同态(απ,βτ): M→M'';
(ⅱ)存在满同态(λ,μ): M ''→M',使下面的同态图表(图2-1)交换.
定理2.2.3设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,若(α,β): M→M'是一个满同态,则M满足交换性质的充分必要条件是M '满足交换性质.
定理2.2.4设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,若(α,β): M→M'是一个满同态,且Q ' > 1,则M是强连通的充分必要条件是M '是强连通的.
定理2.2.6设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,则:
(ⅰ)若(α,β): M→M'是一个满同态,且N = (T ,Σ,η)是M的一个可分离的子状态机,则( )N ' =α(T ),Σ',δ'α( T)是M '的可分离的子状态机.
(ⅱ)若(α,β): M→M'是一个同态, N ' = (T ',Σ',η)是M '的一个可分离的子状态机,且α?1 (T ')≠?,则( )11Nα(T '), ,δα( T')?= ?Σ是M的可分离的子状态机.
定理2.2.7设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,且(α,β): M→M'是一个满同态,若M是连通的,则M '也是连通的;反之不一定成立.
第三章给出了幺半环上四类非确定的模糊自动机和四类确定的模糊自动机及其语言的定义,证明了幺半环上前三类非确定的模糊自动机间的等价性和前三类确定的模糊自动机间的等价性,讨论了幺半环上前三类非确定的模糊自动机和第四类非确定的模糊自动机之间的关系,以及幺半环上非确定的模糊自动机和确定的模糊自动机之间的关系.主要结果有:
定理3.2.1对Σ上的一个R?语言f ,下列陈述等价:
(ⅰ) f能被一个NRA? 1接受;
(ⅱ) f能被一个NRA? 2接受;
(ⅲ) f能被一个NRA? 3接受.
定理3.2.2设Σ是一个非空有限集合,R是一个幺半环,对Σ上的一个R?语言f ,如果f能被一个NRA? 4所接受,则它也能被一个NRA? 1接受;反之,如果f能被一个NRA?1所接受,则存在一个NRA? 4M 4,使得?x≠ε,4f M( x ) = f ( x).
定理3.3.1对Σ上的一个R?语言f ,下列陈述等价:
(ⅰ) f能被一个DRA? 1接受;
(ⅱ) f能被一个DRA? 2接受;
(ⅲ) f能被一个DRA? 3接受.
定理3.4.1设f是Σ上的一个R?语言,若f能被一个DRA接受,则f也能被一个NRA接受,但反之不一定成立.
第四章给出了幺半环上确定型有限状态自动机的状态的等价定义,对幺半环上确定型有限状态自动机的约简性进行了讨论,并给出了一个算法.主要结果有:
定理4.2.2设M = (Q ,Σ,δ,σ0 ,σ1)是一个DRSA,则必然存在一个约简的DRSA与M等价.
最后部分为结束语,总结了本文的主要工作,阐述了与本文相关研究的一些课题,并对下一步的继续研究工作做了设想.
Fuzzy automata is an important direction in the research field of automata, it is widely used in the fields such as automatic control technology and computer sciences etc. In the present, people study fuzzy automata by the methods based on algebraic topology, multi-valued logic, remaining logic, fuzzy logic and under the sence of lattice-monoid. In the paper, equivalence between fuzzy recognizers and finite automata, the exchange property, connectivity and separability under the homomorphism between two fuzzy finite state machines over unitary semirings, relationships among several types of fuzzy automata over unitary semirings, and reduction of fuzzy finite-state automata over unitary semirings are studied through applying algebraic methods.
This paper is composed of six parts. The first part is the introduction, the second to the fifth parts are the core of this paper.
Part I, i.e. Introduction, some of the research background, theory and research sources, the significance of this paper and the main results of the study are introduced.
Part II, i.e. Chapter one, the relationship of fuzzy recognizers and finite automata is discussed. When the same input alphabet is given, the conclusion is proved that given any fuzzy recognizer, inevitably there is a finite automata, the acceptable language of which is the same as the behavior of the fuzzy recognizer, and conversely, given any finite automata, there exists a fuzzy recognizer, the behavior of which is the same as the acceptable language of the finite automata. Thus, the equivalence on the function of language recognition between them is obtained. The main results are as following:
Theorem 1.2.3 Let L ?Σ?,then the following statements are equivalent:
(ⅰ) L is a regular language;
(ⅱ) There exists a deterministic finite automata (for short DFA) A 1, such that A1 = L;
(ⅲ) There exists a nondeterministic finite automata (for short NFA ) A 2, such that A2 = L;
(ⅳ) There exists a nondeterministic finite automata withε? move (for shortε? NFA) A 3, such that A3 = L;
(ⅴ) There exists a fuzzyΣ?recognizers M , such that M = L.
Part III, i.e. Chapter two, the concept of fuzzy finite state machines over unitary semirings is given, the statewise equivalence of fuzzy finite state machines over unitary semirings is defined, and the notion of homomorphism between two fuzzy finite state machines over unitary semirings is introduced. Homomorphism Theorem and Epimorphism Decomposition Theorem are obtained, and the exchange property, connectivity and separability of submachines of fuzzy finite state machines over unitary semirings under homomorphism are discussed. The main results are as following:
Theorem 2.2.1(Homomorphism Theorem)
Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two fuzzy finite state machines over unitary semirings (for short RFM ). If (α,β): M→M' is an epimorphism, then an RFM M is induced by the epimorphism (α,β): M→M' and such that M ? M'.
Theorem 2.2.2( Epimorphism Decomposition Theorem)
Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs and (α,β): M→M' an epimorphism. Suppose thatπαis the partition defined byαon Q ,πis a partition on Q satisfying the conditionπ≤πα,πβis the partition defined byβonΣand thatτis also a partition onΣsatisfying the conditionτ≤πβ,then
(ⅰ) an RFM M '' is induced byπandτ, and there exists an epimorphism (απ,βτ): M→M'';
(ⅱ) there exists an epimorphism (λ,μ): M ''→M' such that the following diagram of homomorphisms (Fig 2-1) is commutative:
Theorem 2.2.3 Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs . Suppose that (α,β): M→M' an epimorphism, then M satisfies the exchange property if and only if M ' satisfies the exchange property.
Theorem 2.2.4 Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs . Suppose that (α,β): M→M' is an epimorphism and Q ' > 1, then M is strongly connected iff M ' is strongly connected.
Theorem 2.2.6 Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs .
(ⅰ) Suppose that (α,β): M→M' is an epimorphism and N = (T ,Σ,η)is a separated submachine of M , then
N ' =α(T ),Σ',δ'α( T) is a separated submachine of M '.
(ⅱ) Suppose that (α,β): M→M' is a homomorphism, N ' = (T ',Σ',η) is a separated submachine of M ', andα?1 (T ')≠? , then ( )11Nα(T '), ,δα( T')?= ?Σis a separated submachine of M .
Theorem 2.2.7 Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs and (α,β) : M→M' an epimorphism. If M is connected, then M ' is also connected. Conversely, the conclusion is not true.
Part IV, i.e. Chapter three, the definitions of the four types of nondeterministic fuzzy automata and the four types of deterministic fuzzy automata over unitary semirings and their languages are given. The equivalence among the former three types of nondeterministic fuzzy automata and the equivalence among the former three types of deterministic fuzzy automata over unitary semirings are proved. The relationships between the fourth type of nondeterministic fuzzy automata over unitary semirings and the other former types nondeterministic fuzzy automata over unitary semirings are studied, and the relationships between nondeterministic fuzzy automata and deterministic fuzzy automata over unitary semirings are also discussed. The main results are as following:
Theorem 3.2.1 For an R ?language f onΣ, the following statements are equivalent:
(ⅰ) f can be accepted by a 1? type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 1);
(ⅱ) f can be accepted by a 2 ?type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 2);
(ⅲ) f can be accepted by a 3? type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 3).
Theorem 3.2.2 LetΣbe a nonempty finite set and R a unitary semirings. For an R ?language f onΣ, if it can be accepted by a 4?type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 4), then it can also be accepted by some NRA? 1.On the contrary, suppose that f can be accepted by a NRA? 1,then there exists some NRA? 4M4 such that 4f M( x ) = f ( x) for any x∈Σ+.
Theorem 3.3.1 For an R ?language f onΣ, the following statements are equivalent:
(ⅰ) f can be accepted by an 1? type of deterministic fuzzy automata over unitary semirings (for short DRA? 1);
(ⅱ) f can be accepted by a 2 ? type of deterministic fuzzy automata over unitary semirings (for short DRA? 2);
(ⅲ) f can be accepted by a 3? type of deterministic fuzzy automata over unitary semirings (for short DRA? 3).
Theorem 3.4.1 Let f be an R ?language onΣ. Suppose that f can be accepted by a DRA, then it can be also accepted by some NRA , but conversely, the conclusion is not true.
Part V, i.e. Chapter four, the notion of equivalence between two states of deterministic finite-state automata over unitary semirings is defined, reduction of the kind of automata is discussed, and a computing algorithm on reduction of the type of automata is given. The main result are as following:
Theorem 4.2.2 Let M = (Q ,Σ,δ,σ0 ,σ1) be a deterministic finite-state automata over unitary semirings (for short DRSA). Then there must exist a reductive DRSA such that it and M are equivalent.
Part VI is concluding remarks, the main work of this paper is summarized, some subjects corresponding to this paper are simply illustrated, and the idea to the next phase of work to continue to study is roughly envisaged.
本文分为六个部分,第一部分是引言,第二至第五部分中每一部分为一章,是本文的核心,最后部分是结束语.
引言部分主要介绍本文的研究背景、研究依据、理论来源和研究的意义以及本文的主要研究成果.
第一章针对模糊识别器与有穷自动机的关系,证明了当输入字母表相同时,任给一个模糊识别器,必然存在一个有穷自动机,使得模糊识别器的行为与有穷自动机所接受的语言相同;反之,任给一个有穷自动机,必然存在一个模糊识别器,使得有穷自动机所接受的语言与模糊识别器的行为相同,从而得出它们之间在识别语言功能上的等价性.主要结果有:
定理1.2.3设L ?Σ?,则下列陈述等价:
(ⅰ)L是正则语言;
(ⅱ)存在一个DFA A 1,使得A1 = L;
(ⅲ)存在一个NFA A 2,使得A2 = L;
(ⅳ)存在一个ε? NFAA 3,使得A3 = L;
(ⅴ)存在一个模糊Σ?识别器M ,使得M = L.
第二章给出了幺半环上模糊有限状态机的概念,对状态之间的等价进行了定义,引入了同态的概念,得到同态定理和满同态分解定理,讨论了幺半环上模糊有限状态机在同态下的交换性质和连通性以及子状态机的可分离性,主要结果有:
定理2.2.1(同态定理)设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,若(α,β): M→M'是一个满同态,则由满同态(α,β): M→M'可导出一个RFM M ,且M ? M'.
定理2.2.2(满同态分解定理)设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM , (α,β): M→M'是一个满同态,由α决定Q上的划分为πα,由β决定Σ上的划分为πβ,若π是Q上的一个划分且π≤πα,τ是Σ上的一个划分且τ≤πβ,则
(ⅰ)由π,τ导出一个RFM M '',且存在一个满同态(απ,βτ): M→M'';
(ⅱ)存在满同态(λ,μ): M ''→M',使下面的同态图表(图2-1)交换.
定理2.2.3设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,若(α,β): M→M'是一个满同态,则M满足交换性质的充分必要条件是M '满足交换性质.
定理2.2.4设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,若(α,β): M→M'是一个满同态,且Q ' > 1,则M是强连通的充分必要条件是M '是强连通的.
定理2.2.6设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,则:
(ⅰ)若(α,β): M→M'是一个满同态,且N = (T ,Σ,η)是M的一个可分离的子状态机,则( )N ' =α(T ),Σ',δ'α( T)是M '的可分离的子状态机.
(ⅱ)若(α,β): M→M'是一个同态, N ' = (T ',Σ',η)是M '的一个可分离的子状态机,且α?1 (T ')≠?,则( )11Nα(T '), ,δα( T')?= ?Σ是M的可分离的子状态机.
定理2.2.7设M = (Q ,Σ,δ), M ' = (Q ',Σ',δ')是RFM ,且(α,β): M→M'是一个满同态,若M是连通的,则M '也是连通的;反之不一定成立.
第三章给出了幺半环上四类非确定的模糊自动机和四类确定的模糊自动机及其语言的定义,证明了幺半环上前三类非确定的模糊自动机间的等价性和前三类确定的模糊自动机间的等价性,讨论了幺半环上前三类非确定的模糊自动机和第四类非确定的模糊自动机之间的关系,以及幺半环上非确定的模糊自动机和确定的模糊自动机之间的关系.主要结果有:
定理3.2.1对Σ上的一个R?语言f ,下列陈述等价:
(ⅰ) f能被一个NRA? 1接受;
(ⅱ) f能被一个NRA? 2接受;
(ⅲ) f能被一个NRA? 3接受.
定理3.2.2设Σ是一个非空有限集合,R是一个幺半环,对Σ上的一个R?语言f ,如果f能被一个NRA? 4所接受,则它也能被一个NRA? 1接受;反之,如果f能被一个NRA?1所接受,则存在一个NRA? 4M 4,使得?x≠ε,4f M( x ) = f ( x).
定理3.3.1对Σ上的一个R?语言f ,下列陈述等价:
(ⅰ) f能被一个DRA? 1接受;
(ⅱ) f能被一个DRA? 2接受;
(ⅲ) f能被一个DRA? 3接受.
定理3.4.1设f是Σ上的一个R?语言,若f能被一个DRA接受,则f也能被一个NRA接受,但反之不一定成立.
第四章给出了幺半环上确定型有限状态自动机的状态的等价定义,对幺半环上确定型有限状态自动机的约简性进行了讨论,并给出了一个算法.主要结果有:
定理4.2.2设M = (Q ,Σ,δ,σ0 ,σ1)是一个DRSA,则必然存在一个约简的DRSA与M等价.
最后部分为结束语,总结了本文的主要工作,阐述了与本文相关研究的一些课题,并对下一步的继续研究工作做了设想.
Fuzzy automata is an important direction in the research field of automata, it is widely used in the fields such as automatic control technology and computer sciences etc. In the present, people study fuzzy automata by the methods based on algebraic topology, multi-valued logic, remaining logic, fuzzy logic and under the sence of lattice-monoid. In the paper, equivalence between fuzzy recognizers and finite automata, the exchange property, connectivity and separability under the homomorphism between two fuzzy finite state machines over unitary semirings, relationships among several types of fuzzy automata over unitary semirings, and reduction of fuzzy finite-state automata over unitary semirings are studied through applying algebraic methods.
This paper is composed of six parts. The first part is the introduction, the second to the fifth parts are the core of this paper.
Part I, i.e. Introduction, some of the research background, theory and research sources, the significance of this paper and the main results of the study are introduced.
Part II, i.e. Chapter one, the relationship of fuzzy recognizers and finite automata is discussed. When the same input alphabet is given, the conclusion is proved that given any fuzzy recognizer, inevitably there is a finite automata, the acceptable language of which is the same as the behavior of the fuzzy recognizer, and conversely, given any finite automata, there exists a fuzzy recognizer, the behavior of which is the same as the acceptable language of the finite automata. Thus, the equivalence on the function of language recognition between them is obtained. The main results are as following:
Theorem 1.2.3 Let L ?Σ?,then the following statements are equivalent:
(ⅰ) L is a regular language;
(ⅱ) There exists a deterministic finite automata (for short DFA) A 1, such that A1 = L;
(ⅲ) There exists a nondeterministic finite automata (for short NFA ) A 2, such that A2 = L;
(ⅳ) There exists a nondeterministic finite automata withε? move (for shortε? NFA) A 3, such that A3 = L;
(ⅴ) There exists a fuzzyΣ?recognizers M , such that M = L.
Part III, i.e. Chapter two, the concept of fuzzy finite state machines over unitary semirings is given, the statewise equivalence of fuzzy finite state machines over unitary semirings is defined, and the notion of homomorphism between two fuzzy finite state machines over unitary semirings is introduced. Homomorphism Theorem and Epimorphism Decomposition Theorem are obtained, and the exchange property, connectivity and separability of submachines of fuzzy finite state machines over unitary semirings under homomorphism are discussed. The main results are as following:
Theorem 2.2.1(Homomorphism Theorem)
Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two fuzzy finite state machines over unitary semirings (for short RFM ). If (α,β): M→M' is an epimorphism, then an RFM M is induced by the epimorphism (α,β): M→M' and such that M ? M'.
Theorem 2.2.2( Epimorphism Decomposition Theorem)
Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs and (α,β): M→M' an epimorphism. Suppose thatπαis the partition defined byαon Q ,πis a partition on Q satisfying the conditionπ≤πα,πβis the partition defined byβonΣand thatτis also a partition onΣsatisfying the conditionτ≤πβ,then
(ⅰ) an RFM M '' is induced byπandτ, and there exists an epimorphism (απ,βτ): M→M'';
(ⅱ) there exists an epimorphism (λ,μ): M ''→M' such that the following diagram of homomorphisms (Fig 2-1) is commutative:
Theorem 2.2.3 Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs . Suppose that (α,β): M→M' an epimorphism, then M satisfies the exchange property if and only if M ' satisfies the exchange property.
Theorem 2.2.4 Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs . Suppose that (α,β): M→M' is an epimorphism and Q ' > 1, then M is strongly connected iff M ' is strongly connected.
Theorem 2.2.6 Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs .
(ⅰ) Suppose that (α,β): M→M' is an epimorphism and N = (T ,Σ,η)is a separated submachine of M , then
N ' =α(T ),Σ',δ'α( T) is a separated submachine of M '.
(ⅱ) Suppose that (α,β): M→M' is a homomorphism, N ' = (T ',Σ',η) is a separated submachine of M ', andα?1 (T ')≠? , then ( )11Nα(T '), ,δα( T')?= ?Σis a separated submachine of M .
Theorem 2.2.7 Let M = (Q ,Σ,δ) and M ' = (Q ',Σ',δ') be two RFMs and (α,β) : M→M' an epimorphism. If M is connected, then M ' is also connected. Conversely, the conclusion is not true.
Part IV, i.e. Chapter three, the definitions of the four types of nondeterministic fuzzy automata and the four types of deterministic fuzzy automata over unitary semirings and their languages are given. The equivalence among the former three types of nondeterministic fuzzy automata and the equivalence among the former three types of deterministic fuzzy automata over unitary semirings are proved. The relationships between the fourth type of nondeterministic fuzzy automata over unitary semirings and the other former types nondeterministic fuzzy automata over unitary semirings are studied, and the relationships between nondeterministic fuzzy automata and deterministic fuzzy automata over unitary semirings are also discussed. The main results are as following:
Theorem 3.2.1 For an R ?language f onΣ, the following statements are equivalent:
(ⅰ) f can be accepted by a 1? type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 1);
(ⅱ) f can be accepted by a 2 ?type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 2);
(ⅲ) f can be accepted by a 3? type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 3).
Theorem 3.2.2 LetΣbe a nonempty finite set and R a unitary semirings. For an R ?language f onΣ, if it can be accepted by a 4?type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 4), then it can also be accepted by some NRA? 1.On the contrary, suppose that f can be accepted by a NRA? 1,then there exists some NRA? 4M4 such that 4f M( x ) = f ( x) for any x∈Σ+.
Theorem 3.3.1 For an R ?language f onΣ, the following statements are equivalent:
(ⅰ) f can be accepted by an 1? type of deterministic fuzzy automata over unitary semirings (for short DRA? 1);
(ⅱ) f can be accepted by a 2 ? type of deterministic fuzzy automata over unitary semirings (for short DRA? 2);
(ⅲ) f can be accepted by a 3? type of deterministic fuzzy automata over unitary semirings (for short DRA? 3).
Theorem 3.4.1 Let f be an R ?language onΣ. Suppose that f can be accepted by a DRA, then it can be also accepted by some NRA , but conversely, the conclusion is not true.
Part V, i.e. Chapter four, the notion of equivalence between two states of deterministic finite-state automata over unitary semirings is defined, reduction of the kind of automata is discussed, and a computing algorithm on reduction of the type of automata is given. The main result are as following:
Theorem 4.2.2 Let M = (Q ,Σ,δ,σ0 ,σ1) be a deterministic finite-state automata over unitary semirings (for short DRSA). Then there must exist a reductive DRSA such that it and M are equivalent.
Part VI is concluding remarks, the main work of this paper is summarized, some subjects corresponding to this paper are simply illustrated, and the idea to the next phase of work to continue to study is roughly envisaged.
引文
[1]Wee W G. On generalizations of adaptive algorithm and application of the fuzzy sets concepts to pattern classification[D]. Purdue University, Westlafayette, Indiana, 1967.
[2]Wee W G, Fu K S. A formulation of fuzzy automata and its application as a model of learning systems[J]. IEEE Translation on System Science and Cybernet, 1969, 5: 215-223.
[3]Hopcroft J E.自动机理论、语言和计算导论[M].刘田等译,第二版.北京: 机械工业出版社,2004.
[4]陶仁骥.自动机引论[M].北京:科学出版社,1986.
[5]Santos E S. Maximin automata[J]. Inform.Control, 1968, 13: 363-377.
[6]Santos E S. Realization of fuzzy languages by Probabilistic, max-prod and maximin automata[J]. Information Sciences, 1975, 8: 39-53.
[7]Mizumoto M, Tanaka J, Tanaka K. Some consideration on fuzzy automata[J]. Computing Systems Sciences, 1969, 3: 409-422.
[8]Malik D S, Mordeson John N. On fuzzy recognizers[J]. Kybernetics, 1999, 28(1): 47-60.
[9]Basak N C, Gupta A. On quotient machines of a fuzzy automaton and the minimal machine[J]. Fuzzy Sets and Systems, 2002, 125: 223-229.
[10]Umbhojkar H V K, Chaudhari S R. Fuzzy recognizers and recognizable sets[J]. Fuzzy Sets and Systems, 2002,131: 381-392.
[11]HoLcombe W M L .Algebraic Automata Theory[M]. Cambridge: Cambridge University Press, 1982.
[12]Eilenburg S. Automata, Languages and Machines Vol A [M]. London :Academic Press, 1974.
[13]Ginzburg A. Algebraic Automata Theory[M]. Cambridge: Cambridge University Press, 1982.
[14]Malik D S, Mordeson J N, Sen M K. On Subsystems of fuzzy finite state machines[J]. Fuzzy Sets and Systems, 1994, 68: 83-92.
[15]谢季坚,刘承平.模糊数学方法及其应用[M],第二版.武汉:华中科技大学出版社,2000.
[16]邓婷,易忠,邓培民.状态机的稳定状态与稳定子集[J].广西师范大学学报(自然科学版), 2005,23(2):29-32.
[17]Malik D S, Mordeson J N, Men M K. Submachines of fuzzy finite state machines[J]. Journal of Fuzzy Mathematics, 1994, 2: 781-792.
[18]Malik D S, Mordeson J N, Men M K. Products of fuzzy state machines[J]. Fuzzy Sets and Systems, 1997, 92: 95-102.
[19]Mordeson J N, Nair P S. Successor and source of (fuzzy) finite state machines and (fuzzy) directed graphs[J]. Information Sciences, 1996, 95: 113-124.
[20]Kumbhojkar H V, Chaudhair S R. On covering of products of fuzzy state machines[J]. Fuzzy Sets and Systems, 2002, 125: 215-222.
[21]Peeva K. Equivalence, reduction and minimization of finite automata over semirings[J]. Theoretical Computer Science, 1991, 88: 269-285.
[22]吕书志.环上线性有限自动机的可逆性的一些结果[J].计算机学报,1991,8:570-578.
[23]欧海文,戴宗铎.自内射环与线性自动机的线性(弱)逆[J].中国科学(A 辑),1998, 28(10):877-883.
[24]Tatjana Petkovi c '. Congruences and homomorphisms of fuzzy automata[J]. Fuzzy Sets and Systems, 2006, 157: 444-458.
[25]Didier Dubois, Henri Prade. Fuzzy Sets and Systems, theory and applications[M]. New York : Academic Press, 1980.
[26]Zadeh L A. Fuzzy sets[J]. Information Control, 1965, 8: 338-353.
[27]Lee E T, Zadeh L A. Note on fuzzy languages[J]. Information Sciences, 1969, 1: 403-419.
[28]Shen J Z. Fuzzy language on free monoid[J]. Information Sciences, 1996, 88: 149-168.
[29]Malik D S, Mordeson J N. On fuzzy regular languages[J]. Information Sciences, 1996, 88: 263-273.
[30]邱道文.基于完备剩余格值逻辑的自动机理论—Ⅰ.拓扑刻画[J].中国科学(E 辑), 2003,33(2):137-146.
[31]Mansoor Doostfatemah, Stefan C Kremer. New directions in fuzzy automata[J]. International Journal of Approximate Reasoning, 2005, 38: 175-214.
[32]李平,李永明.几类格值自动机的关系[J].模糊系统与数学,2005,19(3):96-100.
[33]李永明.格值自动机与语言[J].陕西师范大学学报(自然科学版),2003,31(4):1-6.
[34]Li Zhihui, Li Ping, Li Yongming. The relationships among several types of fuzzy automata[J]. Information Sciences, 2006, 176: 2208-2226.
[35]Li Yongming, Pedryczc Witold. Fuzzy finite automata and fuzzy regular expressions with Membership values in lattice-ordered monoids[J]. Fuzzy Sets and Systems, 2005, 156: 68-92.
[36]Li Y M. Lattice-valued automata and their languages[R], in: 8th World Multiconference on Systems, Cybernetics and Informatics(SCI2004), 18-21 July 2004, Orlando, FL, USA.
[37]Malik D S, Mordeson John N., Sen M K. Minimization of fuzzy finite automata[J], Information Sciences, 1999, 113: 323-330.
[38]Cheng Wei, MO Zhiwen. Minimization algorithm of fuzzy finite automata[J]. Fuzzy Sets and Systems, 2004, 141: 439-448.
[39]MO Zhiwen, PENG Jiayin. Fuzzy minimal automata and reduced fuzzy automata[J]. Journal of Sichuan Normal University(Natural Science), 2002, 25(6): 585-587.
[40]MO Zhiwen, HU Hongli. Minimization of fuzzy finite generalized automata[J]. Journal of Electronic Science and Technology of China, 2006, 4(1): 86-88.
[41]Li Yongming, Pedryczc Witold. Minimization of lattice finite automata and its application to the decomposition of lattice languages[J]. Fuzzy Sets and Systems, 2007, 158: 1423-1436.
[42]Lei Hongxuan, Li Yongming. Minimization of states in automata theory based on finite lattice-ordered Monoids[J]. Information Sciences, 2007, 177: 1413-1421.
[43]雷红轩,李永明.同步格值自动机的约简和最小化算法[J].计算机工程与应用,2006,16: 57-60.
[44]Topencharov V, Ketty Peeva. Equivalence,reduction and minimization of finite fuzzy -automata[J]. Journal of Mathematical Analysis and Applications, 1981, 84: 270-281.
[2]Wee W G, Fu K S. A formulation of fuzzy automata and its application as a model of learning systems[J]. IEEE Translation on System Science and Cybernet, 1969, 5: 215-223.
[3]Hopcroft J E.自动机理论、语言和计算导论[M].刘田等译,第二版.北京: 机械工业出版社,2004.
[4]陶仁骥.自动机引论[M].北京:科学出版社,1986.
[5]Santos E S. Maximin automata[J]. Inform.Control, 1968, 13: 363-377.
[6]Santos E S. Realization of fuzzy languages by Probabilistic, max-prod and maximin automata[J]. Information Sciences, 1975, 8: 39-53.
[7]Mizumoto M, Tanaka J, Tanaka K. Some consideration on fuzzy automata[J]. Computing Systems Sciences, 1969, 3: 409-422.
[8]Malik D S, Mordeson John N. On fuzzy recognizers[J]. Kybernetics, 1999, 28(1): 47-60.
[9]Basak N C, Gupta A. On quotient machines of a fuzzy automaton and the minimal machine[J]. Fuzzy Sets and Systems, 2002, 125: 223-229.
[10]Umbhojkar H V K, Chaudhari S R. Fuzzy recognizers and recognizable sets[J]. Fuzzy Sets and Systems, 2002,131: 381-392.
[11]HoLcombe W M L .Algebraic Automata Theory[M]. Cambridge: Cambridge University Press, 1982.
[12]Eilenburg S. Automata, Languages and Machines Vol A [M]. London :Academic Press, 1974.
[13]Ginzburg A. Algebraic Automata Theory[M]. Cambridge: Cambridge University Press, 1982.
[14]Malik D S, Mordeson J N, Sen M K. On Subsystems of fuzzy finite state machines[J]. Fuzzy Sets and Systems, 1994, 68: 83-92.
[15]谢季坚,刘承平.模糊数学方法及其应用[M],第二版.武汉:华中科技大学出版社,2000.
[16]邓婷,易忠,邓培民.状态机的稳定状态与稳定子集[J].广西师范大学学报(自然科学版), 2005,23(2):29-32.
[17]Malik D S, Mordeson J N, Men M K. Submachines of fuzzy finite state machines[J]. Journal of Fuzzy Mathematics, 1994, 2: 781-792.
[18]Malik D S, Mordeson J N, Men M K. Products of fuzzy state machines[J]. Fuzzy Sets and Systems, 1997, 92: 95-102.
[19]Mordeson J N, Nair P S. Successor and source of (fuzzy) finite state machines and (fuzzy) directed graphs[J]. Information Sciences, 1996, 95: 113-124.
[20]Kumbhojkar H V, Chaudhair S R. On covering of products of fuzzy state machines[J]. Fuzzy Sets and Systems, 2002, 125: 215-222.
[21]Peeva K. Equivalence, reduction and minimization of finite automata over semirings[J]. Theoretical Computer Science, 1991, 88: 269-285.
[22]吕书志.环上线性有限自动机的可逆性的一些结果[J].计算机学报,1991,8:570-578.
[23]欧海文,戴宗铎.自内射环与线性自动机的线性(弱)逆[J].中国科学(A 辑),1998, 28(10):877-883.
[24]Tatjana Petkovi c '. Congruences and homomorphisms of fuzzy automata[J]. Fuzzy Sets and Systems, 2006, 157: 444-458.
[25]Didier Dubois, Henri Prade. Fuzzy Sets and Systems, theory and applications[M]. New York : Academic Press, 1980.
[26]Zadeh L A. Fuzzy sets[J]. Information Control, 1965, 8: 338-353.
[27]Lee E T, Zadeh L A. Note on fuzzy languages[J]. Information Sciences, 1969, 1: 403-419.
[28]Shen J Z. Fuzzy language on free monoid[J]. Information Sciences, 1996, 88: 149-168.
[29]Malik D S, Mordeson J N. On fuzzy regular languages[J]. Information Sciences, 1996, 88: 263-273.
[30]邱道文.基于完备剩余格值逻辑的自动机理论—Ⅰ.拓扑刻画[J].中国科学(E 辑), 2003,33(2):137-146.
[31]Mansoor Doostfatemah, Stefan C Kremer. New directions in fuzzy automata[J]. International Journal of Approximate Reasoning, 2005, 38: 175-214.
[32]李平,李永明.几类格值自动机的关系[J].模糊系统与数学,2005,19(3):96-100.
[33]李永明.格值自动机与语言[J].陕西师范大学学报(自然科学版),2003,31(4):1-6.
[34]Li Zhihui, Li Ping, Li Yongming. The relationships among several types of fuzzy automata[J]. Information Sciences, 2006, 176: 2208-2226.
[35]Li Yongming, Pedryczc Witold. Fuzzy finite automata and fuzzy regular expressions with Membership values in lattice-ordered monoids[J]. Fuzzy Sets and Systems, 2005, 156: 68-92.
[36]Li Y M. Lattice-valued automata and their languages[R], in: 8th World Multiconference on Systems, Cybernetics and Informatics(SCI2004), 18-21 July 2004, Orlando, FL, USA.
[37]Malik D S, Mordeson John N., Sen M K. Minimization of fuzzy finite automata[J], Information Sciences, 1999, 113: 323-330.
[38]Cheng Wei, MO Zhiwen. Minimization algorithm of fuzzy finite automata[J]. Fuzzy Sets and Systems, 2004, 141: 439-448.
[39]MO Zhiwen, PENG Jiayin. Fuzzy minimal automata and reduced fuzzy automata[J]. Journal of Sichuan Normal University(Natural Science), 2002, 25(6): 585-587.
[40]MO Zhiwen, HU Hongli. Minimization of fuzzy finite generalized automata[J]. Journal of Electronic Science and Technology of China, 2006, 4(1): 86-88.
[41]Li Yongming, Pedryczc Witold. Minimization of lattice finite automata and its application to the decomposition of lattice languages[J]. Fuzzy Sets and Systems, 2007, 158: 1423-1436.
[42]Lei Hongxuan, Li Yongming. Minimization of states in automata theory based on finite lattice-ordered Monoids[J]. Information Sciences, 2007, 177: 1413-1421.
[43]雷红轩,李永明.同步格值自动机的约简和最小化算法[J].计算机工程与应用,2006,16: 57-60.
[44]Topencharov V, Ketty Peeva. Equivalence,reduction and minimization of finite fuzzy -automata[J]. Journal of Mathematical Analysis and Applications, 1981, 84: 270-281.