Minimization of states in automata theory based on finite lattice-ordered monoids

In this study, we consider a concept of complete L-fuzzy matrix, define complete lattice-valued finite automata (CLFAs) and study their properties. The definitions of statewise equivalence relations and automata equivalence relations of a CLFA are given, two algorithms are aimed at the minimization of states of a CLFA.     

Automata theory based on complete residuated lattice-valued logic

This paper establishes a fundamental framework of automata theory based on complete residuated lattice-valued logic. First it deals with how to extend the transition relation of states and par-ticularly presents a characterization of residuated lattice by fuzzy automata (called (?) valued automata). After that fuzzy subautomata (called (?) valued subautomata), successor and source operators are pro-posed and their basic properties as well as the equivalent relation among them are discussed, from which it follows that the two fuzzy operators are exactly fuzzy closure operators. Finally an L bifuzzy topological characterization of Q valued automata is presented, so a more generalized fuzzy automata theory is built.     

基于Unsharp量子逻辑的自动机和文法理论

初步建立了具有某种分配律的扩展格序效应代数和格序QMV代数这两种unsharp量子结构上的自动机与文法理论的基本框架。引入了ε-值正则文法的概念,证明了任意ε-值自动机识别的语言等价于某种ε-值正则文法所生成的语言;反之,任意[ε]-值正则文法所生成的语言等价于某种ε-值自动机识别的语言。讨论了ε-值正则语言在和、连接及反转运算下的封闭性质。     

Automata theory based on quantum logic: some characterizations

Automata theory based on quantum logic (abbr. l-valued automata theory) may be viewed as a logical approach of quantum computation. In this paper, we characterize some fundamental properties of l-valued automata theory, and discover that some properties of the truth-value lattices of the underlying logic are equivalent to certain properties of automata. More specifically (i) the transition relations of l-valued automata are extended to describe the transitions enabled by strings of input symbols, and particularly, these extensions depend on the distributivity of the truth-value lattices (Proposition 3.1); (ii) some properties of the l-valued successor and source operators and l-valued subautomata are demonstrated to be equivalent to a property of the truth-value lattices which is exactly equivalent to the distributive law (Proposition 4.3 and Corollary 4.4). This is a new characterization of Boolean algebras in the framework of l-valued automata theory; (iii) we verify that the intersection of two l-valued subautomata is still an l-valued subautomaton if and only if the multiplication (&) is distributive over the union in the truth-value lattices (Proposition 4.5), which is strictly weaker than the usual distributivity; (iv) we show that some topological characterizations in terms of the l-valued successor and source operators also rely on the distributivity of truth-value lattices (Theorem 5.6). Finally, we address some related topics for further study.     

Automata theory based on complete residuated lattice-valued logic (Ⅱ)

It reveals some equivalences between automata based on complete residuated lattice-valued logic (called (?) valued automata) and the truth-value lattice of the underlying logic (i.e. residuated lattice). In particular, it demonstrates several basic equivalent characterizations on the retriev-ability of (?) valued automata. Finally, the connections of the homomorphisms between two (?) valued automata to continuous mappings and open mappings are clarified. So this paper establishes further the more profound fuzzy automata theory.     

一种基于元胞自动机的图像拼接方法

描述了一种基于元胞自动机的图像拼接方法,采用元胞自动机提取图像特征点,然后以特征点邻域灰度互相关法进行特征点匹配,最后根据匹配的特征点对得到图像间的变换参数。实验结果表明,本方法不仅准确实现了图像拼接,而且降低了图像重叠度的要求。     

基于Matlab的元胞自动机的仿真设计

元胞自动机不仅是理论计算机科学领域的一个重要的计算模型 ,而且可视为一无限维的离散动力系统 ,被广泛应用于自然科学和社会科学各领域的复杂性的研究中 ,是一个重要的研究方法和工具。该文以Matlab为开发工具 ,开发了元胞自动机的可视模型 ,为其在各个领域的复杂性研究提供了一个简易、可行的计算机仿真工具。     

Non-uniform Cellular Automata based on Open-ended Rule Evolution

Cellular automata (CAs) are mathematical models of spatially and temporally discrete mathematical systems. Non-uniform CAs are the cellular automata in which each cell may contain a different transition rule and change it with time, while all cells share the same transition rule in regular CAs. Little is still known about the dynamics of open-ended evolution of rules in non-uniform CAs. The purpose of our study is to construct and investigate a model of non-uniform CAs capable of open-ended rule evolution exhibiting a wide variety of behavior across all Wolfram’s classes. For this purpose, we construct 1-dimensional 2-state 3 neighborhood non-uniform CAs with evolving transition rules. In the model, we found an interesting dynamics that Class II (periodical behavior) and III (chaotic behavior) patterns emerged alternately, between which Class IV patterns sometimes emerged.     

Matrices over semirings

Introducing the concept of semi-invertibility of square matrices over semirings, some sufficient conditions for semi-invertibility of square matrices over various kinds of semirings are obtained. Also a necessary and sufficient condition for semi-invertibility of square matrices over semirings is obtained.     

TRDFA:一种用于事务识别的DFA

在Web使用挖掘的预处理中,会话识别结束后需要经过路径补充将那些由于缓存而遗漏的页面补全,而后进行事务识别。构造了一个TRDFA,能从未经路径补充的会话中直接提取事务,并考虑了多窗口方式打开页面的情形。该方法对于只关心最终事务的用户而言,节省了整个预处理的时间,提高了效率。     

基于时间自动机的实时系统建模及验证

实时系统必须在一个事先定义好的时间限制内对来自外部或内部的事件进行响应,如何有效验证实时模型的正确性和安全性是一个难点.文章通过多个时间自动机来模拟实时系统中的各个对象,并用UPPAAL对模型进行验证,减少了模型验证的状态搜索空间,为实时嵌入式系统开发和验证提供了一种可行、安全的控制机制.实验结果显示了系统的有效性.     

Fuzzy ideals of semirings

Using the idea of quasi-coincidence of a fuzzy point with a fuzzy set, the concept of an (α, β)-fuzzy ideal, which is a generalization of a fuzzy ideal, in a semiring is introduced and related properties are investigated. At the following, the concept of fuzzy ideals with thresholds is introduced, and the relationship between logical implication operators and fuzzy ideals with thresholds are analyzed.     

Continuous monoids and semirings

Different kinds of monoids and semirings have been defined in the literature, all of them named “continuous”. We show their relations. The main technical tools are suitable topologies, among others a variant of the well-known Scott topology for complete partial orders.     

某些半环的结构

介绍了A（M）-完全正则半环,并利用（2,2）型代数的坚固构架的概念,给出了A（M）-完全正则半环的次直积分解与其加法（乘法）半群的次直积分解之间的密切联系。特别地,推广了以往文献的一些结果。     

Automata theory,computer-aided design,and some problems of informatics

The main stages of formation and development of automata theory and its applications to computer-aided design of computing systems are considered. Some open problems of modern theoretical cybernetics are discussed. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 3–7, September–October 2007.     

基于自动机原理的硬币兑换机的优化及其应用分析

本文提出了用自动机原理重新设计一台硬币兑换机,通过把原来的确定性有穷自动机变成了非确定性有穷自动机,在仅仅增加二个状态数的情况下实现兑换面额的大幅度增加,大大满足了乘客兑换硬币的需求.文中采用了贪婪的兑换算法,且对该方法进行了编程实现,并对其管理功能的扩展进行了应用分析,同时描述了软件设计思路.