幺半环上模糊有限状态自动机积的覆盖关系

提出了幺半环上模糊有限状态自动机的各种乘积以及覆盖的定义,并得到了一些性质.证明了直积、级联积、圈积三种乘积以及和之间的覆盖关系,得到了乘积自动机、和自动机覆盖关系的一些代数性质.     

幺半环上模糊有限状态机的一些性质

状态机的很多性质在计算机等方面有着广泛的应用,因此对状态机的研究具有重要的意义.本文给出了幺半环上模糊有限状态机的概念,对状态之间的等价进行了定义,引入了同态的概念,得到同态定理和满同态分解定理,讨论了幺半环上模糊有限状态机在同态下的交换性质和连通性以及子状态机的可分离性.     

状态转移函数对加权自动机计算能力的影响

在非确定型加权自动机(NS-WA)与确定型加权自动机(DS-WA)的基础上,引入了状态转移函数是分明的非确定型加权自动机(NS-WA_c)与状态转移函数是分明的带空移动的非确定型加权自动机(NS-WA_(ε-c))的概念。在已知NS-WA与DS-WA不等价的结论下,进一步探究了NS-WA_c、NS-WA_(ε-c)与DS-WA之间的等价性,并给出了等价性证明以及相关的算法和例子。     

几类格值自动机的关系

本文给出了四类格值自动机及其语言的定义，证明了前三类格值自动机的等价性，讨论了第四类格值自动机与前三类格值自动机的关系。     

两类循环模糊自动机的弱等价性

定义循环模糊自动机和循环模糊有限状态自动机,并讨论了这两类循环模糊自动机的弱等价性.     

可逆模糊自动机

首先提出了可逆模糊自动机的概念,研究了能被可逆模糊自动机接受的语言(简记为F(∑))的一些性质.其次给出了自由群上被可逆模糊自动机接受的模糊子集的概念,详细研究了可逆模糊语言与经典可逆语言的关系.最后,通过引入语法幺半群刻画了F(∑)的代数性质.通过这些性质可以有效的判断一个模糊语言是否能被一个可逆模糊自动机接受.     

有界Rl-幺半群的犹豫模糊滤子北大核心

将犹豫模糊集应用到有界剩余格序幺半群(Rl-幺半群)中,引入有界Rl-幺半群的犹豫模糊滤子的概念,研究其相关性质。获得了犹豫模糊滤子的一些等价刻画,建立了犹豫模糊滤子与其水平滤子之间的关系。讨论了犹豫模糊集成为犹豫模糊滤子的条件,给出了由一个给定犹豫模糊集生成的犹豫模糊滤子的表达式。     

Ω-模糊可补子半环

给定一个集合Ω,引入了可补半环的Ω-模糊可补子半环的概念,研究了它的一些基本性质。给出了可补半环的Ω-模糊可补子半环的等价刻画,证明了可补半环的Ω-模糊可补子半环的交、同态像与同态原像等也是可补半环的Ω-模糊可补子半环。最后,通过在SΩ上定义运算+,×,-,得到可补半环(SΩ,+,×,-),并研究了与其相关的模糊可补子半环与Ω-模糊可补子半环。     

具有输出字符功能的模糊自动机的最小化问题

通过文献[8]中两类具有输出字符功能的Fuzzy自动机和Fuzzy有限状态自动机的强等价性,等价性和弱等价性的条件,在以往仅仅给出的Fuzzy有限状态自动机的最小化问题基础上,讨论了具有更广泛意义的具有输出字符功能的Fuzzy自动机的最小化问题,以及其最小化自动机与Fuzzy有限状态自动机的最小化自动机在不同条件下的关系。     

Max-Lukasiewicz复合推理下的模糊图灵机

研究max-Lukasiewicz复合推理下的模糊图灵机.形式化定义了模糊图灵机--确定型模糊图灵机、非确定型模糊图灵机、带部分转移函数的非确定型模糊图灵机和多带模糊图灵机,研究了这几类模糊图灵机的关系.进而定义模糊图灵机上的模糊递归可枚举语言和模糊递归语言.得出结论:当接受模糊递归可枚举语言时 ,非确定型模糊图灵机和确定型模糊图灵机不等价;而接受模糊递归语言时,它们等价.     

Didactic approach for teaching nondeterminism in automata theory

Nondeterminism plays a central role in almost all fields of computer science. It has been incorporated naturally as well as in the theory of automata as a generalization of determinism. Although nondeterministic finite automata do not have more recognition power than deterministic ones their importance and usefulness is of no doubt.Unfortunately, the operation of the mathematical model of nondeterministic automata is difficult to understand which means a didactic challenge for every teacher and lecturer. This paper gives a didactic approach to introduce the notion of finite (deterministic and) nondeterministic automata.As a teaching tool we make use of the automata theory package developed in Maple. We put emphasis on the process character of learning and work out a method that promotes the repetitive experiments.     

Bisimulations for fuzzy automata

Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy automata A and B is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalence relations on A and B and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalence relations. As a consequence we get that fuzzy automata A and B are UFB-equivalent, i.e., there is a uniform forward bisimulation between them, if and only if there is a special isomorphism between the factor fuzzy automata of A and B with respect to their greatest forward bisimulation fuzzy equivalence relations. This result reduces the problem of testing UFB-equivalence to the problem of testing isomorphism of fuzzy automata, which is closely related to the well-known graph isomorphism problem. We prove some similar results for backward-forward bisimulations, and we point to fundamental differences. Because of the duality with the studied concepts, backward and forward-backward bisimulations are not considered separately. Finally, we give a comprehensive overview of various concepts on deterministic, nondeterministic, fuzzy, and weighted automata, which are related to bisimulations.     

On minimal realization of fuzzy behaviour and associated categories

This paper is towards the study of minimal deterministic automata with fuzzy output which realizes the given fuzzy behaviour. The construction of such automaton is based on Myhill-Nerode’s theory, and it is shown that this automaton is a canonical realization of given fuzzy behaviour. Meanwhile, we introduce the categories of deterministic automata with fuzzy output and fuzzy behaviour. The relationship between both the categories through functors is also studied.     

On an expansion of nondeterministic finite automata

We consider a possible generalization of nondeterministic finite automata. The goals of this consideration are: to apply some obtained algorithms for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; to simplify some proofs for algorithms of simplification for usual nondeterministic automata.     

Weighted automata and weighted logics on infinite words

We introduce weighted automata over infinite words with Muller acceptance condition and we show that their behaviors coincide with the semantics of weighted restricted MSO-sentences. Furthermore, we establish an equivalence property of weighted Muller and weighted Büchi automata over certain semirings.     

Shortest directing words of nondeterministic directable automata

In this paper, we will survey several results on the shortest directing words of various types of nondeterministic directable automata.¹     

模糊关系下的半环的广义模糊双理想

给出了半环的广义模糊双理想的概念并讨论了模糊关系下的半环的广义模糊双理想的一些代数性质.