Unification in Abelian semigroups

Unification in equational theories, i.e., solving of equations in varieties, is a basic operation in computational logic, in artificial intelligence (AI) and in many applications of computer science. In particular the unifiction of terms in the presence of an associative and commutative function, i.e., solving of equations in Abelian semigroups, turned out to be of practical relevance for term rewriting systems, automated theorem provers and many AI-programming languages. The observation that unification under associativity and commutativity reduces to the solution of certain linear diophantine equations is the basis for a complete and minimal unification algorithm. The set of most general unfiers is closely related to the notion of a basis for the linear solution space of these equations.This result is extended to unification in free term algebras combined with Abelian semigroups.     

Equivalence of regular expressions over a partially commutative alphabet

The equivalence problem is considered for regular expressions over a partially commutative alphabet. The alphabet is decomposed into disjoint subsets of noncommutative elements. The special case of the problem when the cardinal number of only one subset is larger than 1 and the cardinal numbers of the other subsets are equal to 1 is proved to be algorithmically solvable. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 65–74, May–June 2009.     

Extension of Brzozowski’s derivation calculus of rational expressions to series over the free partially commutative monoids

We introduce an extension of the derivatives of rational expressions to expressions denoting formal power series over partially commuting variables. The expressions are purely noncommutative, however they denote partially commuting power series. The derivations (which are so-called -derivations) are shown to satisfy the commutation relations.Our main result states that for every so-called rigid rational expression, there exists a stable finitely generated submodule containing it. Moreover, this submodule is generated by what we call Words, that is by products of letters and of pure stars.Consequently this submodule is free and it follows that every rigid rational expression represents a recognizable series in . This generalizes the previously known property where the star was restricted to mono-alphabetic and connected series.     

On the relation between Context and Sequence Unification

Both Sequence and Context Unification generalize the same problem: Word Unification. Besides that, Sequence Unification solves equations between unranked terms involving sequence variables, and seems to be appealing for information extraction in XML documents, program transformation, knowledge representation, and rule-based programming. It is decidable. Context Unification deals with the same problem for ranked terms involving context variables, and has applications in computational linguistics and program transformation. Its decidability is a long-standing open question.In this work we study a relation between these two problems. We introduce a variant (restriction) of Context Unification, called Left-Hole Context Unification (LHCU), to which Sequence Unification is P-reduced: We define a partial currying procedure to translate Sequence Unification problems into Left-Hole Context Unification problems, and prove the soundness of the translation. Furthermore, a precise characterization of the shape of the unifiers allows us to easily reduce Left-Hole Context Unification to (the decidable problem of) Word Unification with Regular Constraints, obtaining then a new decidability proof for Sequence Unification. Finally, we define an extension of Sequence Unification (ESU) and, closing the circle, prove the inter-P-reducibility of LHCU and ESU.     

Implementing Nominal Unification

Nominal matching and unification underly the dynamics of nominal rewriting. Urban, Pitts and Gabbay gave a nominal unification algorithm which finds the most general solution to a nominal matching or unification problem, if one exists. Later the algorithm was extended by Fernández and Gabbay to deal with name generation and locality.In this paper we describe first a direct implementation of the nominal unification algorithm, including the extensions, in Maude. This implementation is not efficient (it is exponential in time), but we will show that we can obtain a feasible implementation by using termgraphs.     

一种新的模式合一算法

传统的模式合一,使用递归调用的方法,算法的时间复杂度是指数级的,因此,往往容易耗费大量的系统资源,从而造成系统的崩溃。为了解决这个问题,本文提出一种新的模式合一算法,共时间复杂度为线性的。实验结果表明,本算法可以有效地解决原来算法中存在的递归调用问题。     

Unification: A case-study in data refinement

In this paper, the Z notation is used to develop a small theory of terms and substitutions within which a simple unification algorithm can be specified and proved correct. Particular emphasis is placed on the use of Z's mathematical data types to simplify the development and structure of this theory. The correctness of an abstract version of the algorithm is proved first; this version operates on substitutions by composition. Then data refinement is used to show that the substitutions can be represented by binding functions that make composition a particularly efficient operation. The approach taken in this paper is compared with the approaches of three previous papers based on VDM.The contribution of this paper is to show how data refinement can be used to explain the design decisions behind a non-trivial program, and to provide a point of comparison between Z and VDM approaches to the same problem.     

Computing automorphisms of semigroups

In this paper an algorithm is presented that can be used to calculate the automorphism group of a finite transformation semigroup. The general algorithm employs a special method to compute the automorphism group of a finite simple semigroup. As applications of the algorithm all the automorphism groups of semigroups of order at most 7 and of the multiplicative semigroups of some group rings are found. We also consider which groups occur as the automorphism groups of semigroups of several distinguished types.     

由可精确测量元控制的弱可换的伪效应代数

主要研究了由可精确测量元控制的弱可换的伪效应代数中可精确测量元。证明了可精确测量元控制的弱可换的伪效应代数中可精确测量元是弱可换的伪正交代数代数。讨论了弱可换的伪效应代数与BZ-偏序集之间的关系。讨论了弱可换的伪效应代数商代数中可精确测量元与正规Riesz理想之间的关系。     

Unification under associativity and idempotence is of type nullary

It is shown, that there exist a unification problem〈s=t〉 _AI , for which the set of solutions under associativity and idempotence is not empty. But , the complete and minimal subset of this set of solutions does not exist, i.e.A+I is of type nullary. This is the first known standard first order theory with this unpleasant feature. This work is supported by the Deutsche Forschungsgemeinschaft, National Research Schema ‘Artificial Intelligence and Knowledge Based Systems’, SFB 314.     

Linearly ordered semigroups for fuzzy set theory

The fuzzy set theory initiated by Zadeh (Information Control 8:338–353, 1965) was based on the real unit interval [0,1] for support of membership functions with the natural product for intersection operation. This paper proposes to extend this definition by using the more general linearly ordered semigroup structure. As Moisil (Essais sur les Logiques non Chrysippiennes. Académie des Sciences de Roumanie, Bucarest, 1972, p. 162) proposed to define Lukasiewicz logics on an abelian ordered group for truth values set, we give a simple negative answer to the question on the possibility to build a Many-valued logic on a finite abelian ordered group. In a constructive way characteristic properties are step by step deduced from the corresponding set theory to the semigroup order structure. Some results of Clifford on topological semigroups (Clifford, A.H., Proc. Amer. Math. Soc. 9:682–687, 1958; Clifford, A.H., Trans. Amer. Math. Soc. 88:80–98, 1958), Paalman de Miranda work on I-semigroups (Paalman de Miranda, A.B., Topological Semigroups. Mathematical Centre Tracts, Amsterdam, 1964) and Schweitzer, Sklar on T-norms (Schweizer, B., Sklar, A., Publ. Math. Debrecen 10:69–81, 1963; Schweizer, B., Sklar, A., Pacific J. Math. 10:313–334, 1960; Schweizer, B., Sklar, A., Publ. Math. Debrecen 8:169–186, 1961) are revisited in this framework. As a simple consequence of Faucett theorems (Proc. Amer. Math. Soc. 6:741–747, 1955), we prove how canonical properties from the fuzzy set theory point of view lead to the Zadeh choice thus giving another proof of the representation theorem of T-norms. This structural approach shall give a new perspective to tackle the question of G. Moisil about the definition of discrete Many-valued logics as approximation of fuzzy continuous ones.      

Highly Constrained Unification Grammars

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In general, the recognition problem is undecidable for unification grammars. Even with restricted variants of the formalism, off-line parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity and allow for efficient processing. We first show that non-reentrant unification grammars generate exactly the class of context-free languages. We then relax the constraint and show that one-reentrant unification grammars generate exactly the class of mildly context-sensitive languages. We thus relate the commonly used and linguistically motivated formalism of unification grammars to more restricted, computationally tractable classes of languages.     

Competing for theAC-Unification Race

We describe our implementation of the unification algorithm for terms involving some associative-commutative operators plus free function symbols described by Boudetet al. The first goal of this implementation is efficiency, more precisely competing for theAC Unification Race. Although our implementation has been designed for good performance when applied to non-elementaryAC-unification problems, it is also very efficient on elementary problems. Our implementation, written in C and running on Sun workstations, is to be compared with the implementations in LISP, on Symbolics LIPS machines.     

Soft ideals and soft filters of soft ordered semigroups

It is shown that soft ordered semigroups over an ordered semigroup are actually soft ordered subsemigroups of (S,A). Soft idealistic semigroups over an ordered semigroup are soft ideals of soft ordered semigroup (S,A). The concept of soft filters of a soft ordered semigroup is introduced. It is shown that restricted complement of a soft filter is a soft prime ideal of (S,A).     

无对运算的无证书部分盲签名

由于对运算的计算量较大,结合新的无证书的公钥密码体制,提出一种无需对运算的无证书部分盲签名方案。采用随机预言机模型,分析了新方案的安全性,结果表明,新方案满足不可伪造性和部分盲性。新方案基于离散对数问题和计算性Diffie-Hellman（CDH）假设,计算开销明显优于其他无证书部分盲签名方案,可适用于移动电子商务。     

Efficient solution of some problems in free partially commutative monoids

Linear-time algorithms are presented for several problems concerning words in a partially commutative monoid, including whether one word is a factor of another and whether two words are conjugate in the monoid.     

RaRb Transformation of Compound Finite Automata over Commutative Rings

Some results on RaRb transformation of compound finite automata over finite field are generalized to the case of commutative rings.Properties of RaRb transformation are discussed and applied to the inversion problem for compound finite automata.