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.     

Modelling concurrency with comtraces and generalized comtraces

Comtraces (combined traces) are extensions of Mazurkiewicz traces that can model the “not later than” relationship. In this paper, we first introduce the novel notion of generalized comtraces, extensions of comtraces that can additionally model the “non-simultaneously” relationship. Then we study some basic algebraic properties and canonical representations of comtraces and generalized comtraces. Finally we analyze the relationship between generalized comtraces and generalized stratified order structures. The major technical contribution of this paper is a proof showing that generalized comtraces can be represented by generalized stratified order structures.     

Monoid-labeled transition systems

Given a -complete (semi)lattice , we consider -labeled transition systems as coalgebras of a functor ⁽⁻⁾, associating with a set X the set ^X of all -fuzzy subsets. We describe simulations and bisimulations of -coalgebras to show that L⁽⁻⁾ weakly preserves nonempty kernel pairs iff it weakly preserves nonempty pullbacks iff L is join infinitely distributive (JID).Exchanging for a commutative monoid , we consider the functor ⁽⁻⁾_ω which associates with a set X all finite multisets containing elements of X with multiplicities m M. The corresponding functor weakly preserves nonempty pullbacks along injectives iff 0 is the only invertible element of , and it preserves nonempty kernel pairs iff is refinable, in the sense that two sum representations of the same value, r₁ + … + r_m = c₁ + … + c_n, have a common refinement matrix (m_{(i, j)}) whose k-th row sums to r_k and whose l-th column sums to c_l for any 1≤ k ≤ m and 1 ≤ l ≤ n.     

格值树自动机与格值上下文无关树文法的等价性

本文将模糊树自动机和模糊上下文无关树文法的概念推广到格半群上。证明了在接受语言和生成语言的意义下,树自动机和上下文无关树文法是等价的。同时给出了构造正规形式的等价文法的方法。     

取值于赋值幺半群的加权正则文法语言

正则文法是研究自动机的重要工具。引入取值于赋值幺半群的加权正则文法、加权类正则文法的定义,讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机(WFA)的关系。证明了在赋值幺半群上,已知一个加权正则文法或加权类正则文法,分别存在一个WFA与之等价。定义了可分配的赋值幺半群,证明了在可分配的赋值幺半群上已知一个WFA,存在一个加权正则文法和加权类正则文法与之等价,即证明了可分配的赋值幺半群上加权正则文法、加权类正则文法和WFA在生成语言上等价,并举例说明了赋值幺半群的可分配性不是已知WFA存在与之等价的加权正则文法或加权类正则文法的必要条件。     

Optimizing Queries with Object Updates

Object-oriented databases (OODBs) provide powerful data abstractions and modeling facilities but they usually lack a suitable framework for query processing and optimization. Even though there is an increasing number of recent proposals on OODB query optimization, only few of them are actually focused on query optimization in the presence of object identity and destructive updates, features often supported by most realistic OODB languages. This paper presents a formal framework for optimizing object-oriented queries in the presence of side effects. These queries may contain object updates at any place and in any form. We present a language extension to the monoid comprehension calculus to express these object-oriented features and we give a formal meaning to these extensions. Our method is based on denotational semantics, which is often used to give a formal meaning to imperative programming languages. The semantics of our language extensions is expressed in terms of our monoid calculus, without the need of any fundamental change to our basic framework. Our method not only maintains referential transparency, which allows us to do meaningful query optimization, but it is also practical for optimizing OODB queries since it allows the same optimization techniques applied to regular queries to be used with minimal changes for OODB queries with updates.     

确定型格值有限自动机的最小化

给出了确定型格值有限自动机的定义,并同时给出了有效终止状态和可达到状态的定义。指出了求取DLFA M=Q,Σ,δ,q₀,σ的实质是求取Q/R_k。由此以可到达状态为基础引入了等价关系R_k、S_k与商集Q/S_k,证明了R_k=R_k-1∩S_k,由此得到Q/R_k的等价类为Q/R_k-1中等价类与Q/S_k中等价类的非空交集全体。引入了H_k,并证明了可由H_k求取Q/S_k,从而得到仅利用集合运算便可求取Q/R_k的算法,最终给出了DLFA最小化算法的一个容易实现的构造型描述和相应示例。     

Factorial languages whose growth function is quadratically upper bounded

A language L over a finite alphabet is factorial if L = F(L), where F(L) denotes the set of the factors of all words of L. It is proved that if the growth function of L is quadratically upper-bounded then the monoid of the factors of L is weakly-permutable.     

一类格值自动机的极小化

给出了格值自动机的同余和同态,从代数角度出发详细研究了同余和同态关系的代数性质,揭示了格值自动机的代数性质和取值格半群的紧密联系,利用同余和同态关系最终研究了格值自动机的极小化问题,在正则同余下给出了可在有限步实现具有模糊初始状态和特殊模糊终状态的自动机极小化的算法。     

样本依赖与连接依赖的等价性

以抽象代数为工具,探索了全样本依赖与全连接依赖之间的关系.首先,分别在全样本依赖集和全连接依赖集上建立等价关系,这两种等价关系都将作用相同的依赖视为等价依赖. 然后证明了在这两个等价关系下的商集分别构成么半群,并且这两个么半群是同构的.这就等于证明了全样本依赖类本质上等同于全连接依赖类.最后给出了一个关于全无环连接依赖的有趣结果.有关结果可以在关系数据库的设计中发挥积极作用.