On the equivalence and range of applicability of graph-based representations of logic programs

Logic programs under Answer Sets semantics can be studied, and actual computation can be carried out, by means of representing them by directed graphs. Several reductions of logic programs to directed graphs are now available. We compare our proposed representation, called Extended Dependency Graph, to the Block Graph representation recently defined by Linke [Proc. IJCAI-2001, 2001, pp. 641-648]. On the relevant fragment of well-founded irreducible programs, extended dependency and block graph turns out to be isomorphic. So, we argue that graph representation of general logic programs should be abandoned in favor of graph representation of well-founded irreducible programs, which are more concise, more uniform in structure while being equally expressive.     

Dynamic structural symmetry breaking for constraint satisfaction problems

In recent years, symmetry breaking for constraint satisfaction problems (CSPs) has attracted considerable attention. Various general schemes have been proposed to eliminate symmetries. In general, these schemes may take exponential space or time to eliminate all the symmetries. We identify several classes of CSPs that encompass many practical problems and for which symmetry breaking for various forms of value or variable interchangeability is tractable using dedicated search procedures. We also show the limits of efficient symmetry breaking for such dominance-detection schemes by proving intractability results for some classes of CSPs.     

On the constraint function method for contact problems

The objective in this paper is to present some theoretical insight and valuable numerical experiences for the analysis of contact problems. We review the theoretical basis of the constraint function method for general contact problems and discuss some important characteristics of the method. In the presentation, we consider static and dynamic conditions. We then give numerical experiences with the method through the solution of some demonstrative test problems and through the results obtained in some industrial analysis cases.     

A unified theory of structural tractability for constraint satisfaction problems

In this paper we derive a generic form of structural decomposition for the constraint satisfaction problem, which we call a guarded decomposition. We show that many existing decomposition methods can be characterised in terms of finding guarded decompositions satisfying certain specified additional conditions.Using the guarded decomposition framework we are also able to define a new form of decomposition, which we call a spread-cut. We show that the discovery of width-k spread-cut decompositions is tractable for each k, and that spread-cut decompositions strongly generalise many existing decomposition methods. Finally we exhibit a family of hypergraphs $H_n$, for $n=1,2,3\dots$, where the minimum width of any hypertree decomposition of each $H_n$ is 3n, but the width of the best spread-cut decomposition is only $2n+1$.     

Evaluation of Kermeta for solving graph-based problems

Kermeta is a meta-language for specifying the structure and behavior of graphs of interconnected objects called models. In this paper, we show that Kermeta is relatively suitable for solving three graph-based problems. First, Kermeta allows the specification of generic model transformations such as refactorings that we apply to different metamodels including Ecore, Java, and Uml. Second, we demonstrate the extensibility of Kermeta to the formal language Alloy using an inter-language model transformation. Kermeta uses Alloy to generate recommendations for completing partially specified models. Third, we show that the Kermeta compiler achieves better execution time and memory performance compared to similar graph-based approaches using a common case study. The three solutions proposed for those graph-based problems and their evaluation with Kermeta according to the criteria of genericity, extensibility, and performance are the main contribution of the paper. Another contribution is the comparison of these solutions with those proposed by other graph-based tools.     

On formal power series representations for uncertain systems

The concept of minimality as developed for uncertain and multidimensional systems represented by linear fractional transformations (LFTs) is related to realization theory results for formal power series. We discuss the relationship between the notions of minimality for LFT and series realizations, and present a method for obtaining one type of minimal realization from the opposing type. An extension of an existing minimality result for formal power series to the multi-input-multi-output (MIMO) case is also presented     

On the mathematics of sequential decompositions

We view the process of constructing a program as the stepwise transformation of a relation into simpler relations. In this paper, we focus on a particular transformation: that which decomposes the specification of an iterative program into the specification of the initialization segment and the specification of the while loop. We investigate in some detail the mathematics of this decomposition.     

Exploiting the deep structure of constraint problems

We introduce a technique for analyzing the behavior of sophisticated AI search programs working on realistic, large-scale problems. This approach allows us to predict where, in a space of problem instances, the hardest problems are to be found and where the fluctuations in difficulty are greatest. Our key insight is to shift emphasis from modelling sophisticated algorithms directly to modelling a search space that captures their principal effects. We compare our model's predictions with actual data on real problems obtained independently and show that the agreement is quite good. By systematically relaxing our underlying modelling assumptions we identify their relative contribution to the remaining error and then remedy it. We also discuss further applications of our model and suggest how this type of analysis can be generalized to other kinds of AI problems.     

On graph-based characteristics of optimal overlay topologies

In this paper, we address the challenge of overlay topology design by considering which overlay topology best minimizes cost function, taking into account overlay link creation cost and routing cost. First, we formulate the problem as Integer Linear Programming (ILP) given a traffic matrix and assuming cooperative behavior of nodes. Then, we propose some heuristics to find near-optimal overlay topologies with a reduced complexity. The solutions to the ILP problem on real network topologies have been analyzed, showing that the traffic demands between the nodes affect the decision to create new overlay links. Next, the obtained optimal and near-optimal overlay topologies are thoroughly analyzed and the heuristics are compared through extensive numerical evaluations. Finally guidelines for the selection of the best heuristic as a function of the cost parameters are also provided.     

On expressive power of regular realizability problems

A regular realizability (RR) problem is a problem of testing nonemptiness of intersection of some fixed language (filter) with a regular language. We show that RR problems are universal in the following sense. For any language L there exists an RR problem equivalent to L under disjunctive reductions in nondeterministic log space. From this result, we derive existence of complete problems under polynomial reductions for many complexity classes, including all classes of the polynomial hierarchy.     

Relaxations of semiring constraint satisfaction problems

The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. Bistarelli et al. [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraint solving and optimization, Journal of the ACM 44 (2) (1997) 201-236] defines a maximal solution to a SCSP as the best set of solution tuples for the variables in the problem. Sometimes this maximal solution may not be good enough, and in this case we want to change the constraints so that we solve a problem that is slightly different from the original problem but has an acceptable solution. We propose a relaxation of a SCSP, and use a semiring to give a measure of the difference between the original SCSP and the relaxed SCSP. We introduce a relaxation scheme but do not address the computational aspects.     

Hybrid tractability of valued constraint problems

The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Valued constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of valued constraint problems; that is, properties which guarantee tractability of the given valued constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and the SoftAllDiff constraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.     

On the resolution of some unilaterally constrained problems in structural engineering

This paper proposes a procedure for solving problems of structural analysis, in an algebraic formulation, in terms of equations and inequalities (incremental or finite elastoplastic analysis, elastic analysis with unilateral constraining on displacements, etc.). A version of the “principal pivoting method” is proposed for solving the quadratic programming problem which is connected to the inequalities. The method is illustrated with regard to a contact problem; an account of its performances is given. The whole procedure profits from the symmetry present in the algebraic problem.     

On some fundamental properties of structural topology optimization problems

We study some fundamental mathematical properties of discretized structural topology optimization problems. Either compliance is minimized with an upper bound on the volume of the structure, or volume is minimized with an upper bound on the compliance. The design variables are either continuous or 0–1. We show, by examples which can be solved by hand calculations, that the optimal solutions to the problems in general are not unique and that the discrete problems possibly have inactive volume or compliance constraints. These observations have immediate consequences on the theoretical convergence properties of penalization approaches based on material interpolation models. Furthermore, we illustrate that the optimal solutions to the considered problems in general are not symmetric even if the design domain, the external loads, and the boundary conditions are symmetric around an axis. The presented examples can be used as teaching material in graduate and undergraduate courses on structural topology optimization.     

On the expressiveness of subset-sum representations

We develop a general theory for representing information as sums of elements in a subset of the basic set A of numbers of cardinality n, often refered to as a “knapsack vector”. How many numbers can be represented in this way depends heavily on n. The lower, resp. upper, bound for the cardinality of the set of representable numbers is quadratic, resp. exponential, in terms of n. We give an algorithm for the construction of a knapsack vector of any prescribed expressiveness (that is, the cardinality of the set of representable numbers), provided it falls within the range possible for expressiveness. Received: 13 March 1997 / 18 November 1999     

On compatible star decompositions of simple polygons

The authors introduce the notion of compatible star decompositions of simple polygons. In general, given two polygons with a correspondence between their vertices, two polygonal decompositions of the two polygons are said to be compatible if there exists a one-to-one mapping between them such that the corresponding pieces are defined by corresponding vertices. For compatible star decompositions, they also require correspondence between star points of the star pieces. Compatible star decompositions have applications in computer animation and shape representation and analysis. They present two algorithms for constructing compatible star decompositions of two simple polygons. The first algorithm is optimal in the number of pieces in the decomposition, providing that such a decomposition exists without adding Steiner vertices. The second algorithm constructs compatible star decompositions with Steiner vertices, which are not minimal in the number of pieces but are asymptotically worst-case optimal in this number and in the number of added Steiner vertices. They prove that some pairs of polygons require Ω(n²) pieces, and that the decompositions computed by the second algorithm possess no more than O(n²) pieces. In addition to the contributions regarding compatible star decompositions, the paper also corrects an error in the only previously published polynomial algorithm for constructing a minimal star decomposition of a simple polygon, an error which might lead to a nonminimal decomposition     

A new tractable class of constraint satisfaction problems

In this paper we consider constraint satisfaction problems where the set of constraint relations is fixed. Feder and Vardi (1998) identified three families of constraint satisfaction problems containing all known polynomially solvable problems. We introduce a new class of problems called para-primal problems, incomparable with the families identified by Feder and Vardi (1998) and we prove that any constraint problem in this class is decidable in polynomial time. As an application of this result we prove a complete classification for the complexity of constraint satisfaction problems under the assumption that the basis contains all the permutation relations. In the proofs, we make an intensive use of algebraic results from clone theory about the structure of para-primal and homogeneous algebras. AMS subject classification 08A70     

On the numerical solution of a class of unilateral contact structural optimization problems

This paper deals with a special class of structural optimization problems in nonsmooth mechanics. More precisely, it is required to minimize the weight of a structure subject to frictionless unilateral contact conditions and constraints on the magnitudes of contact forces, displacements, stresses and cross-sectional areas. This problem, as is well-known, can be formulated as a special and challenging optimization problem known as a Mathematical Program with Equilibrium Constraints (MPEC), a key feature of which is the presence of complementarity conditions, involving the orthogonality of two sign-constrained vectors. In spite of its inherent nonsmoothness, we attempt to solve the problem using standard nonlinear programming techniques. In particular, we investigate numerically the application of two simple algorithms, both based on the use of the general-purpose nonlinear programming code CONOPT accessed via the powerful GAMS modelling language, for solving the suitably reformulated problem. Application is illustrated by means of three numerical examples.     

Quantifying structural attributes of system decompositions in 28 feature-oriented software product lines

A key idea of feature orientation is to decompose a software product line along the features it provides. Feature decomposition is orthogonal to object-oriented decomposition—it crosscuts the underlying package and class structure. It has been argued often that feature decomposition improves system structure by reducing coupling and by increasing cohesion. However, recent empirical findings suggest that this is not necessarily the case. In this exploratory, observational study, we investigate the decompositions of 28 feature-oriented software product lines into classes, features, and feature-specific class fragments. The product lines under investigation are implemented using the feature-oriented programming language Fuji. In particular, we quantify and compare the internal attributes import coupling and cohesion of the different product-line decompositions in a systematic, reproducible manner. For this purpose, we adopt three established software measures (e.g., coupling between units, CBU; internal-ratio unit dependency, IUD) as well as standard concentration statistics (e.g., Gini coefficient). In our study, we found that feature decomposition can be associated with higher levels of structural coupling in a product line than a decomposition into classes. Although coupling can be concentrated in very few features in most feature decompositions, there are not necessarily hot-spot features in all product lines. Interestingly, feature cohesion is not necessarily higher than class cohesion, whereas features are more equal in serving dependencies internally than classes of a product line. Our empirical study raises critical questions about alleged advantages of feature decomposition. At the same time, we demonstrate how our measurement approach of coupling and cohesion has potential to support static and dynamic analyses of software product lines (i.e., type checking and feature-interaction detection) by facilitating product sampling.