Propositional Logic Constraint Patterns and Their Use in UML-Based Conceptual Modeling and Analysis

An important conceptual modeling activity in the development of database, object-oriented and agent-oriented systems is the capture and expression of domain constraints governing underlying data and object states. UML is increasingly used for capturing conceptual models, as it supports conceptual modeling of arbitrary domains, and has extensible notation allowing capture of invariant constraints both in the class diagram notation and in the separately denoted OCL syntax. However, a need exists for increased formalism in constraint capture that does not sacrifice ease of use for the analyst. In this paper, we codify a set of invariant patterns formalized for capturing a rich category of propositional constraints on class diagrams. We use tools of Boolean logic to set out the distinction between these patterns, applying them in modeling by way of example. We use graph notation to systematically uncover constraints hidden in the diagrams. We present data collected from applications across different domains, supporting the importance of "pattern-finding" for n-variable propositional constraints using general graph theoretic methods. This approach enriches UML-based conceptual modeling for greater completeness, consistency, and correctness by formalizing the syntax and semantics of these constraint patterns, which has not been done in a comprehensive manner before now     

Patterns of self-stabilization in database consistency maintenance

A substantial portion of the database programming efforts are invested in integrity constraints enforcement. Traditionally, both the constraint semantics and their enforcement were embedded inside application programs. In recent years several studies have dealt with specifying integrity constraints as separate entities (e.g. rules), and relating the database consistency requirements to these rules. In this paper we deal with the complementary issue of stabilizing the database when update exceptions occur. While a simplistic approach is to abort any transaction that inflicts consistency violations, this is not always the desired action. We take advantage of the empirical observation that most of the exception-handling policies follow a small number of behavior patterns. Unlike some previous approaches that base their repair solution on syntactic analysis of the constraints and performance issues, we base our approach on the application semantics as reflected in these behavioral patterns. We describe a model that uses high-level abstractions called stabilizer types denoting these behavior patterns for consistency restorations, whose exact semantics is case dependent. It follows the fault tolerance's self-stabilization approach. An inference mechanism translates these abstractions into executable active rules. This approach provides high-level language to the exception handling portion of the application and substantially reduces the required programming.     

CLPS–B – A constraint solver to animate a B specification

This paper proposes an approach to evaluating B formal specifications using constraint logic programming with sets (CLPS). This approach is used to animate and generate test sequences from B formal specifications. The solver, called CLPS–B, is described in terms of constraint domains, consistency verification, and constraint propagation. It is more powerful than most constraint systems because it allows the domain of variable to contain other variables, which increases the level of abstraction. The constrained state propagates the nondeterminism of the B specifications and reduces the number of states in a reachability graph. We illustrate this approach by comparing the constrained state graph exploration with the concrete one in a simple example – process scheduler. We also describe the automated test generation method that uses the CLPS–B solver to better control combinational explosion.     

Formal languages for integer programming modeling of shift scheduling problems

This paper approaches the problem of modeling optimization problems containing substructures involving constraints on sequences of decision variables. Such constraints can be very complex to express with Mixed Integer Programming (MIP). We suggest an approach inspired by global constraints used in Constraint Programming (CP) to exploit formal languages for the modeling of such substructures with MIP. More precisely, we first suggest a way to use automata, as the CP regular constraint does, to express allowed patterns for the values taken by the constrained sequence of variables. Secondly, we present how context-free grammars can contribute to formulate constraints on sequences of variables in a MIP model. Experimental results on both approaches show that they facilitate the modeling, but also give models easier to solve by MIP solvers compared to compact assignment MIP formulations.     

SAT Modulo Linear Arithmetic for Solving Polynomial Constraints

Polynomial constraint solving plays a prominent role in several areas of hardware and software analysis and verification, e.g., termination proving, program invariant generation and hybrid system verification, to name a few. In this paper we propose a new method for solving non-linear constraints based on encoding the problem into an SMT problem considering only linear arithmetic. Unlike other existing methods, our method focuses on proving satisfiability of the constraints rather than on proving unsatisfiability, which is more relevant in several applications as we illustrate with several examples. Nevertheless, we also present new techniques based on the analysis of unsatisfiable cores that allow one to efficiently prove unsatisfiability too for a broad class of problems. The power of our approach is demonstrated by means of extensive experiments comparing our prototype with state-of-the-art tools on benchmarks taken both from the academic and the industrial world.     

Toward the Reverse Engineering of UML Sequence Diagrams for Distributed Java Software

This paper proposes a methodology and instrumentation infrastructure toward the reverse engineering of UML (Unified Modeling Language) sequence diagrams from dynamic analysis. One motivation is, of course, to help people understand the behavior of systems with no (complete) documentation. However, such reverse-engineered dynamic models can also be used for quality assurance purposes. They can, for example, be compared with design sequence diagrams and the conformance of the implementation to the design can thus be verified. Furthermore, discrepancies can also suggest failures in meeting the specifications. Due to size constraints, this paper focuses on the distribution aspects of the methodology we propose. We formally define our approach using metamodels and consistency rules. The instrumentation is based on aspect-oriented programming in order to alleviate the effort overhead usually associated with source code instrumentation. A case study is discussed to demonstrate the applicability of the approach on a concrete example     

A Systematic Approach for Designing Analytical Dynamics and Servo Control of Constrained Mechanical Systems

A systematic approach for designing analytical dynamics and servo control of constrained mechanical systems is proposed. Fundamental equation of constrained mechanical systems is first obtained according to Udwadia-Kalaba approach which is applicable to holonomic and nonholonomic constrained systems no matter whether they satisfy the D'Alember's principle. The performance specifications are modeled as servo constraints. Constraint-following servo control is used to realize the servo constraints. For this inverse dynamics control problem, the determination of control inputs is based on the Moore-Penrose generalized inverse to complete the specified motion. Secondorder constraints are used in the dynamics and servo control. Constraint violation suppression methods can be adopted to eliminate constraint drift in the numerical simulation. Furthermore, this proposed approach is applicable to not only fully actuated but also underactuated and redundantly actuated mechanical systems. Two-mass spring system and coordinated robot system are presented as examples for illustration.      

Validation of static properties in unified modeling language models for cyber physical systems

Cyber physical systems (CPSs) can be found nowadays in various fields of activity. The increased interest for these systems as evidenced by the large number of applications led to complex research regarding the most suitable methods for design and development. A promising solution for specification, visualization, and documentation of CPSs uses the Object Management Group (OMG) unified modeling language (UML). UML models allow an intuitive approach for embedded systems design, helping end-users to specify the requirements. However, the UML models are represented in an informal language. Therefore, it is difficult to verify the correctness and completeness of a system design. The object constraint language (OCL) was defined to add constraints to UML, but it is deficient in strict notations of mathematics and logic that permits rigorous analysis and reasoning about the specifications. In this paper, we investigated how CPS applications modeled using UML deployment diagrams could be formally expressed and verified. We used Z language constructs and prototype verification system (PVS) as formal verification tools. Considering some relevant case studies presented in the literature, we investigated the opportunity of using this approach for validation of static properties in CPS UML models.     

Support for managing design-time decisions

The desirability of maintaining multiple stakeholders' interests during the software design process argues for leaving choices undecided as long as possible. Yet, any form of underspecification, either missing information or undecided choices, must be resolved before automated analysis tools can be used. This paper demonstrates how constraint satisfaction problem solution techniques (CSTs) can be used to automatically reduce the space of choices for ambiguities by incorporating the local effects of constraints, ultimately with more global consequences. As constraints typical of those encountered during the software design process, we use UML consistency and well-formedness rules. It is somewhat surprising that CSTs are suitable for the software modeling domain since the constraints may relate many ambiguities during their evaluation, encountering a well-known problem with CSTs called the k-consistency problem. This paper demonstrates that our CST-based approach is computationally scalable and effective-as evidenced by empirical experiments based on dozens of industrial models.     

Robust adaptive control for a class of semi‐strict feedback systems with state and input constraints

This paper proposes a dynamic surface control (DSC)–based robust adaptive control scheme for a class of semi‐strict feedback systems with full‐state and input constraints. In the control scheme, a constraint transformation method is employed to prevent the transgression of the full‐state constraints. Specifically, the state constraints are firstly represented as the surface error constraints, then, an error transformation is introduced to convert the constrained surface errors into new equivalent variables without constraints. By ensuring the boundedness of the transformed variables, the violation of the state constraints can be prevented. Moreover, in order to obtain magnitude limited virtual control signal for the recursive design, the saturations are incorporated into the control law. The auxiliary design systems are constructed to analyze the effects of the introduced saturations and the input constraints. Rigorous theoretical analysis demonstrates that the proposed control law can guarantee all the closed‐loop signals are uniformly ultimately bounded, the tracking error converges to a small neighborhood of origin, and the full‐state constraints are not violated. Compared with the existing results, the key advantages of the proposed control scheme include: (i) the utilization of the constraint transformation can handle both time‐varying symmetric and asymmetric state constraints and static ones in a unified framework; (ii) the incorporation of the saturations permits the removal of a feasibility analysis step and avoids solving the constrained optimization problem; and (iii) the “explosion of complexity” in traditional backstepping design is avoided by using the DSC technique. Simulations are finally given to confirm the effectiveness of the proposed approach.     

Constraint models for graceful graphs

We present three constraint models of the problem of finding a graceful labelling of a graph, or proving that the graph is not graceful. An experimental comparison of the models applied to different classes of graph is given. The first model seems a natural way to represent the problem, but explores a much larger search tree than the other models. The second model does much less search, by making the most constrained decisions first, but is slow because the constraints are time-consuming to propagate. The third model combines the best features of the others, doing little more search than the second model while being much the fastest of the three. The comparison of the three models provides a useful case-study of modelling problems as constraint satisfaction problems. In addition, we show that constraint programming can be a useful tool for the study of graceful graphs; the models presented here have contributed many new results.     

E-CSPE约束的一致性判定

分布式程序目前被大量使用．由于并发的存在，测试分布式程序需要采用事件约束来判定运行事件序列的正确性，事件约束之间需要判定一致性．初始的事件约束可以通过规约来定义，作者提出E-CSPE约束的描述规则来推导新约束，并提出约束之间的一致性判定机制．该算法具有多项式复杂度．     

Real-time constrained linear discriminant analysis to target detection and classification in hyperspectral imagery

In this paper, we present a constrained linear discriminant analysis (CLDA) approach to hyperspectral image detection and classification as well as its real-time implementation. The basic idea of CLDA is to design an optimal transformation matrix which can maximize the ratio of inter-class distance to intra-class distance while imposing the constraint that different class centers after transformation are along different directions such that different classes can be better separated. The solution turns out to be a constrained version of orthogonal subspace projection (OSP) implemented with a data whitening process. The CLDA approach can be applied to solve both detection and classification problems. In particular, by introducing color for display the classification is achieved with a single classified image where a pre-assigned color is used to display a specified class. The real-time implementation is also developed to meet the requirement of on-line image analysis when the immediate data assessment is critical. The experiments using HYDICE data demonstrate the strength of CLDA approach in discriminating the targets with subtle spectral difference.     

Specifying and validating structural constraints of analysis class models using OCL

Analysis modeling focuses on functional requirements and postpone implementation specific issues until subsequent design activities are undertaken. Based on the analysis models, the design activities are performed by refining and clarifying the analysis models. Thus, the quality of analysis models has a vast impact on the design models. Therefore, much effort should be taken to build correct analysis models.In this paper, we propose structural constraints that analysis class models of information systems should satisfy, and describe an OCL-based approach to validating the analysis class models against the constraints. In addition, through a case study with four medium-sized industrial information systems, we find that the proposed approach can help to identify deficiencies in analysis models.     

Consistency techniques for continuous constraints

We consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing one single optimal solution, we address the problem of computing a compact representation of the space of all solutions admitted by the constraints. In particular, we show how globally consistent (also called decomposable) labelings of a constraint satisfaction problem can be computed.Our approach is based on approximating regions of feasible solutions by 2 ^k -trees, a representation commonly used in computer vision and image processing. We give simple and stable algorithms for computing labelings with arbitrary degrees of consistency. The algorithms can process constraints and solution spaces of arbitrary complexity, but with a fixed maximal resolution.Previous work has shown that when constraints are convex and binary, path-consistency is sufficient to ensure global consistency. We show that for continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of constraint satisfaction problems with continuous variables.     

Exhaustive and Efficient Constraint Propagation: A Graph-Based Learning Approach and Its Applications

This paper presents a novel pairwise constraint propagation approach by decomposing the challenging constraint propagation problem into a set of independent semi-supervised classification subproblems which can be solved in quadratic time using label propagation based on $k$ -nearest neighbor graphs. Considering that this time cost is proportional to the number of all possible pairwise constraints, our approach actually provides an efficient solution for exhaustively propagating pairwise constraints throughout the entire dataset. The resulting exhaustive set of propagated pairwise constraints are further used to adjust the similarity matrix for constrained spectral clustering. Other than the traditional constraint propagation on single-source data, our approach is also extended to more challenging constraint propagation on multi-source data where each pairwise constraint is defined over a pair of data points from different sources. This multi-source constraint propagation has an important application to cross-modal multimedia retrieval. Extensive results have shown the superior performance of our approach.     

On the synthesis of brain-state-in-a-box neural models with application to associative memory

In this article we present techniques for designing associative memories to be implemented by a class of synchronous discrete-time neural networks based on a generalization of the brain-state-in-a-box neural model. First, we address the local qualitative properties and global qualitative aspects of the class of neural networks considered. Our approach to the stability analysis of the equilibrium points of the network gives insight into the extent of the domain of attraction for the patterns to be stored as asymptotically stable equilibrium points and is useful in the analysis of the retrieval performance of the network and also for design purposes. By making use of the analysis results as constraints, the design for associative memory is performed by solving a constraint optimization problem whereby each of the stored patterns is guaranteed a substantial domain of attraction. The performance of the designed network is illustrated by means of three specific examples.     

An agent-oriented approach to change propagation in software maintenance

Software maintenance and evolution is a lengthy and expensive phase in the life cycle of a software system. In this paper we focus on the change propagation problem: given a primary change that is made in order to meet a new or changed requirement, what additional, secondary, changes are needed? We propose a novel, agent-oriented, approach that works by repairing violations of desired consistency rules in a design model. Such consistency constraints are specified using the Object Constraint Language (OCL) and the Unified Modelling Language (UML) metamodel, which form the key inputs to our change propagation framework. The underlying change propagation mechanism of our framework is based on the well-known Belief-Desire-Intention (BDI) agent architecture. Our approach represents change options for repairing inconsistencies using event-triggered plans, as is done in BDI agent platforms. This naturally reflects the cascading nature of change propagation, where each change (primary or secondary) can require further changes to be made. We also propose a new method for generating repair plans from OCL consistency constraints. Furthermore, a given inconsistency will typically have a number of repair plans that could be used to restore consistency, and we propose a mechanism for semi-automatically selecting between alternative repair plans. This mechanism, which is based on a notion of cost, takes into account cascades (where fixing the violation of a constraint breaks another constraint), and synergies between constraints (where fixing the violation of a constraint also fixes another violated constraint). Finally, we report on an evaluation of the approach, covering effectiveness, efficiency and scalability.