Symbolic Reasoning with Weighted and Normalized Decision Diagrams

Several variants of Bryant's ordered binary decision diagrams have been suggested in the literature to reason about discrete functions. In this paper, we introduce a generic notion of weighted decision diagrams that captures many of them and present criteria for canonicity. As a special instance of such weighted diagrams, we introduce a new BDD-variant for real-valued functions, called normalized algebraic decision diagrams. Regarding the number of nodes and arithmetic operations like addition and multiplication, these normalized diagrams are as efficient as factored edge-valued binary decision diagrams, while several other operators, like the calculation of extrema, minimum or maximum of two functions or the switch from real-valued functions to boolean functions through a given threshold, are more efficient for normalized diagrams than for their factored counterpart.     

Co-Algebraic Models for Quantitative Spatial Logics

We introduce a class of coalgebraic models and a family of modal logics that support the specification of spatial properties of distributed applications. The evaluation of a formula yields a value in a suitable multi-valued algebraic structure, giving a measure of the satisfaction of a requirement, induced by the decomposition of a system into subsystems, meant as available resources. As semantic domain we consider certain algebraic structures, called c-semirings, that allow us to generalize boolean logics to the multi-valued case, while keeping a number of the axioms of boolean algebras. Under suitable conditions on the structure of c-semirings, we show that, even if our logical formalisms are equipped with spatial operators, the interpretation of formulas fully characterizes bisimilarity.     

STR2: optimized simple tabular reduction for table constraints

Table constraints play an important role within constraint programming. Recently, many schemes or algorithms have been proposed to propagate table constraints and/or to compress their representation. In this paper, we describe an optimization of simple tabular reduction (STR), a technique proposed by J. Ullmann to dynamically maintain the tables of supports when generalized arc consistency (GAC) is enforced/maintained. STR2, the new refined GAC algorithm we propose, allows us to limit the number of operations related to validity checking and search of supports. Interestingly enough, this optimization makes simple tabular reduction potentially r times faster where r is the arity of the constraint(s). The results of an extensive experimentation that we have conducted with respect to random and structured instances indicate that STR2 is usually around twice as fast as the original STR, two or three times faster than the approach based on the hidden variable encoding, and can be up to one order of magnitude faster than previously state-of-the-art (generic) GAC algorithms on some series of instances. When comparing STR2 with the more recently developed algorithm based on multi-valued decision diagrams (MDDs), we show that both approaches are rather complementary.     

Data structures for symbolic multi-valued model-checking

Multi-valued logics provide an interesting alternative to classical boolean logic for modeling and reasoning about systems. Such logics can be used for reasoning about partially-specified systems, effectively encode vacuity detection and query-checking problems, help in detecting inconsistencies, and many others.In our earlier work, we identified a useful family of multi-valued logics: those specified over finite distributive lattices where negation preserves involution, i.e., for every element a of the logic. Such structures are called quasi-boolean algebras, and model-checking over these not only extends the domain of applicability of automated reasoning to new problems, but can also speed up solutions to some classical verification problems.Symbolic model-checking over quasi-boolean algebras can be cast in terms of operations over multi-valued sets: sets whose membership functions are multi-valued. In this paper, we propose and empirically evaluate several choices for implementing multi-valued sets with decision diagrams. In particular, we describe two major approaches: (1) representing the multi-valued membership function canonically, using MDDs or ADDs; (2) representing multi-valued sets as a collection of classical sets, using a vector of either MBTDDs or BDDs. The naive implementation of (2) includes having a classical set for each value of the algebra. We exploit a result of lattice theory to reduce the number of such sets that need to be represented.The major contribution of this paper is the evaluation of the different implementations of multi-valued sets, done via a series of experiments and using several case studies.

Improved Binary Space Partition merging

This paper presents a new method for evaluating boolean set operations between Binary Space Partition (BSP) trees. Our algorithm has many desirable features, including both numerical robustness and O(n) output sensitive time complexity, while simultaneously admitting a straightforward implementation. To achieve these properties, we present two key algorithmic improvements. The first is a method for eliminating null regions within a BSP tree using linear programming. This replaces previous techniques based on polygon cutting and tree splitting. The second is an improved method for compressing BSP trees based on a similar approach within binary decision diagrams. The performance of the new method is analyzed both theoretically and experimentally. Given the importance of boolean set operations, our algorithms can be directly applied to many problems in graphics, CAD and computational geometry.     

Sylvan: multi-core framework for decision diagrams

Decision diagrams, such as binary decision diagrams, multi-terminal binary decision diagrams and multi-valued decision diagrams, play an important role in various fields. They are especially useful to represent the characteristic function of sets of states and transitions in symbolic model checking. Most implementations of decision diagrams do not parallelize the decision diagram operations. As performance gains in the current era now mostly come from parallel processing, an ongoing challenge is to develop datastructures and algorithms for modern multi-core architectures. The decision diagram package Sylvan provides a contribution by implementing parallelized decision diagram operations and thus allowing sequential algorithms that use decision diagrams to exploit the power of multi-core machines. This paper discusses the design and implementation of Sylvan, especially an improvement to the lock-free unique table that uses bit arrays, the concurrent operation cache and the implementation of parallel garbage collection. We extend Sylvan with multi-terminal binary decision diagrams for integers, real numbers and rational numbers. This extension also allows for custom MTBDD leaves and operations and we provide an example implementation of GMP rational numbers. Furthermore, we show how the provided framework can be integrated in existing tools to provide out-of-the-box parallel BDD algorithms, as well as support for the parallelization of higher-level algorithms. As a case study, we parallelize on-the-fly symbolic reachability in the model checking toolset LTSmin. We experimentally demonstrate that the parallelization of symbolic model checking for explicit-state modeling languages, as supported by LTSmin, scales well. We also show that improvements in the design of the unique table result in faster execution of on-the-fly symbolic reachability.     

基于多值分解和多类标学习的分类框架设计

多值多类标的数据分类是研究一个样本不但同时属于多个类别,而且在某些属性下也可能存在多个取值的问题。提出了一种结合多值分解和多类标学习的多值多类标分类框架（MDML）,采用4种不同的多值分解策略,将问题转化为多类标问题,然后利用3种经典的多类标算法进行学习。实验结果表明,MDML与已有的多值多类标决策树算法相比,有效地提高了分类的性能,而且不同的组合方法适用于不同特点的数据集。     

Multiway Decision Graphs for Automated Hardware Verification

Traditional ROBDD-based methods of automated verification suffer from the drawback that they require a binary representation of the circuit. To overcome this limitation we propose a broader class of decision graphs, called Multiway Decision Graphs (MDGs), of which ROBDDs are a special case. With MDGs, a data value is represented by a single variable of abstract type, rather than by 32 or 64 boolean variables, and a data operation is represented by an uninterpreted function symbol. MDGs are thus much more compact than ROBDDs, and this greatly increases the range of circuits that can be verified. We give algorithms for MDG manipulation, and for implicit state enumeration using MDGs. We have implemented an MDG package and provide experimental results.     

How efficiently can room at the bottom be traded away for speed at the top?

Given exponential 2 ⁿ space, we know that an Adleman-Lipton computation can decide many hard problems – such as boolean formula and boolean circuit evaluation – in a number of steps that is linear in the problem size n. We wish to better understand the process of designing and comparing bio-molecular algorithms that trade away weakly exponential space to achieve as low a running time as possible, and to analyze the efficiency of their space and time utilization relative to those of their best extant classical/bio-molecular counterparts. We propose a randomized framework which augments that of the sticker model of Roweis et al. to provide an abstract setting for analyzing the space-time efficiency of both deterministic and randomized bio-molecular algorithms. We explore its power by developing and analyzing such algorithms for theCovering Code Creation (CCC) and k-SAT problems. In the process, we uncover new classical algorithms for CCC andk-SAT that, while exploiting the same space-time trade-off as the best previously known classical algorithms, are exponentially more efficient than them in terms of space-time product utilization. This work indicates that the proposed abstract bio-molecular setting for randomized algorithm design provides a logical tool of independent interest. This revised version was published online in June 2006 with corrections to the Cover Date.     

Mining minimal distinguishing subsequence patterns with gap constraints

Discovering contrasts between collections of data is an important task in data mining. In this paper, we introduce a new type of contrast pattern, called a Minimal Distinguishing Subsequence (MDS). An MDS is a minimal subsequence that occurs frequently in one class of sequences and infrequently in sequences of another class. It is a natural way of representing strong and succinct contrast information between two sequential datasets and can be useful in applications such as protein comparison, document comparison and building sequential classification models. Mining MDS patterns is a challenging task and is significantly different from mining contrasts between relational/transactional data. One particularly important type of constraint that can be integrated into the mining process is the gap constraint. We present an efficient algorithm called ConSGapMiner (Contrast Sequences with Gap Miner), to mine all MDSs satisfying a minimum and maximum gap constraint, plus a maximum length constraint. It employs highly efficient bitset and boolean operations, for powerful gap-based pruning within a prefix growth framework. A performance evaluation with both sparse and dense datasets, demonstrates the scalability of ConSGapMiner and shows its ability to mine patterns from high dimensional datasets at low supports.     

Boolean Expression Diagrams

This paper presents a new data structure called boolean expression diagrams (BEDs) for representing and manipulating Boolean functions. BEDs are a generalization of binary decision diagrams (BDDs) which can represent any Boolean circuit in linear space. Two algorithms are described for transforming a BED into a reduced ordered BDD. One is a generalized version of the BDD apply-operator while the other can exploit the structural information of the Boolean expression. This ability is demonstrated by verifying that two different circuit implementations of a 16-bit multiplier implement the same Boolean function. Using BEDs, this verification problem is solved efficiently, while using standard BDD techniques this problem is infeasible. Generally, BEDs are useful in applications, for example tautology checking, where the end-result as a reduced ordered BDD is small. Moreover, using operators for substitution and existential quantification they allow for the verification of large hierarchical circuits.     

基于双格的多值模型的精化关系与对称化简

多值模型是传统布尔模型的扩展。与布尔模型相比,多值模型更适合对包含不确定和不一致信息的软件系统进行建模。为了解决模型检测时的状态爆炸问题,研究了对基于双格的多值模型的对称化简方法。提出了一种新的多值模型的精化关系,证明其保持对[μ]演算公式的模型检测结果的正确性。定义多值模型的对称化简商结构,证明商结构与原模型之间存在互为精化的关系,因此对[μ]演算公式的模型检测在二者上可以得到相同的结果。     

An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints

A table constraint is explicitly represented as its set of solutions or non-solutions. This ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC expensive. In this paper, we address the space and time inefficiencies simultaneously by presenting the mddc constraint. mddc is a global constraint that represents its (non-)solutions with a multi-valued decision diagram (MDD). The MDD-based representation has the advantage that it can be exponentially smaller than a table. The associated GAC algorithm (called mddc) has time complexity linear to the size of the MDD, and achieves full incrementality in constant time. In addition, we show how to convert a positive or negative table constraint into an mddc constraint in time linear to the size of the table. Our experiments on structured problems, car sequencing and still-life, show that mddc is also a fast GAC algorithm for some global constraints such as sequence and regular. We also show that mddc is faster than the state-of-the-art generic GAC algorithms in Gent et al. (2007), Lecoutre and Szymanek (2006), Lhomme and Régin (2005) for table constraint.     

On problems without polynomial kernels

Kernelization is a strong and widely-applied technique in parameterized complexity. A kernelization algorithm, or simply a kernel, is a polynomial-time transformation that transforms any given parameterized instance to an equivalent instance of the same problem, with size and parameter bounded by a function of the parameter in the input. A kernel is polynomial if the size and parameter of the output are polynomially-bounded by the parameter of the input.In this paper we develop a framework which allows showing that a wide range of FPT problems do not have polynomial kernels. Our evidence relies on hypothesis made in the classical world (i.e. non-parametric complexity), and revolves around a new type of algorithm for classical decision problems, called a distillation algorithm, which is of independent interest. Using the notion of distillation algorithms, we develop a generic lower-bound engine that allows us to show that a variety of FPT problems, fulfilling certain criteria, cannot have polynomial kernels unless the polynomial hierarchy collapses. These problems include k-Path, k-Cycle, k-Exact Cycle, k-Short Cheap Tour, k-Graph Minor Order Test, k-Cutwidth, k-Search Number, k-Pathwidth, k-Treewidth, k-Branchwidth, and several optimization problems parameterized by treewidth and other structural parameters.     

Reflections on the virtues of modularity: a case study in linux security modules

Developing a modular system that properly supports a range of security models is challenging. The work presented here details our experiences with the modular Linux security framework called Linux Security Modules, or LSMs. Throughout our experiences we discovered that the developers of the LSM framework made certain tradeoffs for speed and simplicity during implementation, and consequently leaving the framework incomplete. Our experiences show at which points the theory of the LSM differs from reality, and details how these differences play out when developing and using a custom LSM. Copyright © 2009 John Wiley & Sons, Ltd.     

Achieving destination differentiation in ingress aggregated fairness for resilient packet rings by weighted destination based fair dropping

The IEEE 802.17 is a standardized ring topology network architecture, called the Resilient Packet Ring (RPR), to be used mainly in metropolitan and wide area networks. This paper introduces destination differentiation in ingress aggregated fairness for RPR and focuses on the RPR MAC client implementation of the IEEE 802.17 RPR MAC in the aggressive mode of operation. It also introduces an enhanced active queue management scheme for ring networks that achieves destination differentiation as well as higher overall utilization of the ring bandwidth with simpler and less expensive implementation than the generic implementation provided in the standard. The enhanced scheme introduced in this paper provides performance comparable to the per destination queuing implementation, which is the best achievable performance, while providing weighted destination based fairness as well as weighted ingress aggregated fairness. In addition, the proposed scheme has been demonstrated via extensive simulations to provide improved stability and fairness with respect to different packet arrival rates as compared to earlier algorithms.     

On-line Prediction and Conversion Strategies

We study the problem of deterministically predicting boolean values by combining the boolean predictions of several experts. Previous on-line algorithms for this problem predict with the weighted majority of the experts' predictions. These algorithms give each expert an exponential weight ^m where is a constant in [0, 1) andm is the number of mistakes made by the expert in the past. We show that it is better to use sums of binomials as weights. In particular, we present a deterministic algorithm using binomial weights that has a better worst case mistake bound than the best deterministic algorithm using exponential weights. The binomial weights naturally arise from a version space argument. We also show how both exponential and binomial weighting schemes can be used to make prediction algorithms robust against noise.     

Instance-Based Learning Algorithms

Storing and using specific instances improves the performance of several supervised learning algorithms. These include algorithms that learn decision trees, classification rules, and distributed networks. However, no investigation has analyzed algorithms that use only specific instances to solve incremental learning tasks. In this paper, we describe a framework and methodology, called instance-based learning, that generates classification predictions using only specific instances. Instance-based learning algorithms do not maintain a set of abstractions derived from specific instances. This approach extends the nearest neighbor algorithm, which has large storage requirements. We describe how storage requirements can be significantly reduced with, at most, minor sacrifices in learning rate and classification accuracy. While the storage-reducing algorithm performs well on several real-world databases, its performance degrades rapidly with the level of attribute noise in training instances. Therefore, we extended it with a significance test to distinguish noisy instances. This extended algorithm's performance degrades gracefully with increasing noise levels and compares favorably with a noise-tolerant decision tree algorithm.     

P-sufficient statistics for PAC learning k-term-DNF formulas through enumeration

Working in the framework of PAC-learning theory, we present special statistics for accomplishing in polynomial time proper learning of DNF boolean formulas having a fixed number of monomials. Our statistics turn out to be near sufficient for a large family of distribution laws – that we call butterfly distributions. We develop a theory of most powerful learning for analyzing the performance of learning algorithms, with particular reference to trade-offs between power and computational costs. Focusing attention on sample and time complexity, we prove that our algorithm works as efficiently as the best algorithms existing in the literature – while the latter only take care of subclasses of our family of distributions.