Quantitative and qualitative analysis of SysML activity diagrams

Model-driven engineering refers to a range of approaches that uses models throughout systems and software development life cycle. Towards sustaining such a successful approach in practice, we present a model-based verification framework that supports the quantitative and qualitative analysis of SysML activity diagrams. To this end, we propose an algorithm that maps SysML activity diagrams into Markov decision processes expressed using the language of the probabilistic symbolic model checker PRISM. Furthermore, we elaborate on the correctness of our translation algorithm by proving its soundness with respect to a SysML activity diagrams operational semantics that we also present in this work. The generated models can be verified against a set of properties expressed in the probabilistic computation tree logic. To automate our approach, we developed a prototype tool that interfaces a modeling environment and the probabilistic model checker. We also show how to leverage adversary generation to provide the developer with a useful counterexample/witness as a feedback on the verified properties. Finally, the established theoretical foundations are complemented with an illustrative case study that demonstrates the usability and benefit of such a framework.     

二叉决策图在逻辑综合中的应用

二叉决策图（BDDs）是布尔函数的一个表示方法，最近它被广泛于逻辑综合、布尔电路的模拟和测试等领域。在这些应用中，有些基本问题需要解决，其中包括电路图到决策图的转换。本文提出一个转换的方法。文中分两步叙述，首先是对无扇出电路的转换，然后是对有扇出电路的转换，最后把两者结合为一个通用算法。     

p-Automata: New foundations for discrete-time probabilistic verification

We introduce p-Automata, which are automata that accept languages of Markov chains, by adapting notions and techniques from alternating tree automata to the realm of Markov chains. The set of languages of p-automata is closed under Boolean operations, and for every PCTL formula it contains the language of the set of models of the formula. Furthermore, the language of every p-automaton is closed under probabilistic bisimulation. Similar to tree automata, whose acceptance is defined via two-player games, we define acceptance of Markov chains by p-automata through two-player stochastic games. We show that acceptance is solvable in EXPTIME; but for automata that arise from PCTL formulas acceptance matches that of PCTL model checking, namely, linear in the formula and polynomial in the Markov chain. We also derive a notion of simulation between p-automata that approximates language containment in EXPTIME and is complete for Markov chains. These foundations therefore enable abstraction-based probabilistic model checking for probabilistic specifications that subsume Markov chains, and LTL and CTL* like logics.     

Query evaluation over probabilistic XML

Query evaluation over probabilistic XML is explored. The queries are twig patterns with projection, and the data is represented in terms of three models of probabilistic XML (that extend existing ones in the literature). The first model makes an assumption of independence among the probabilistic junctions, whereas the second model can encode probabilistic dependencies. The third model combines the first two and, hence, is the most general. An efficient algorithm (under data complexity) is given for query evaluation in the first model. In addition, various optimizations are proposed, and their effectiveness is shown both analytically and experimentally. For the other two models, it is shown that every query is either intractable or trivial. Nonetheless, efficient (additive and multiplicative) approximation algorithms are given for these two models. Finally, Boolean queries are enriched by allowing disjunctions and negations of branches. The above algorithm for the first model is extended to handle these queries. For the other two models, there is an efficient additive approximation, and a multiplicative one also exists if there is no negation; in addition, it is shown that if the query is non-monotonic, then no efficient multiplicative approximation exists unless NP = RP.     

Learning symmetric causal independence models

Causal independence modelling is a well-known method for reducing the size of probability tables, simplifying the probabilistic inference and explaining the underlying mechanisms in Bayesian networks. Recently, a generalization of the widely-used noisy OR and noisy AND models, causal independence models based on symmetric Boolean functions, was proposed. In this paper, we study the problem of learning the parameters in these models, further referred to as symmetric causal independence models. We present a computationally efficient EM algorithm to learn parameters in symmetric causal independence models, where the computational scheme of the Poisson binomial distribution is used to compute the conditional probabilities in the E-step. We study computational complexity and convergence of the developed algorithm. The presented EM algorithm allows us to assess the practical usefulness of symmetric causal independence models. In the assessment, the models are applied to a classification task; they perform competitively with state-of-the-art classifiers.     

Symbol recognition in electrical diagrams using probabilistic graph matching

In this paper a method is proposed to recognize symbols in electrical diagrams based on probabilistic matching. The skeletons of the symbols are represented by graphs. After finding the pose of the graph (orientation, translation, scale) by a bounded search for a minimum error transformation, the observed graph is matched to the class models and the likelihood of the match is calculated. Results are given for computer-generated symbols and hand drawn symbols with and without a template. Error rates range from <1% to 8%.     

Mod-2-OBDDs—A data structure that generalizes EXOR-sum-of-products and ordered binary decision diagrams

We present a data structure for Boolean manipulation-the Mod-2-OBDDs-that considerably extends ESOPs (EXOR-sum-of-products) as well as OBDDs (ordered binary decision diagrams). There are Boolean functions of practical interest which have exponential size optimal ESOPs (even multilevel EXOR-expressions) and/or OBDDs that can be represented by (low degree) polynomial size Mod-2-OBDDs. We show that Boolean manipulation tasks such as apply operation, quantification, composition can be performed with Mod-2-OBDDs at least as efficient as with OBDDs. Indeed, since the size of a minimal Mod-2-OBDD-representation of a Boolean function is, in general, smaller (sometimes even exponentially smaller) than the size of an optimal OBDD-representation, the increase in efficiency is considerable. Moreover, EXOR-operations as well as complementations can be performed in constant timeO (1). However, the price of constant time EXOR-apply operations is the canonicity of the Mod-2-OBDD-representation. In order to allow in spite of this fact efficient analysis of Mod-2-OBDDs we present a fast probabilistic equivalence test with one-sided error probability for Mod-2-OBDDs (and, hence, for ESOPs) which performs only linear many arithmetic operations.     

概率计算树逻辑的限界模型检测

为了缓解概率计算树逻辑模型检测中的状态空间爆炸问题,提出了概率计算树逻辑的限界模型检测技术.该技术首先定义概率计算树逻辑的限界语义,并证明其正确性;之后,通过实例说明在传统限界模型检测中,以路径长度作为判断检测过程终止的标准已经失效,基于数值计算中牛顿迭代法的终止准则,设计了新的终止判断标准;然后提出基于线性方程组求解的限界模型检测算法;最后,通过3个测试用例说明,概率计算树逻辑限界模型检测方法在反例较短的情况下能够快速完成检测过程,而且比概率计算树逻辑的无界模型检测算法所需求得的状态空间要少.     

Boolean representation of bounded BCK-algebras

We define the Boolean center and the Boolean skeleton of a bounded BCK-algebra, and we use the Boolean skeleton to obtain a representation of bounded BCK-algebras, called (weak) Pierce -representation, as (weak) Boolean products of bounded BCK-algebras. We analyze the cases in which the stalks in these representations are directly indecomposable, finitely subdirectly irreducible or simple algebras. We give some examples of algebras and relative subvarieties of bounded BCK-algebras to illustrate the results.     

Isomorphism for Graphs of Bounded Distance Width

In this paper we study the GRAPH ISOMORPHISM problem on graphs of bounded treewidth, bounded degree, or bounded bandwidth. GRAPH ISOMORPHISM can be solved in polynomial time for graphs of bounded treewidth, pathwidth, or bandwidth, but the exponent depends on the treewidth, pathwidth, or bandwidth. Thus, we look for special cases where ``fixed parameter tractable' polynomial time algorithms can be established. We introduce some new and natural graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve GRAPH ISOMORPHISM in O(n ² ) time for graphs with bounded rooted path distance width, and in O(n ³ ) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is NP-hard, but both path and tree distance width can be computed in O(n ^k+1 ) time, when they are bounded by a constant k; the rooted path or tree distance width can be computed in O(ne) time. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters. Received February 18, 1997; revised February 23, 1998.     

Decision-diagram-based techniques for bounded reachability checking of asynchronous systems

Bounded reachability analysis and bounded model checking are widely believed to perform poorly when using decision diagrams instead of SAT procedures. Recent research suggests this to be untrue with regards to synchronous systems and, in particular, digital circuits. This article shows that the belief is also a myth for asynchronous systems, such as models specified by Petri nets. We propose several Bounded Saturation approaches to compute bounded state spaces using decision diagrams. These approaches are based on the established Saturation algorithm, which benefits from a non-standard search strategy that is very different from breadth-first search, but employ different flavors of decision diagrams: multi-valued decision diagrams, edge-valued decision diagrams, and algebraic decision diagrams. We apply our approaches to studying deadlock as a safety property. Our extensive benchmarking shows that our algorithms often, but not always, compare favorably against two SAT-based approaches that are advocated in the literature. Research supported by the NSF under grants CNS-0501747 and CNS-0501748 and by the EPSRC under grant GR/S86211/01. An extended abstract of this article appeared in the proceedings of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), LNCS~4424, pp.~648–663, 2007, Springer.     

The Satisfiability Problem for Probabilistic Ordered Branching Programs

We show that the satisfiability problem for bounded-error probabilistic ordered branching programs is \NP -complete. If the error is very small, however (more precisely, if the error is bounded by the reciprocal of the width of the branching program), then we have a polynomial-time algorithm for the satisfiability problem. Received March 17, 2001, and in final form July 19, 2001. Online publication October 30, 2001.     

An algorithm for visible-line and visible-surface display of CSG models

An algorithm is presented for display of Constructive Solid Geometry (CSG) models, in which Boolean evaluation of a model is done during image generation only for the visible parts of the model.The algorithm is based on Atherton's CSG scan-line algorithm. It involves, however, dividing the image plane into strips of varying width, inside which areas are determined where only one face is visible. This may involve subdivision of an area into smaller areas.Two versions of the algorithm are presented: an efficient visible-line version for a raster display, and a visible-surface version, which turns out to be an improved variant for simple models of Atherton's algorithm.Sample images and CPU times for some models are given to show the efficiency of the algorithm.     

Labeling Points with Weights

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually referred to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups: fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for labeling n points with unit-height rectangles. We show how an O(n\log n)-time factor-2 approximation algorithm and a PTAS for fixed-position models can be extended to handle the weighted case. Our main contribution is the first algorithm for weighted sliding labels. Its approximation factor is (2+\varepsilon), it runs in O(n ²/\varepsilon) time and uses O(n/\varepsilon) space. We show that other than for fixed-position models even the projection to one dimension remains NP-hard. For slider models we also investigate some special cases, namely (a) the number of different point weights is bounded, (b) all labels are unit squares, and (c) the ratio between maximum and minimum label height is bounded.     

Labeling Points with Weights

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually referred to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups: fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for labeling n points with unit-height rectangles. We show how an O(n\log n)-time factor-2 approximation algorithm and a PTAS for fixed-position models can be extended to handle the weighted case. Our main contribution is the first algorithm for weighted sliding labels. Its approximation factor is (2+\varepsilon), it runs in O(n ²/\varepsilon) time and uses O(n/\varepsilon) space. We show that other than for fixed-position models even the projection to one dimension remains NP-hard. For slider models we also investigate some special cases, namely (a) the number of different point weights is bounded, (b) all labels are unit squares, and (c) the ratio between maximum and minimum label height is bounded.     

Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

Valiant (1984) and others have studied the problem of learning various classes of Boolean functions from examples. Here we discuss incremental learning of these functions. We consider a setting in which the learner responds to each example according to a current hypothesis. Then the learner updates the hypothesis, if necessary, based on the correct classification of the example. One natural measure of the quality of learning in this setting is the number of mistakes the learner makes. For suitable classes of functions, learning algorithms are available that make a bounded number of mistakes, with the bound independent of the number of examples seen by the learner. We present one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions. The basic method can be expressed as a linear-threshold algorithm. A primary advantage of this algorithm is that the number of mistakes grows only logarithmically with the number of irrelevant attributes in the examples. At the same time, the algorithm is computationally efficient in both time and space.     

柔性制造系统中生产调度问题的零压缩二叉决策图算法

针对赋时有界Petri网模型下柔性制造系统的生产调度问题,给出了有界Petri网的零压缩二叉决策图表示方法,进而建立了此类生产调度问题求解的符号零压缩二叉决策图算法.该算法在求解过程中对状态空间及其搜索过程中的相关数据,采用零压缩二叉决策图表示,避免了状态和搜索的显式枚举,实现了隐式高效操作,有效地改善了算法的计算性能.实验结果表明了算法的有效性.     

Compact representations of all members of an independence system

It is well known that (reduced, ordered) binary decision diagrams (BDDs) can sometimes be compact representations of the full solution set of Boolean optimization problems. Recently they have been suggested to be useful as discrete relaxations in integer and constraint programming (Hoda et al. 2010). We show that for every independence system there exists a top-down (i.e., single-pass) construction rule for the BDD. Furthermore, for packing and covering problems on n variables whose bandwidth is bounded by \(\mathcal {O}(\log n)\) the maximum width of the BDD is bounded by \(\mathcal {O}(n)\). We also characterize minimal widths of BDDs representing the set of all solutions to a stable set problem for various basic classes of graphs. Besides implicitly enumerating or counting all solutions and optimizing a class of nonlinear objective functions that includes separable functions, the results can be applied for effective evaluation of generating functions.