Rational Unification in 28 Characters

We present a case study where Synchronising Graphs, a system of parallel graph transformation, are used to solve the syntactic unification problem for first order rational terms (with possibly infinite unifier). The solution we offer is efficient, that is quasi-linear, and simple: a program of 28 characters.     

Short Single Axioms for Boolean Algebra

We present short single equational axioms for Boolean algebra in terms of disjunction and negation and in terms of the Sheffer stroke. Previously known single axioms for these theories are much longer than the ones we present. We show that there is no shorter axiom in terms of the Sheffer stroke. Automated deduction techniques were used in several parts of the work.     

A note on the parallel complexity of anti-unification

The anti-unifier is the dual notion to the unifier, i.e., it is the most specific term that has the input terms as instances. We show that the problem of anti-unification is in NC, in contrast to unification that is known to be P-complete.     

布尔函数与扩散码的组合安全性

本文对扩散码密码体制中多列扩散码组合对布尔函数次数的影响进行了探讨,引入了单项,、多项和函数的组合约化的概念,搪塞了组合约化的条件,给出了在扩散码列的任意线性组合下布尔函数ｒ次可约性的检验方法,并获得了一个布尔函数和扩散码的充分条件,在这个条件下对任意的线性组合布尔函数的次数不低于ｒ,文末给出了说明检验方法的实例。     

Context unification with one context variable

The context unification problem is a generalization of standard term unification. It consists of finding a unifier for a set of term equations containing first-order variables and context variables. In this paper we analyze the special case of context unification where the use of at most one context variable is allowed and show that it is in NP. The motivation for investigating this subcase of context unification is interprocedural program analysis for programs described using arbitrary terms, generalizing the case where terms were restricted to using unary function symbols. Our results imply that the redundancy problem is in coNP, and that the finite redundancy property holds in this case. We also exhibit particular cases where one context unification is polynomial.     

Formal Correctness of a Quadratic Unification Algorithm

We present a case study using ACL2 to verify a nontrivial algorithm that uses efficient data structures. The algorithm receives as input two first-order terms, and it returns a most general unifier of these terms if they are unifiable, failure otherwise. The verified implementation stores terms as directed acyclic graphs by means of a pointer structure. Its time complexity is and its space complexity , and it can be executed in ACL2 at a speed comparable to a similar C implementation. We report the main issues encountered to achieve this formally verified implementation. This work has been supported by project TIN2004-03884 (Ministerio de Educación y Ciencia, Spain) and FEDER funds.     

Arithmetic Boolean Expression Manipulator Using BDDs

Recently, there has been a lot of works on LSI design systems using Binary Decision Diagrams (BDDs), which are efficient representations of Boolean functions. We previously developed a Boolean expression manipulator, that can quickly calculate Boolean expressions by using BDD techniques. It has greatly assisted us in developing VLSI design systems and solving combinatorial problems.In this paper, we present an Arithmetic Boolean Expression Manipulator (BEM-II), that is also based on BDD techniques. BEM-II calculates Boolean expressions that contain arithmetic operations, such as addition, subtraction, multiplication and comparison, and then displays the results in various formats. It can solve problems represented by a set of equalities and inequalities, which are dealt with in 0-1 linear programming. We discuss the algorithm and data structure used for manipulating arithmetic Boolean expressions and show the formats used for displaying the results.The specifications for BEM-II are described and several application examples are presented. Arithmetic Boolean expressions will be useful for various applications. They perform well in terms of the total time for programming and execution. We expect BEM-II to facilitate research and development of digital systems.     

Deterministic second-order patterns

Second-order patterns, together with second-order matching, enable concise specification of program transformation, and have been implemented in several program transformation systems. However, second-order matching in general is nondeterministic, and the matching algorithm is so expensive that the matching is NP-complete. It is orthodox to impose constraints on the form of higher-order patterns so as to obtain the desirable matches satisfying certain properties such as decidability and finiteness. In the context of unification, Miller's higher-order patterns have a single most-general unifier. In this paper, we relax the restriction of his patterns without changing determinism in the context of matching instead of unification. As a consequence, our deterministic second-order patterns cover a wide class of useful patterns for program transformation. The time-complexity of our deterministic matching algorithm is linear in the size of a term for a fixed pattern.     

电路宽度制导的布尔推理

在基于逻辑电路的布尔推理过程中，经常用到二又判决图(BDD)与布尔可满足性(SAT)相结合的算法．由于电路宽度能很好地反映电路的复杂性，提出了一种基于电路宽度的启发式策略，根据电路宽度来实现SAT算法与BDD算法的交替．充分发挥两者的优势，不仅可以防止因构造BDD可能导致的内存爆炸，而且还能避免SAT算法可能遇到的超时现象．与以往同类策略相比，该启发式策略更节省计算资源，提高算法性能．针对组合电路的测试产生实验，证实了其在布尔推理中的效率．     

Symbolic Configuration for Interactive Container Ship Stowage Planning

Low‐cost containerized shipping requires high‐quality stowage plans. Scalable stowage planning optimization algorithms have been developed recently. All of these algorithms, however, produce monolithic solutions that are hard for stowage coordinators to modify, which is necessary in practice owing to exceptions and operational disruptions. This article introduces an approach for modifying a stowage plan interactively without breaking its constraints. We focus on rearranging the containers in a single‐bay section and show two approaches for providing complete and backtrack‐free decision support using symbolic configuration techniques, one based on binary decision diagrams and one based on DPLL solvers. We show that binary decision diagrams can be used to solve real‐world sized instances of a single bay, and that search‐based solvers can be used to solve simplified instances going beyond a single bay.     

Unification in sort theories and its applications

In this article we investigate the properties of unification in sort theories. A sort is represented by a set of monadic predicates, called sort symbols. Sorts are attached to variables restricting their respective domain to the intersection of the denotations of the sort symbols. A sort theory consists of a set of declarations that are atoms starting with a sort symbol. Two terms are unifiable with respect to some sort theory, if they are unifiable in the standard sense and the assignments of the unifier do respect the declarations in the sort theory. Therefore, the new sorted unification algorithm is formed by standard unification augmented by extra rules that consider the information in the sort theory. We prove the new sorted unification algorithm to be correct and complete and establish complexity results for several different, syntactically characterized sort theories. The notions of a sort and a sort theory are developed in such a way that sort symbols are used like ordinary monadic predicate symbols. To this end, sorts may denote empty sets, and the sort theory is not a static part of the signature. It may dynamically change during a deduction process. The applicability of the approach is demonstrated for the resolution and the tableau calculus.     

An Algorithm for the Retrieval of Unifiers from Discrimination Trees

We present a modification of the unification algorithm that is adapted to the extraction of simultaneously unifiable literals from discrimination trees. The algorithm is useful for efficient implementation of binary resolution, hyperresolution, and paramodulation. The algorithm is able to traverse simultaneously more than one discrimination tree and to construct a unifier at the same time. In this way backtracking is reduced.     

Implementing Valiant's Learnability Theory Using Random Sets

A general learning framework which uses random sets is introduced for solving discrete-space classification problems. This framework is based on the pac-learning formalism introduced by Valiant (1984) and generalized in set-theoretic terms by Blumer, et al., (1989). The random set version of this theory is used to develop an algorithm which is a particularly efficient search scheme. This is accomplished by recasting the representational class and constructive proof presented in Valiant (1984) into random set terms and implementing it as an exhaustive search algorithm. The algorithm is a problem-specific incremental (psi) approach in that it satisfies learnability criteria for distribution-specific problems as examples are being sampled. Some theoretical and empirical analyses are presented to demonstrate the convergent pac-learnability and sample complexity of this psi-algorithm. Its performance is then tested on the multiplexor class of problems. This class has been analyzed by others as a benchmark for decision trees and genetic classifiers. Results from these test cases show that, despite using an exhaustive search, this random set implementation is computationally competitive with these more established methods (which use empirically proven heuristics). Conclusions are drawn about potential further improvements in the efficiency of this approach.     

Boolean Functions as Models for Quantified Boolean Formulas

In this paper, we introduce the notion of models for quantified Boolean formulas. For various classes of quantified Boolean formulas and various classes of Boolean functions, we investigate the problem of determining whether a model exists. Furthermore, we show for these classes the complexity of the model checking problem, which is to check whether a given set of Boolean functions is a model for a formula. For classes of Boolean functions, we establish some characterizations in terms of classes of quantified Boolean formulas that have such a model. This research has been supported in part by the Air Force Office of Scientific Research under grant FA9550-06-1-0050. This research has been supported in part by the NSFC under grants 60573011 and 10410638.     

Identification of partial disjunction, parity, and threshold functions

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.     

Protecting data privacy through hard-to-reverse negative databases

A set DB of data elements can be represented in terms of its complement set, known as a negative database. That is, all of the elements not in DB are represented, and DB itself is not explicitly stored. This method of representing data has certain properties that are relevant for privacy enhancing applications. The paper reviews the negative database (NDB) representation scheme for storing a negative image compactly, and proposes using a collection of NDBs to represent a single DB, that is, one NDB is assigned for each record in DB. This method has the advantage of producing negative databases that are hard to reverse in practice, i.e., from which it is hard to obtain DB. This result is obtained by adapting a technique for generating hard-to-solve 3-SAT formulas. Finally we suggest potential avenues of application.     

基于二元语义一致性的混合多属性灰关联决策

为了解决指标权重未知的混合型多属性决策问题, 提出基于二元语义一致性的灰关联决策方法. 首先, 针对异质决策信息问题, 提出了使所有决策信息转化为二元语义变量的一致化方法; 然后根据离差最大化原理, 客观确定属性的指标权重, 利用灰关联分析对决策方案进行排序; 最后以某供应链中供应商的绩效评估作为算例, 用所提出方法对混合型多属性决策问题进行求解, 结果表明该方法易于操作且可为决策者提供丰富的决策信息.

     

Permutation equivalence of cubic rotation symmetric Boolean functions

Rotation symmetric Boolean functions have been extensively studied for about 15 years because of their applications in cryptography and coding theory. Until recently little was known about the basic question of when two such functions are affine equivalent. The simplest case of quadratic rotation symmetric functions which are generated by cyclic permutations of the variables in a single monomial was only settled in 2009. For the much more complicated case of cubic rotation symmetric functions generated by a single monomial, the affine equivalence classes under permutations which preserve rotation symmetry were determined in 2011. It was conjectured then that the cubic equivalence classes are the same if all nonsingular affine transformations, not just permutations, are allowed. This conjecture is probably difficult, but here we take a step towards it by proving that the cubic affine equivalence classes found in 2011 are the same if all permutations, not just those preserving rotation symmetry, are allowed. The needed new idea uses the theory of circulant matrices.     

A Shortest 2-Basis for Boolean Algebra in Terms of the Sheffer Stroke

In this article, we present a short 2-basis for Boolean algebra in terms of the Sheffer stroke and prove that no such 2-basis can be shorter. We also prove that the new 2-basis is unique (for its length) up to applications of commutativity. Our proof of the 2-basis was found by using the method of proof sketches and relied on the use of an automated reasoning program. This revised version was published online in August 2006 with corrections to the Cover Date.     

Path Sensitization

For different delay models,the concept of sensitization can be very different.Traditonal concepts of sensitization cannot precisely describe circuit behavior when the input vectors change very fast.Using Boolean process aporoach,this paper presents a new definition of sensitization for arbitrary input waveforms.By this new concept it is found that if the inputs of a combinational circuit can change at any time,and each gate‘s delay varies within an interval (bounded gate delay model),then every path,which is not necessarily a single topological path,is sensitizable.From the experimental results it can be seen that,all nonsensitizable paths for traditional concepts actually can propagate transitions along them for some input waveforms.However,specified time between input transitions(STBIT) and minimum permissible pulse width(ε）are two major factors to make some paths non-sensitizable.