Encoding RTL Constructs for MathSAT: a Preliminary Report

Formal checking at Register-Transfer Level (RTL) is currently a fundamental step in the design of hardware circuits. Most tools for formal checking, however, work at the boolean level, which is not expressive enough to capture the abstract, high level (e.g., structural, word level) information of RTL designs. Tools for formal checking are thus confronted with problems which are “flattened” down to boolean level, so that a predominant part of their computational effort is wasted in performing useless boolean search on the bitwise encoding of integer data and arithmetical operations. In this paper we present a way of encoding RTL constructs into SMT formulas, that is, boolean combinations of boolean variables and quantifier-free constraints in Integer Linear Arithmetic. Such formulas can be handled by the MathSAT tool (and others) directly, without flattening to boolean level, so that to reduce drastically the computational effort.We propose a mixed boolean/ILP encoding, in which control variables are encoded as boolean variables, datapath variables as integer variables; control constructs are handled as boolean combination of control variables and predicates over datapath variables, and datapath constructs are encoded, as much as possible, as linear arithmetical constraints over datapath variables.     

Exact Learning of Formulas in Parallel

We investigate the parallel complexity of learning formulas from membership and equivalence queries. We show that many restricted classes of boolean functions cannot be efficiently learned in parallel with a polynomial number of processors.     

A Constant-Space Sequential Model of Computation for First-Order Logic

We define and justify a natural sequential model of computation with a constant amount of read/write work space, despite unlimited (polynomial) access to read-only input and write-only output. The model is deterministic, uniform, and sequential. The constant work space is modeled by a finite number of destructively read boolean variables, assignable by formulas over the canonical boolean operations. We show that computation on this model is equivalent to expressibility in first-order logic, giving a duality between (read-once) constant-space serial algorithms and constant-time parallel algorithms.     

Spectral Transforms for Large Boolean Functions with Applications to Technology Mapping

The Walsh transform has numerous applications in computer-aided design, but the usefulness of these techniques in practice has been limited by the size of the boolean functions that can be transformed. Currently available techniques limit the functions to less than 20 variables. In this paper, we show how to compute concise representations of the Walsh transform for functions with several hundred variables. We have applied our techniques to boolean technology mapping and, in certain cases, we obtained a speed up of as much as 50% for the matching phase.     

基于自变量是非均匀分布的多输出布尔函数的特征值研究

研究了自变量是非均匀分布的多输出函数的特征值,并且给出了无偏函数和t—弹性函数的特征值的计算公式和上界。     

Theory of fault-based predicate testing for computer programs

Predicates appear in both the specification and implementation of a program. One approach to software testing, referred to as predicate testing, is to require certain types of tests for a predicate. In this paper, three fault-based testing criteria are defined for compound predicates, which are predicates with one or more AND/OR operators. BOR (boolean operator) testing requires a set of tests to guarantee the detection of (single or multiple) boolean operator faults, including incorrect AND/OR operators and missing/extra NOT operators. BRO (boolean and relational operator) testing requires a set of tests to guarantee the detection of boolean operator faults and relational operator faults (i.e., incorrect relational operators). BRE (boolean and relational expression) testing requires a set of tests to guarantee the detection of boolean operator faults, relational operator faults, and a type of fault involving arithmetical expressions. It is shown that for a compound predicate with n, n>0, AND/OR operators, at most n+2 constraints are needed for BOR testing and at most 2*n+3 constraints for BRO or BRE testing, where each constraint specifies a restriction on the value of each boolean variable or relational expression in the predicate. Algorithms for generating a minimum set of constraints for BOR, BRO, and BRE testing of a compound predicate are given, and the feasibility problem for the generated constraints is discussed. For boolean expressions that contain multiple occurrences of some boolean variables, how to combine BOR testing with the meaningful impact strategy (Weyuker et al., 1994) is described     

Knowledge Representation

Abstract

In this semi-expository note, we first recall that every boolean function f of n variables is determined uniquely by a certain subset S of the nodes of the hypercube Q". We then propose the subgraph of Q_n induced by S as a realization of f, and call it the graph of a boolean function. We observe that boolean functions of the same type always have the same graph, but the converse does not hold. We conclude with the open question which suggests itself from a confrontation of the disjunctive and conjunctive normal forms of a boolean function.     

Implementation of supervisory control using extended finite-state machines

This article aims at bridging the gap between traditional designs to discrete-event control problems and supervisory control theory of Ramadge and Wonham. We propose to implement supervisory control by extending the plant's finite state machine with Boolean variables, guard formulas and updating functions. Boolean variables are used to encode the supervisor's states, event observation is captured by a set of Boolean functions that update the value of variables, and control is introduced by guarding events with Boolean formulas. The framework developed in this work is fundamental in our ongoing research on communication between supervisors in a distributed discrete-event system.     

基于量化布尔公式的条件规划编码方式

介绍条件规划问题及其相关的求解系统,着重分析以逻辑为基拙的编码方式。针对基于量化布尔公式的转换方法进行详细分析,给出3种不同形式的量化布尔公式编码。最后,对这3种编码进行比较,分析基于命题逻辑公式与量化布尔公式这两种不同转换方式的优劣,讨论基于量化布尔公式的规划方法未来的研究方向和发展趋势。     

Best approximations of fitness functions of binary strings

Fitness functions of binary strings (pseudo-boolean functions) canbe represented as polynomials over a set of boolean variables. Weshow that any such function has a unique best approximation in thelinear span of any subset of polynomials. For example, there is aunique best linear approximation and a unique best quadraticapproximation. The error of an approximation here isroot-mean-squared error. If all the details of the function to beapproximated are known, then the approximation can be calculateddirectly. Of more practical importance, we give a method for usingsampling to estimate the coefficients of the approximation, anddescribe its limitations.     

Nonadaptive quantum query complexity

We study the power of nonadaptive quantum query algorithms, which are algorithms whose queries to the input do not depend on the result of previous queries. First, we show that any bounded-error nonadaptive quantum query algorithm that computes a total boolean function depending on n variables must make Ω(n) queries to the input in total. Second, we show that, if there exists a quantum algorithm that uses k nonadaptive oracle queries to learn which one of a set of m boolean functions it has been given, there exists a nonadaptive classical algorithm using queries to solve the same problem. Thus, in the nonadaptive setting, quantum algorithms for these tasks can achieve at most a very limited speed-up over classical query algorithms.     

On Similarity Measures for Multimedia Database Applications

A multimedia database query consists of a set of fuzzy and boolean (or crisp) predicates, constants, variables, and conjunction, disjunction, and negation operators. The fuzzy predicates are evaluated based on different media criteria, such as color, shape, layout, keyword. Since media-based evaluation yields similarity values, results to such a query is defined as an ordered set. Since many multimedia applications require partial matches, query results also include tuples which do not satisfy all predicates. Hence, any fuzzy semantics which extends the boolean semantics of conjunction in a straight forward manner may not be desirable for multimedia databases. In this paper, we focus on the problem of ‘given a multimedia query which consists of multiple fuzzy and crisp predicates, how to provide the user with a meaningful overall ranking.’ More specifically, we study the problem of merging similarity values in queries with multiple fuzzy predicates. We describe the essential multimedia retrieval semantics, compare these with the known approaches, and propose a semantics which captures the retrieval requirements in multimedia databases. Received 13 August 1999 / Revised 13 May 2000 / Accepted in revised form 26 July 2000     

Domain Extension of Isothetic Polyhedra with Minimal CSG Representation

We consider the problem of converting boundary representations of isothetic polyhedra into constructive solid geometry (CSG) representations. The CSG representation is a boolean formula based on the half-spaces supporting the faces of the polyhedron. This boolean formula exhibits two important features: no term is complemented (it is monotone) and each supporting half-space appears in the formula once and only once. It is known that such formulas do not always exist for general polyhedra in the three-dimensional space. In this work first we give a procedure that extends the domain of polyhedra for which such a nice representation can be computed. Then we prove that not all cyclic isothetic polyhedra have a CSG representation of the style given above.     

Evaluating Boolean function with random variables

The paper considers the determination of the value of a boolean function by examining its variable. The function's value is deterministically determined by the variables which arc binary and random. A sequential testing procedure of the variables is presented. It is shown that this procedure minimizes the expected number of necessary tests for some classes of functions and probably do so for others. The presence of such problem is described in file searching, reliability systems, switching circuits and graph connectivity.     

Clouds,Fuzzy Sets,and Probability Intervals

Clouds are a concept for uncertainty mediating between the concept of a fuzzy set and that of a probability distribution. A cloud is to a random variable more or less what an interval is to a number. We discuss the basic theoretical and numerical properties of clouds, and relate them to histograms, cumulative distribution functions, and likelihood ratios.We show how to compute nonlinear transformations of clouds, using global optimization and constraint satisfaction techniques. We also show how to compute rigorous enclosures for the expectation of arbitrary functions of random variables, and for probabilities of arbitrary statements involving random variables, even for problems involving more than a few variables.Finally, we relate clouds to concepts from fuzzy set theory, in particular to the consistent possibility and necessity measures of Jamison and Lodwick.     

Negative Results for Equivalence Queries

We consider the problem of exact identification of classes of concepts using only equivalence queries. We define a combinatorial property,approximate fingerprints, of classes of concepts and show that no class with this property can be exactly identified in polynomial time using only equivalence queries. As applications of this general theorem, we show that there is no polynomial time algorithm using only equivalence queries that exactly identifies deterministic or nondeterministic finite state acceptors, context free grammars, or disjunctive or conjunctive normal form boolean formulas.     

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of computer networks, is the problem of partitioning a given graph into a maximum number of disjoint dominating sets. This number is called the domatic number of the graph. We prove that the problem of determining whether or not the domatic number of a given graph is exactly one of k given values is complete for BH_2k(NP), the 2kth level of the boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not the domatic number of a given graph equals exactly a given integer. Note that DP = BH₂(NP). We obtain similar results for the exact versions of generalized dominating set problems and of the conveyor flow shop problem. Our reductions apply Wagner's conditions sufficient to prove hardness for the levels of the boolean hierarchy over NP.     

粗集中上下近似运算的逻辑性质

1 引论近年来,粗集理论的实际应用与理论探讨已成为计算机科学中的一个热点问题。1995年Pawlak曾在文[6]中指出,粗集的逻辑性质研究将是今后粗集理论的一个重要同题。本文正是通过深入研究拓扑布尔代数与粗集的关系,给出了关于有限拓扑布尔代数的表示定理,从逻辑上全面刻画了粗集中上下近似运算这一核心概念。