The Experts below are selected from a list of 38661 Experts worldwide ranked by ideXlab platform
Martin Gogolla - One of the best experts on this subject based on the ideXlab platform.
-
employing the object Constraint Language in model based engineering
European Conference on Modelling Foundations and Applications, 2013Co-Authors: Martin GogollaAbstract:MBE (Model-Based Engineering) proposes to develop software by taking advantage of models, in contrast to traditional code-centric development approaches. If models play a central role in development, model properties must be formulated and checked early on the modeling level, not late on the implementation level. We discuss how to validate and verify model properties in the context of modeling Languages like the UML (Unified Modeling Language) combined with textual restrictions formulated in the OCL (Object Constraint Language).
-
object Constraint Language ocl a definitive guide
Formal Methods, 2012Co-Authors: Jordi Cabot, Martin GogollaAbstract:The Object Constraint Language (OCL) started as a complement of the UML notation with the goal to overcome the limitations of UML (and in general, any graphical notation) in terms of precisely specifying detailed aspects of a system design. Since then, OCL has become a key component of any model-driven engineering (MDE) technique as the default Language for expressing all kinds of (meta)model query, manipulation and specification requirements. Among many other applications, OCL is frequently used to express model transformations (as part of the source and target patterns of transformation rules), well-formedness rules (as part of the definition of new domain-specific Languages), or code-generation templates (as a way to express the generation patterns and rules). This chapter pretends to provide a comprehensive view of this Language, its many applications and available tool support as well as the latest research developments and open challenges around it.
-
modular embedding of the object Constraint Language into a programming Language
Formal Methods, 2011Co-Authors: Fabian Buttner, Martin GogollaAbstract:The Object Constraint Language (OCL) is a well-accepted ingredient in model-driven engineering and accompanying modeling Languages like UML (Unified Modeling Language) or EMF (Eclipse Modeling Framework) which support object-oriented software development. Among various possibilities, OCL offers the formulation of state invariants and operation contracts in form of pre- and postconditions. With OCL, side effect free query operations can be implemented. However, for operations changing the system state an implementation cannot be given within OCL. In order to fill this gap, this paper proposes the Language SOIL (Simple OCL-like Imperative Language). The expression sub-Language of SOIL is identical to OCL. SOIL adds well-known, traditional imperative constructs. Thus by employing OCL and SOIL, it is possible to describe any operation in a declarative way and in an operational way on the modeling level without going into the details of a conventional programming Language. In contrast to other similar approaches, the embedding of OCL into SOIL is done in a new, careful way so that elementary properties in OCL are preserved (for example, commutativity of logical conjunction). The paper discusses the major criteria of a conservative embedding of OCL into SOIL. SOIL has a sound formal semantics and is implemented in the UML and OCL tool USE (UML-based Specification Environment).
-
specification and validation of authorisation Constraints using uml and ocl
Lecture Notes in Computer Science, 2005Co-Authors: Karsten Sohr, Martin Gogolla, Lars MiggeAbstract:Authorisation Constraints can help the policy architect design and express higher-level security policies for organisations such as financial institutes or governmental agencies. Although the importance of Constraints has been addressed in the literature, there does not exist a systematic way to validate and test authorisation Constraints. In this paper, we attempt to specify non-temporal Constraints and history-based Constraints in Object Constraint Language (OCL) which is a Constraint specification Language of Unified Modeling Language (UML) and describe how we can facilitate the USE tool to validate and test such policies. We also discuss the issues of identification of conflicting Constraints and missing Constraints.
-
on formalizing the uml object Constraint Language ocl
International Conference on Conceptual Modeling, 1998Co-Authors: Mark Richters, Martin GogollaAbstract:We present a formal semantics for the Object Constraint Language (OCL) which is part of the Unified Modeling Language (UML) – an emerging standard Language and notation for object-oriented analysis and design. In context of information systems modeling, UML class diagrams can be utilized for describing the overall structure, whereas additional integrity Constraints and queries are specified with OCL expressions. By using OCL, Constraints and queries can be specified in a formal yet comprehensible way. However, the OCL itself is currently defined only in a semi-formal way. Thus the semantics of Constraints is in general not precisely defined. Our approach gives precise meaning to OCL concepts and to some central aspects of UML class models. A formal semantics facilitates verification, validation and simulation of models and helps to improve the quality of models and software designs.
Fredrik Kuivinen - One of the best experts on this subject based on the ideXlab platform.
-
hard Constraint satisfaction problems have hard gaps at location 1
Theoretical Computer Science, 2009Co-Authors: Peter Jonsson, Andrei Krokhin, Fredrik KuivinenAbstract:An instance of the maximum Constraint satisfaction problem (Max CSP) is a finite collection of Constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied Constraints. Max CSP captures many well-known problems (such as Maxk-SAT and Max Cut) and is consequently NP-hard. Thus, it is natural to study how restrictions on the allowed Constraint types (or Constraint Language) affect the complexity and approximability of Max CSP. The PCP theorem is equivalent to the existence of a Constraint Language for which Max CSP has a hard gap at location 1; i.e. it is NP-hard to distinguish between satisfiable instances and instances where at most some constant fraction of the Constraints are satisfiable. All Constraint Languages, for which the CSP problem (i.e., the problem of deciding whether all Constraints can be satisfied) is currently known to be NP-hard, have a certain algebraic property. We prove that any Constraint Language with this algebraic property makes Max CSP have a hard gap at location 1 which, in particular, implies that such problems cannot have a PTAS unless P=NP. We then apply this result to Max CSP restricted to a single Constraint type; this class of problems contains, for instance, Max Cut and Max DiCut. Assuming P NP, we show that such problems do not admit PTAS except in some trivial cases. Our results hold even if the number of occurrences of each variable is bounded by a constant. Finally, we give some applications of our results.
-
hard Constraint satisfaction problems have hard gaps at location 1
arXiv: Computational Complexity, 2007Co-Authors: Peter Jonsson, Andrei Krokhin, Fredrik KuivinenAbstract:An instance of Max CSP is a finite collection of Constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied Constraints. Max CSP captures many well-known problems (such as Max k-SAT and Max Cut) and is consequently NP-hard. Thus, it is natural to study how restrictions on the allowed Constraint types (or Constraint Languages) affect the complexity and approximability of Max CSP. The PCP theorem is equivalent to the existence of a Constraint Language for which Max CSP has a hard gap at location 1, i.e. it is NP-hard to distinguish between satisfiable instances and instances where at most some constant fraction of the Constraints are satisfiable. All Constraint Languages, for which the CSP problem (i.e., the problem of deciding whether all Constraints can be satisfied) is currently known to be NP-hard, have a certain algebraic property. We prove that any Constraint Language with this algebraic property makes Max CSP have a hard gap at location 1 which, in particular, implies that such problems cannot have a PTAS unless P = NP. We then apply this result to Max CSP restricted to a single Constraint type; this class of problems contains, for instance, Max Cut and Max DiCut. Assuming P $\neq$ NP, we show that such problems do not admit PTAS except in some trivial cases. Our results hold even if the number of occurrences of each variable is bounded by a constant. We use these results to partially answer open questions and strengthen results by Engebretsen et al. [Theor. Comput. Sci., 312 (2004), pp. 17--45], Feder et al. [Discrete Math., 307 (2007), pp. 386--392], Krokhin and Larose [Proc. Principles and Practice of Constraint Programming (2005), pp. 388--402], and Jonsson and Krokhin [J. Comput. System Sci., 73 (2007), pp. 691--702]
-
ruling out polynomial time approximation schemes for hard Constraint satisfaction problems
Computer Science Symposium in Russia, 2007Co-Authors: Peter Jonsson, Andrei Krokhin, Fredrik KuivinenAbstract:The maximum Constraint satisfaction problem (Max CSP) is the following computational problem: an instance is a finite collection of Constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied Constraints. Max CSP captures many well-known problems (such as Max k-SAT and Max Cut) and so is NP-hard in general. It is natural to study how restrictions on the allowed Constraint types (or Constraint Language) affect the complexity and approximability of Max CSP. All Constraint Languages, for which the CSP problem (i.e., the problem of deciding whether all Constraints in an instance can be simultaneously satisfied) is currently known to be NP-hard, have a certain algebraic property, and it has been conjectured that CSP problems are tractable for all other Constraint Languages. We prove that any Constraint Language with this algebraic property makes Max CSP hard at gap location 1, thus ruling out the existence of a polynomial-time approximation scheme for such problems. We then apply this result to Max CSP restricted to a single Constraint type. We show that, unless P = NP, such problems either are trivial or else do not admit polynomial-time approximation schemes. All our hardness results hold even if the number of occurrences of each variable is bounded by a constant.
Pascal Van Hentenryck - One of the best experts on this subject based on the ideXlab platform.
-
CP - Contraint-Based Combinators for Local Search
Constraints, 2005Co-Authors: Pascal Van Hentenryck, Laurent Michel, Liyuan LiuAbstract:One of the most appealing features of Constraint programming is its rich Constraint Language for expressing combinatorial optimization problems. This paper demonstrates that traditional combinators from Constraint programming have natural counterparts for local search, although their underlying computational model is radically different. In particular, the paper shows that Constraint combinators, such as logical and cardinality operators, reification, and first-class expressions can all be viewed as differentiable objects. These combinators naturally support elegant and efficient modelings, generic search procedures, and partial Constraint satisfaction techniques for local search. Experimental results on a variety of applications demonstrate the expressiveness and the practicability of the combinators.
-
Constraint-based combinators for local search
Lecture Notes in Computer Science, 2004Co-Authors: Pascal Van Hentenryck, Laurent Michel, Liyuan LiuAbstract:One of the most appealing features of Constraint programming is its rich Constraint Language for expressing combinatorial optimization problems. This paper demonstrates that traditional combinators from Constraint programming have natural counterparts for local search, although their underlying computational model is radically different. In particular, the paper shows that Constraint combinators, such as logical and cardinality operators, reification, and first-class expressions can all be viewed as differentiable objects. These combinators naturally support elegant and efficient modelings, generic search procedures, and partial Constraint satisfaction techniques for local search. Experimental results on a variety of applications demonstrate the expressiveness and the practicability of the combinators.
-
design implementation and evaluation of the Constraint Language cc fd
22nd Spring School in Theoretical Computer Science, 1995Co-Authors: Pascal Van Hentenryck, Vijay Saraswat, Yves DevilleAbstract:This paper describes the design, implementation, and applications of the Constraint logic Language cc(FD). cc(FD) is a declarative nondeterministic Constraint logic Language over finite domains based on the cc framework [33], an extension of the Constraint Logic Programming (CLP) scheme [21]. Its Constraint solver includes (nonlinear) arithmetic Constraints over natural numbers which are approximated using domain and interval consistency. The main novelty of cc (FD) is the inclusion of a number of general-purpose combinators, in particular cardinality, constructive disjunction, and blocking implication, in conjunction with new Constraint operations such as Constraint entailment and generalization. These combinators significantly improve the operational expressiveness, extensibility, and flexibility of CLP Languages and allow issues such as the definition of nonprimitive Constraints and disjunctions to be tackled at the Language level. The implementation of cc (FD) (about 40,000 lines of C) includes a WAM-based engine [44], optimal are-consistency algorithms based on AC-5 [40], and incremental implementation of the combinators. Results on numerous problems, including scheduling, resource allocation, sequencing, packing, and hamiltonian paths are reported and indicate that cc(FD) comes close to procedural Languages on a number of combinatorial problems. In addition, a small cc(FD) program was able to find the optimal solution and prove optimality to a famous 10/10 disjunctive scheduling problem [29], which was left open for more than 20 years and finally solved in 1986. (C) 1998 Elsevier Science Inc. All rights reserved.
-
design implementation and evaluation of the Constraint Language cc fd
Selected Papers from Constraint Programming: Basics and Trends, 1994Co-Authors: Pascal Van Hentenryck, Vijay Saraswat, Yves DevilleAbstract:This paper describes the design, implementation, and applications of the Constraint logic Language cc(FD). cc(FD) is a declarative nondeterministic Constraint logic Language over finite domains based on the cc framework, an extension of the CLP scheme. Its Constraint solver includes (nonlinear) arithmetic Constraints over natural numbers which are approximated using domain and interval consistency. The main novelty of cc(FD) is the inclusion of a number of general-purpose combinators, in particular cardinality, constructive disjunction, and blocking implication, in conjunction with new Constraint operations such as Constraint entailment and generalization. These combinators significantly improve the operational expressiveness, extensibility, and flexibility of CLP Languages and allow issues such as the definition of non-primitive Constraints and disjunctions to be tackled at the Language level. The implementation of cc(FD) (about 40,000 lines of C) includes a WAM-based engine, optimal arc-consistency algorithms based on AC-5, and incremental implementation of the combinators. Results on numerous problems, including scheduling, resource allocation, sequencing, packing, and hamiltonian paths are reported, and indicate that cc(FD) comes close to procedural Languages on a number of combinatorial problems. In addition, a small cc(FD) program was able to find the optimal solution and prove optimality to a famous 10/10 disjunctive scheduling problem, which was left open for more than 20 years and finally solved in 1988.
Frank Finger - One of the best experts on this subject based on the ideXlab platform.
-
modular architecture for a toolset supporting ocl
Science of Computer Programming, 2002Co-Authors: Heinrich Hussmann, Birgit Demuth, Frank FingerAbstract:The practical application of the object Constraint Language (OCL), which is part of the UML specification since version 1.1, depends crucially on the existence of adequate tool support. This paper discusses general design issues for OCL tools. It is argued that the nature of OCL will lead to a large variety of tools, applied in combination with a variety of different UML tools. Therefore, a flexible modular architecture for a UML/OCL toolset is proposed. The paper reports on the first results of an ongoing project which aims at the provision of such an OCL toolset that is available as free software.
-
modular architecture for a toolset supporting ocl
Lecture Notes in Computer Science, 2000Co-Authors: Heinrich Hussmann, Birgit Demuth, Frank FingerAbstract:The practical application of the Object Constraint Language, which is part of the UML specification since version 1.1, depends crucially on the existence of adequate tool support. This paper discusses general design issues for OCL tools. It is argued that the nature of OCL will lead to a large variety of tools, applied in combination with a variety of different UML tools. Therefore, a flexible modular architecture for a UML/OCL toolset is proposed. The paper reports on the first results of an ongoing project which aims at the provision of such an OCL toolset for the public domain.
Hubie Chen - One of the best experts on this subject based on the ideXlab platform.
-
Best-Case and Worst-Case Sparsifiability of Boolean CSPs
Algorithmica, 2020Co-Authors: Hubie Chen, Bart M P Jansen, Astrid PieterseAbstract:We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of Constraints in a problem instance without changing the answer, such that a bound on the number of resulting Constraints can be given in terms of the number of variables n . We investigate how the worst-case sparsification size depends on the types of Constraints allowed in the problem formulation—the Constraint Language—and identify Constraint Languages giving the best-possible and worst-possible behavior for worst-case sparsifiability. Two algorithmic results are presented. The first result essentially shows that for any arity k , the only Constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with $$O(n)$$ O ( n ) Constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a Constraint type to be captured by a degree-1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NP-complete Boolean CSPs whose Constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which Constraint Languages allow for a linear sparsification. For Boolean CSPs in which every Constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the Constraint Language.
-
best case and worst case sparsifiability of boolean csps
arXiv: Computational Complexity, 2018Co-Authors: Hubie Chen, Bart M P Jansen, Astrid PieterseAbstract:We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of Constraints in a problem instance without changing the answer, such that a bound on the number of resulting Constraints can be given in terms of the number of variables n. We investigate how the worst-case sparsification size depends on the types of Constraints allowed in the problem formulation (the Constraint Language). Two algorithmic results are presented. The first result essentially shows that for any arity k, the only Constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with O(n) Constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a Constraint type to be captured by a degree-1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NP-complete Boolean CSPs whose Constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which Constraint Languages allow for a linear sparsification. For Boolean CSPs in which every Constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the Constraint Language.
-
Quantified Constraint satisfaction and the polynomially generated powers property
Algebra universalis, 2011Co-Authors: Hubie ChenAbstract:The quantified Constraint satisfaction probem (QCSP) is the problem of deciding, given a relational structure and a sentence consisting of a quantifier prefix followed by a conjunction of atomic formulas, whether or not the sentence is true in the structure. The general computational intractability of the QCSP has led to the study of restricted versions of this problem. In this article, we study restricted versions of the QCSP that arise from prespecifying the relations that may occur via a set of relations called a Constraint Language . A basic tool used is a correspondence that associates an algebra to each Constraint Language; this algebra can be used to derive information on the behavior of the Constraint Language. We identify a new combinatorial property on algebras, the polynomially generated powers (PGP) property, which we show is tightly connected to QCSP complexity. We also introduce another new property on algebras, switchability , which both implies the PGP property and implies positive complexity results on the QCSP. Our main result is a classification theorem on a class of three-element algebras: each algebra is either switchable and hence has the PGP, or provably lacks the PGP. The description of non-PGP algebras is remarkably simple and robust.
-
quantified Constraint satisfaction and the polynomially generated powers property extended abstract
2008Co-Authors: Hubie ChenAbstract:The quantified Constraint satisfaction probem (QCSP) is the problem of deciding, given a relational structure and a sentence consisting of a quantifier prefix followed by a conjunction of atomic formulas, whether or not the sentence is true in the structure. The general intractability of the QCSP has led to the study of restricted versions of this problem. In this article, we study restricted versions of the QCSP that arise from prespecifying the relations that may occur via a set of relations called a Constraint Language. A basic tool used is a correspondence that associates an algebra to each Constraint Language; this algebra can be used to derive information on the behavior of the Constraint Language. We identify a new combinatorial property on algebras, the polynomially gen- erated powers (PGP) property, which we show is tightly connected to QCSP com- plexity. We also introduce another new property on algebras, switchability ,w hich both implies the PGP property and implies positive complexity results on the QCSP. Our main result is a classification theorem on a class of three-element al- gebras: each algebra is either switchable and hence has the PGP, or provably lacks the PGP. The description of non-PGP algebras is remarkably simple and robust. that is, a conjunction of atomic formulas in front of which all variables are existentially quantified, whether or not the sentence is true in the structure. The quantified Constraint satisfaction problem (QCSP) is the generalization of the CSP where universal quan- tification is permitted in addition to existential quantification. Each of these problems constitutes a natural syntactic restriction of model checking in first-order logic. The general intractability of the CSP and the QCSP-they are NP-complete and PSPACE-complete, respectively-has prompted the study of restricted versions of these problems. In this paper, we study restricted versions of the QCSP that are obtained by prespecifying the relations that may occur using a set of relations called a Constraint
