Bisimulation and Hidden Algebra

A hidden algebra is a special case of coalgebra. A hidden congruence on a hidden algebra corresponds to a bisimulation equivalence on the corresponding coalgebra. The paper generalizes the notion of hidden congruence to that of hidden bisimulation between two different hidden algebras. We first define hidden bisimulation between two hidden algebras having the same signature. A hidden bisimulation is in fact a bisimulation between the corresponding coalgebras. We then define hidden simulation between two hidden algebras having different signatures related by a vertical signature morphism. We prefer to call this relation simulation because it is unidirectional, due to the signature morphism. For the last case, the relationship between simulation and refinement is discussed.     

粗糙集与FI代数

在粗糙集的代数刻画方面,一个重要方法是在偶序对<■(X),■(X)>构成的集合中,通过定义基本运算,寻找刻画偶序对所构成集合的代数结构。本文在偶序对<■(X),■(X)>构成的集合中定义二元运算→,证明了偶序对<■(X),■(X)>所构成的集合构成FI代数,并给出几个简单性质。     

Kleene Algebra and Bytecode Verification

Most standard approaches to the static analysis of programs, such as the popular worklist method, are first-order methods that inductively annotate program points with abstract values. In [6] we introduced a second-order approach based on Kleene algebra. In this approach, the primary objects of interest are not the abstract data values, but the transfer functions that manipulate them. These elements form a left-handed Kleene algebra. The dataflow labeling is not achieved by inductively labeling the program with abstract values, but rather by computing the star (Kleene closure) of a matrix of transfer functions. In this paper we show how this general framework applies to the problem of Java bytecode verification. We show how to specify transfer functions arising in Java bytecode verification in such a way that the Kleene algebra operations (join, composition, star) can be computed efficiently. We also give a hybrid dataflow analysis algorithm that computes the closure of a matrix on a cutset of the control flow graph, thereby avoiding the recalculation of dataflow information when there are cycles in the graph. This method could potentially improve the performance over the standard worklist algorithm when a small cutset can be found.     

Involution Narrowing Algebra

The narrowing algebra formalism underlying CLP(intervals) consists of lattice-ordered monoids of monotone contractions on the lattice of states; these are generated by the canonical idempotent operators of the primitive relations of the constraint system used for the problem. This mathematical structure has some similarities with that of some classical operator rings, even though the underlying states form a non-Boolean lattice instead of a linear space. In this paper we show that in the restricted case of certain binary interval convex primitives, there is a broken symmetry which can be restored by generalizing the state lattice to produce an involution on the important fragment of the narrowing algebra. This involution allows some basic theorems of classical *-rings to be ported into this domain.     

Using the Magma Computer Algebra System in Abstract Algebra Courses

Students meeting their first serious course in abstract algebra commonly experience difficulty understanding many of the basic concepts. This makes it very hard for them to interpret and generate proofs. The first step in reaching an understanding of such concepts is often best achieved by constructing and manipulating instances in particular algebraic structures. Computer algebra systems open up the possibility of students being able to experiment rapidly and conveniently with such concepts in a variety of structures having non-trivial size and complexity. The new Magma computer algebra system has a syntax and semantics based directly on fundamental algebraic notions, and consequently should provide an appropriate learning environment for those branches of mathematics that are heavily algebraic in nature. This paper describes the development of Magma-based exercises and a course methodology that utilizes Magma as a key learning tool in a Pass-level Rings and Fields course given at the University of Sydney.     

路由网络代数

基于基本网络代数 (BasicNetworkAlgebra ,BNA)和LOTOS/E LOTOS ,该文提出一种适合于分析Inter net路由系统行为的代数系统 .该代数系统称为路由网络代数 (RoutingNetworkAlgebra,RNA) ,它结合了BNA中的并行、串行运算以及LOTOS中的同步并行运算 ,并在此基础提出更适合于描述Internet路由系统行为的选择运算“ ”、协同并行“ ”以及路由网络常量 ,如m×n(路由转发 )、∧ m(分支 )、∨ m(合并 )、⊥ m(下沉 )和┬ m(亚元 ) .通过分析由上述代数运算和路由网络常量构成的路由网络代数模型 ,可以分析路由系统中死锁 (deadlock)和活锁(alivelock)等行为 .为了检验路由网络代数的有效性 ,完成了BGP路由稳定性的实验分析工作 .     

贪婪协议路由代数及其应用

在无线网络路由协议中,错误地使用路由尺度会降低网络的路由性能,甚至会导致某些节点之间根本无法正常通信,称为路由尺度的兼容性问题.基于路由代数理论,分析了贪婪协议中路由尺度的兼容性问题,推导出了贪婪算法用作数据分组的转发机制时贪婪协议具有可达性的充分必要条件,并以4个路由尺度实例说明了分析结论在贪婪协议设计中的具体应用,为贪婪协议的设计提供了重要的技术依据.     

一种概率关系数据库系统

传统关系模式不适合处理不确定性信息,为处理不确定信息,该文基于元组属性间的联合概率,定义了概率关系及几种基本的概率关系操作和关系代数,提出了概率函数依赖关系的概念,给出了一种概率关系数据库模式及代数。     

Computer Algebra and Computing Special Functions

Examples of using symbolic transformations for computing special functions are given. These transformations considerably improve stability and efficiency of precise computation in a number of difficult problems. The first example deals with the computation of the Riemann zeta function (s). A technique for the elimination of false poles of this function on the critical line s = 1/2 + it is suggested. The second example concerns the computation of the generalized hypergeometric function _p F _{p – 1}. A method of analytic continuation to the neighborhood of the singular point z = 1 is developed.     

Algebra and logic for access control

The access control problem in computer security is fundamentally concerned with the ability of system entities to see, make use of, or alter various system resources. We provide a mathematical framework for modelling and reasoning about (distributed) systems with access control. This is based on a calculus of resources and processes together with a Hennessy–Milner-style modal logic, based on the connectives of bunched logic, for which an appropriate correspondence theorem obtains. As a consequence we get a consistent account of both operational behaviour and logical reasoning for systems with access control features. In particular, we are able to introduce a process combinator that describes, as a form of concurrent composition, the action of one agent in the role of another, and provide a logical characterization of this operator via a modality ‘says’. We give a range of examples, including analyses of co-signing, roles, and chains of trust, which illustrates the utility of our mathematical framework.     

粗糙集代数与蕴涵格

在粗糙集的代数刻画方面,一个重要方法是在偶序对〈R（X）,R（X）〉构成的集合中通过定义基本运算寻找刻画偶序对所成集合的代数结构。其中,最有影响的代数结构是正则双Stone代数和Nelson代数。本文从偶序对〈T（X）,R（X）〉构成的集合入手,通过定义蕴涵运算证明了偶序对〈R（X）,R（X）〉所成集合构成蕴涵格,讨论了粗蕴涵格与
正则双Stone代数的关系。本文的讨论可为粗糙逻辑和粗糙推理奠定基础。     

Equality in Computer Algebra and Beyond

Equality is such a fundamental concept in mathematics that, in fact, we seldom explore it in detail, and tend to regard it as trivial. When it is shown to be non-trivial, we are often surprised. As is often the case, the computerization of mathematical computation in computer algebra systems on the one hand, and mathematical reasoning in theorem provers on the other hand, forces us to explore the issue of equality in greater detail.     

多粒化的粗糙集代数

众所周知,一个粗糙集代数是由一个集合代数加上一对近似算子构成的。一方面 ,在公理化的方法下对经典的多粒化粗糙集代数系统进行了讨论,可知经典的粗糙集代数没有很好的性质;另一方面,给出了单调等价关系的定义,并给出了基于单调等价关系的多粒化近似算子的概念,在此基础上讨论了粗糙集代数的性质,并得到了诸多结果。