Christian Gout
email: christian.gout@insa-rouen.fr

Lucia Romani
email: lucia.romani@unimib.it

"Multivariate Approximation: Theory and Applications" Dedicated to Leonardo Traversoni for his 60th birthday

Keywords: Interpolation, Multiresolution and subdivision, Image processing, Numerical approximation, Numerical methods related to PDEs

This introductory paper describes the main topics of this special issue, dedicated to Leonardo Traversoni, known at international level as the promoter of the conference series "Multivariate Approximation: Theory and Applications", to celebrate his 60th birthday.

Introduction

The …rst "Multivariate Approximation: Theory and Applications" conference was held in 1995 at Cancun, Mexico. Each time, a special issue in a Journal was realized except for the conference organized in 1999:

-Journal of Computational and Applied Mathematics (Elsevier) 73, in 1996 (A. Le Méhauté, L.L. Schumaker and L. Traversoni) for the MATA 1995 conference, -no special issue for the Second International Conference on Multivariate Scattered Data Fitting, organized by P. Gonzalez-Casanova, A. Le Méhauté, L.L. Schumaker The occasion of this special issue for Journal of Computational and Applied Mathematics in 2012 is also the celebration of the 60th birthday of Leonardo Traversoni. Since from 1995 Leonardo Traversoni has been the main organizer of a conference series entitled "Multivariate Approximation: Theory and Applications", we decided to have a special issue in his honour with the same title.

Main themes of the special issue

This special issue of the journal of Computational and Applied Mathematics contains a selected collection of 20 contributions, dealing with recent progress in the …eld of "Multivariate Approximation: Theory and Applications" (see the References below for the complete list of these papers). All of them have been refereed according to the standard peer review process of the journal. The rate of acceptance is 57% (20/35). The papers in this special issue cover the following topics:

1. Interpolation [START_REF] Beccari | Construction and characterization of non-uniform local interpolating polynomial splines[END_REF][START_REF] Jakliµ | Hermite interpolation by rational G k motions of low degree[END_REF][START_REF] Karciauskas | Non-uniform interpolating subdivision and splines[END_REF][START_REF] Schumaker | On Hermite Interpolation with Polynomial Splines on T-meshes[END_REF] 2. Multiresolution and subdivision [START_REF] Charina | Polynomial Reproduction of Multivariate Scalar Subdivision Schemes[END_REF][START_REF] Davydov | Re…nable C 2 Piecewise Quintic Polynomials on Powell-Sabin-12 Triangulations[END_REF][START_REF] Kadri-Harouna | E¤ective construction of divergence-free wavelets on the square[END_REF][START_REF] Zarrabeitia | Multiresolution terrain modeling using level curve information[END_REF] 3. Image processing [START_REF] Bonamy | Split Bregman iteration and in…nity Laplacian for image decomposition[END_REF][START_REF] Derfoul | Image processing tools for better incorporation of 4D seismic data into reservoir models[END_REF][START_REF] Jung | Variational Multiframe Restoration of Images Degraded by Noisy (Stochastic) Blur Kernels[END_REF][START_REF] Guyader | Gradient …elds approximation: application to registration processes in image processing[END_REF] 4. Numerical approximation [START_REF] Beatson | Faster fast evaluation of thinplate splines in two dimensions[END_REF][START_REF] Bozzini | The detection and recovery of discontinuity curves from scattered data[END_REF][START_REF] Cervantes Cabrera | Vector …eld approximation using radial basis functions[END_REF][START_REF] Huang | An Optimization Based Empirical Mode Decomposition Scheme[END_REF][START_REF] Levesley | A Multiplier Version of the Bernstein Inequality on the Complex Sphere[END_REF] 5. Numerical methods related to PDEs [START_REF] Barucq | Upscaling for the Laplace Problem using a Discontinuous Galerkin Method[END_REF][START_REF] Siqueira | A new procedure for the construction of hierarchical high order Hdiv and Hcurl …nite element spaces[END_REF][START_REF] Heindl | An Adaptive Wavelet Viscosity Method for Systems of Hyperbolic Conservation Laws[END_REF] In the following subsections we provide a short overview of such topics and we describe the corresponding contributions.

Interpolation

Interpolation is still a hot research topic. A variety of interpolation methods, based either on spline or subdivision approaches, are currently under investigation with the aim of producing smooth shapes passing through a given data set. In [START_REF] Beccari | Construction and characterization of non-uniform local interpolating polynomial splines[END_REF] the authors present a general framework for the construction and characterization of piecewise-polynomial local interpolants with given smoothness and approximation order, de…ned on non-uniform knot partitions. Thanks to its generality, the proposed framework allows to recover uniform local interpolating splines previously proposed in the literature, to generalize them to the non-uniform case, and to complete families of arbitrary support width. Furthermore it provides new local interpolating polynomial splines with prescribed smoothness and polynomial reproduction properties.

[16] also deals with the development of a framework, but for generating and analyzing non-uniform interpolating subdivision algorithms, closely related to non-uniform splines. Families of symmetric interpolating 2n-point schemes of smoothness C n 1 are presented for n = 2; 3; 4; 5, as well as a non-uniform 6-point scheme with C 3 continuity. As an extension of basic interpolation, Hermite interpolation is aimed at producing a curve or surface that not only passes through a given set of points, but also matches the slope at those points. [START_REF] Jakliµ | Hermite interpolation by rational G k motions of low degree[END_REF] deals with the problem of interpolating motions of a rigid body in the Hermite sense with geometric continuity conditions. To this end, …rst rational motions are de…ned and the concept of geometric continuity is adapted to them. Then, the general G k continuous interpolation problem for motions is formulated and an approach for rational spline motions with G 1 or G 2 smoothness and interpolating a sequence of assigned positions/orientations is introduced. In [START_REF] Schumaker | On Hermite Interpolation with Polynomial Splines on T-meshes[END_REF] authors focus on the problem of constructing Hermite interpolants using polynomial splines on T-meshes. In particular, the space of bivariate splines of degree (componentwise) (d 1 ; d 2 ) and smoothness (r 1 ; r 2 ), with d 1 2r 1 + 1; d 2 2r 2 + 1 over regular T-meshes without cycles, is considered. Error bounds for Hermite interpolation of smooth functions are provided and compared with similar error bounds for Hermite interpolation by tensor product polynomials.

Multiresolution and subdivision

The strength and popularity of subdivision schemes is well-established in many …elds. Among these, for instance, we …nd the construction of smooth curves and surfaces and the generation of re…nable functions. It is wellknown that re…nability is a very useful property since it allows to generate a multiresolution analysis and hierarchical structures (or multilevel approaches).

In [START_REF] Charina | Polynomial Reproduction of Multivariate Scalar Subdivision Schemes[END_REF] the authors derive necessary and su¢ cient conditions for a multivariate subdivision scheme to reproduce polynomials up to a certain degree. These conditions are algebraic and can easily be checked by analysing the symbol of the scheme and its derivatives. They nicely complement the known algebraic conditions for polynomial generation. A key element in the analysis is the derivation of a suitable parameterization for a given subdivision scheme, that is, a sequence of parameter values to which the generated data at each level should be attached. In [START_REF] Davydov | Re…nable C 2 Piecewise Quintic Polynomials on Powell-Sabin-12 Triangulations[END_REF] the authors present a construction of nested spaces of degree 5, C 2 macro-elements on triangulations of a polygonal domain obtained by uniform re…nements of an initial triangulation and a Power-Sabin-12 split. The advantage of this construction is in the fact that the degree of the re…nable macro-elements is substantially lower than the degree of the currently existing proposals. [START_REF] Zarrabeitia | Multiresolution terrain modeling using level curve information[END_REF] illustrates an interesting application of multiresolution representations to the …eld of digital terrain modelling. The term digital terrain model refers to a representation of the earth's surface in digital form, without including details such as vegetation, bridges, buildings, etc. It is very useful to visualize the terrain in a computer and to study its properties. In [START_REF] Zarrabeitia | Multiresolution terrain modeling using level curve information[END_REF] the authors propose an algorithm for computing a multiresolution representation of a digital terrain model using level curves. The input curves are sorted by their importance in such a way that the n most relevant curves are contained in the n-th resolution level. Finally, [START_REF] Kadri-Harouna | E¤ective construction of divergence-free wavelets on the square[END_REF] is devoted to an e¤ective construction of divergence-free wavelets on the square [0; 1] [0; 1], with suitable boundary conditions. To this end it combines the construction of multiresolution analysis of H 1 0 ([0; 1]) and the construction of biorthogonal wavelets linked by derivation. As an example, a divergence-free decomposition of a velocity …eld of lid driven cavity ‡ow is computed and the interpretation of the result is provided.

Image processing

The development of image processing tools has been of great importance in the last years. Many applications require such tools: segmentation for medical applications, noise removal in Medicine and Geophysics, inpainting, image restoration, registration classi…cation and so on. For a long time a pure informatics topic, image processing has now become a strong theme in the mathematical community. The contribution of mathematicians was to provide rigorous models of imaging problems. These include variational approaches, the study of existence / uniqueness of solutions, not to mention the numerical aspects. Parallel implementations (sometimes with GPU) have also been proposed. This is a theme very active, having very strong developments. In this secial issue, several imaging problems a studied.

In [START_REF] Jung | Variational Multiframe Restoration of Images Degraded by Noisy (Stochastic) Blur Kernels[END_REF], the authors deal with the restoration of images degraded by a noisy blur kernel. This modelling can be encountered for instance in astronomy or in medical imaging. They empirically show that in several cases classical methods such as the Rudin-Osher model fail to properly clean the degraded image, visual artifacts being still visible, which motivates the introduction of the multiframe approach. The idea is to adopt the multiframe model, which consists in using several degraded frames in the reconstruction of a single restored image. The multiframe model is introduced into two variational minimization problems. They also propose an application of their framework for joint restoration and binary segmentation. Numerical results are given on color images, as well as on real video datasets.

In [START_REF] Bonamy | Split Bregman iteration and in…nity Laplacian for image decomposition[END_REF],This paper is concerned with image decomposition problem which consists in separating the geometric component u of an image f : ! R; from the oscillatory part v. The authors introduce auxiliary variables that naturally emerge from the Helmholtz-Hodge decomposition for smooth …elds, and which yields to the minimization of the L 1 -norm of the gradients of the new unknowns. This constrained minimization problem is transformed into a series of unconstrained problems by means of Bregman Iteration. The authors prove the existence of minimizers for the involved subproblems. Then a gradient descent method is selected to solve each subproblem, becoming related, in the case of the auxiliary functions, to the in…nity Laplacian. Existence/ Uniqueness as well as regularity results of the viscosity solutions of the PDE introduced are proved. Numerical examples are also given.

In [START_REF] Guyader | Gradient …elds approximation: application to registration processes in image processing[END_REF], the authors present a vector …eld approximation. In the modelling, they use classical tools such that a D m -splines approach, leading to the minimization of a functional on a Hilbert space. Several theoretical results are given, and applications on image registration is shown. In image processing, registration is an important task since it allows comparing a subject/time variant template image T with an unbiased reference image R. More precisely, given a reference R and a template T , de…ned on image domain, the goal is to …nd a smooth, invertible transformation to map T into an image similar to R. For images of the same modality, a well-registered template has geometric features and intensity distribution matched with the reference.

In [START_REF] Derfoul | Image processing tools for better incorporation of 4D seismic data into reservoir models[END_REF], the authors are working with speci…c datasets : geophysical data. Calibrating reservoir models to ‡ow data involves history matching processes. Model parameters are iteratively adjusted to minimize the mis-…t between the real data and the corresponding simulated responses. The current formulation used to quantify the seismic data mismatch is neither representative of the di¤erence between two images, nor of matching quality. The authors describe an alternative formulation, using methods rooted in image processing (such that Chan-Vese segmentation method, NL means, Hausdor¤ distance...), to extract relevant information from seismic images and compute their dissimilarity. Numerical results are given.

Numerical approximation

Splines, orthogonal polynomials and Radial Basis funtions (RBF) are still a very active subject for research in approximation, both from a theoretical point of view and for applications. It usually leads to numerical methods to approximate or interpolate di¤erent kind od datasets.

[2] presents a new algorithm, based on a multipole method, for fast evaluation of thinplate splines in two dimensions, providing experimental evidence of its e¢ ciency. In [START_REF] Bozzini | The detection and recovery of discontinuity curves from scattered data[END_REF] the authors present a numerical method for the detection of faults and gradient faults of two dimensional functions when a sample of N uniformly scattered and noisy data is given. The method recognizes the presence of a discontinuity curve by a suitable statistic. The recovering of such curve is discussed and a computational bound of the pointwise error is provided together with a study of the convergence properties of the algorithm as N grows to in…nity. In [START_REF] Cervantes Cabrera | Vector …eld approximation using radial basis functions[END_REF] the authors investigate the performance of RBF-PDE methods to approximate solenoidal vector …elds. More precisely, they perform a numerical investigation between RBF global and local methods in order to study the possible advantages of local methods for the approximation of vector …elds.

The main interest of this approach is to compare the local Hermite interpolation (LHI) method, using inverse multiquadrics, against the non symmetric Kansa's collocation method to approximate solenoidal …elds at great scale. The authors of [START_REF] Huang | An Optimization Based Empirical Mode Decomposition Scheme[END_REF] propose an optimization based EMD method (OEMD) for one-dimensional signals. An interesting aspect of the proposed method is that the upper and lower envelopes of the signal are constructed by solving a convex optimization problem instead of using the cubic spline interpolation as in the original EMD method. The main advantage of this construction is that it does not create over-or undershoots that have been observed in the original EMD based on the cubic spline interpolation. [START_REF] Levesley | A Multiplier Version of the Bernstein Inequality on the Complex Sphere[END_REF] discusses Bernstein type inequalities for certain operators on functions de…ned on the complex sphere that include fractional versions of the Laplace-Beltrami operator. Moreover, it contains a new result relating a bivariate sum involving Jacobi polynomials and Gegenbauer polynomials, which relates the sum of reproducing kernels on spaces of polynomials irreducibly invariant under the unitary group, with the reproducing kernel of the sum of these spaces, which is irreducibly invariant under the action of the orthogonal group.

Numerical methods related to PDEs

The second half of the twentieth century has witnessed the advent of Partial Derivative Equations (PDE) linked to the modelling of many problems like Computational Fluid Dynamics (CFD), a new branch of applied mathematics that deals with numerical simulation of ‡uid ‡ows, or Level set Methods (Hamilton-Jacobi) or many others famous PDE (Navier-Stokes, Saint-Venant, .Schrödinger, Waves, Maxwell and so on...). Many tools have been introduced in this period, including …nite di¤erence, …nite elements, …nite volumes to process the solution of such problems. In this issue, several papers bring novelty in this area.

In [START_REF] Barucq | Upscaling for the Laplace Problem using a Discontinuous Galerkin Method[END_REF], the authors quantify the performance and numerical advantages of the operator-based upscaling technique applied to the Laplace problem using a discontinuous Galerkin method. Such approach permits to get the …ne scale e¤ects with computations on coarse meshes, leading to reduced computational costs, instead of computing the solution of the problem on a re…ned mesh in case of small scales.

In [START_REF] Heindl | An Adaptive Wavelet Viscosity Method for Systems of Hyperbolic Conservation Laws[END_REF], the authors present a viscosity method based on wavelets for systems of conservation laws (Euler's equations for gas dynamics). As the viscosity stabilization produces some parasitical oscillations (Gibbs phenomena), the authors discuss di¤erent postprocessing techniques known from data and image processing together with a number of numerical comparisons.

In [START_REF] Siqueira | A new procedure for the construction of hierarchical high order Hdiv and Hcurl …nite element spaces[END_REF], the authors present a new …nite elements approach, proposing a construction of H(div) and H(curl) …nite element basis functions for triangles and quadrilaterals.

  and L. Traversoni in April 1999 at Puerto Vallarta, Mexico -Numerical Algorithms (Springer) 39, 2005 for the Third Multivariate Approximation: Theory and Applications conference organized in April 2003 at Cancun, Mexico, -Numerical Algorithms (Springer) 48, 2008 for the Fourth Multivariate Approximation: Theory and Applications conference organized in May 2007 at Cancun, Mexico,

Acknowledgements

We would like to thank the contributors to this volume, Luc Wuytack, the editor-in-chief, for giving us the opportunity to publish this special issue and the publishing sta¤ at JCAM for their help in making this special issue come to be. We also want to express our warm thanks to all the reviewers for their hard work in ensuring the quality of the …nal papers.


Guillaume Bécan

Sana Ben Nasr

Mathieu Acher

Benoit Baudry

WebFML: Synthesizing Feature Models Everywhere

Keywords: D.2.13 [Software Engineering]: Reusable Software; D.2.9 [Software Engineering]: Management-Software configuration management Ontologic-Aware Synthesis, Feature Modeling Environment, Reverse Engineering Feature Models

Feature Models (FMs) are the de-facto standard for documenting, model checking, and reasoning about the configurations of a software system. This paper introduces WebFML a comprehensive environment for synthesizing FMs from various kinds of artefacts (e.g. propositional formula, dependency graph, FMs or product comparison matrices). A key feature of WebFML is an interactive support (through ranking lists, clusters, and logical heuristics) for choosing a sound and meaningful hierarchy. WebFML opens avenues for numerous practical applications (e.g., merging multiple product lines, slicing a configuration process, reverse engineering configurable systems).

INTRODUCTION

Feature Models (FMs) are by far the most popular notation for representing and reasoning about common and variable properties (features) of a system [START_REF] Apel | An overview of feature-oriented software development[END_REF][START_REF] Berger | A survey of variability modeling in industrial practice[END_REF]. FMs offer a simple yet expressive way to define a set of legal configurations (i.e., combinations of features) [START_REF] Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF][START_REF] Czarnecki | Feature models are views on ontologies[END_REF][START_REF] Pohl | A performance comparison of contemporary algorithmic approaches for automated analysis operations on feature models[END_REF][START_REF] Thüm | Reasoning about edits to feature models[END_REF]. FMs also define an ontological semantics [START_REF] Czarnecki | Feature models are views on ontologies[END_REF]: a tree-like hierarchy and feature groups organize features into multiple levels of increasing detail.

Both configuration and ontological aspects of FMs are important. First, the proper handling of the configuration set is unquestionable: it should not be too large (otherwise some unsafe compositions of the features are allowed) or too narrow (otherwise it translates as a lack of flexibility in the software project). Second, a doubtful feature hierarchy may pose severe problems for a further exploitation by automated transformation tools or by stakeholders that need to understand, maintain and exploit an FM. For instance, the FM f mu of Figure 1a characterizes the same set of configurations than the FM f mg of Figure 1b, but with an inappropriate ontological semantics (e.g. Java is located below Storage rather than being child feature of Programming Language).

As an FM should both conform to a configuration semantics and exhibit an appropriate hierarchy, a manual elaboration or maintenance of an FM is usually time-consuming and error-prone -even for a small number of features and dependencies [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] Bécan | Breathing Ontological Knowledge Into Feature Model Management[END_REF][START_REF] She | Reverse engineering feature models[END_REF].

WebFML provides automated techniques for speeding up and supervising the building process of FMs. WebFML also aims to ease the mechanical translation of artefacts with variability into FMs. It enables practitioners to reduce their effort and avoid accidental complexity when (re)engineering or maintaining their variability models. In a nutshell, WebFML is a comprehensive environment for synthesizing FMs from various kinds of artefacts:

• product comparison matrices: a specific form of spreadsheets documenting the features of products under comparison. By giving a specific interpretation of their semantics, these matrices can be interpreted as FMs [START_REF] Sannier | From comparison matrix to variability model: The wikipedia case study[END_REF].

• dependency graphs which can be extracted from configuration files of build systems (e.g. pom.xml files in Maven) [START_REF] Abbasi | Reverse engineering web configurators[END_REF][START_REF] Acher | Extraction and evolution of architectural variability models in plugin-based systems[END_REF].

• compilation directives and source code in which features and their dependencies can be mined [START_REF] Nadi | Mining configuration constraints: Static analyses and empirical results[END_REF][START_REF] She | Reverse engineering feature models[END_REF];

• propositional formulas in conjunctive or disjunctive normal form [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] She | Feature Model Synthesis[END_REF] • a (set of ) FM(s): slicing, merging or refactoring existing FMs are instances of the synthesis problem we are addressing with WebFML [START_REF] Acher | Composing your compositions of variability models[END_REF][START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Hubaux | Domain Engineering: Product Lines, Conceptual Models, and Languages, chapter Separating Concerns in Feature Models: Retrospective and Multi-View Support[END_REF].

In addition, some outputs of mining tools (e.g., for extracting features and their constraints from source code [START_REF] Dietrich | A robust approach for variability extraction from the linux build system[END_REF][START_REF] Nadi | Mining configuration constraints: Static analyses and empirical results[END_REF][START_REF] Rabkin | Static extraction of program configuration options[END_REF][START_REF] She | Reverse engineering feature models[END_REF], requirements [START_REF] Niu | Extracting and modeling product line functional requirements[END_REF][START_REF] Weston | A framework for constructing semantically composable feature models from natural language requirements[END_REF] or product descriptions [START_REF] Bécan | Automating the formalization of product comparison matrices[END_REF][START_REF] Davril | Feature model extraction from large collections of informal product descriptions[END_REF][START_REF] Hariri | Supporting domain analysis through mining and recommending features from online product listings[END_REF]) are amenable to an input format (e.g., formula) of WebFML.

An unique feature of WebFML is its interactive support for choosing a sound and meaningful hierarchy. Ranking lists and clusters guide users in the choice of a relevant hierarchy among the thousands of possibilities. For a given feature, siblings or parent candidates are presented to users and sorted according to the syntactic or semantic similarities between feature names. We develop generic, state-ofthe-art heuristics [START_REF] Bécan | Breathing Ontological Knowledge Into Feature Model Management[END_REF] [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF][START_REF] Krueger | Biglever software Gears and the 3-tiered spl methodology[END_REF]32,[START_REF] Thüm | Featureide: An extensible framework for feature-oriented software development[END_REF], we are unaware of an environment that considers both configuration and ontological aspects when synthesizing an FM.

Another strength of WebFML is that numerous operations have been developed on top the synthesis support. Likewise practitioners can envision the use of WebFML in practical scenarios: merging of multiple product lines [START_REF] Acher | Composing your compositions of variability models[END_REF]; slicing of a configuration process into different steps or tasks [START_REF] Hubaux | Domain Engineering: Product Lines, Conceptual Models, and Languages, chapter Separating Concerns in Feature Models: Retrospective and Multi-View Support[END_REF]; sound refactoring of FMs [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF], especially when fully automated techniques produce incorrect FMs; reverse engineering of configurable systems through the combined use of composition, decomposition and refactoring operators [START_REF] Abbasi | Reverse engineering web configurators[END_REF][START_REF] Acher | Extraction and evolution of architectural variability models in plugin-based systems[END_REF].

BACKGROUND AND MOTIVATION

The formalism of FMs offers syntactic constructions to attach variability information to features organized in the hierarchy. When decomposing a feature into subfeatures, the subfeatures may be optional, mandatory or may form Mutex, Xor, or Or groups.

The variability restricts the possible combinations of features (i.e., configurations): features Java and PHP cannot be both selected since the two features belong to a Xor-group in Figure 1b; every configuration of Figure 1b necessarily includes the two mandatory features Storage, License and the root Wiki, etc. Importantly, the feature hierarchy also contributes to the definition of the configuration semantics: all features, except the root, logically imply their parent.

The FM synthesis problem [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF] is at the heart of many reverse engineering procedures (see, e.g. [START_REF] Abbasi | Reverse engineering web configurators[END_REF][START_REF] Acher | Extraction and evolution of architectural variability models in plugin-based systems[END_REF][START_REF] Davril | Feature model extraction from large collections of informal product descriptions[END_REF][START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF][START_REF] She | Reverse engineering feature models[END_REF]). FM management operations are also impacted by the problem [START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] She | Feature Model Synthesis[END_REF]. It can be formulated as follows: given a set of features' names and Boolean dependencies among features typically encoded as a propositional formula φ in conjunctive or disjunctive normal form, the problem is to synthesize an FM with a sound configuration semantics. We also expect the FM to be maximal, i.e. as much information as possible is represented in the diagrammatic part of the FM (see a formalization in [START_REF] Andersen | Efficient synthesis of feature models[END_REF]).

WebFML tackles a generalization of the FM synthesis problem by providing an interactive support in order to synthesize maximal FMs both i) conformant to the configuration semantics and ii) exhibiting an appropriate ontological semantics. WebFML also targets different kinds of inputs amenable to the synthesis problem.

ENVIRONMENT

Features of the environment

Our procedure is based on the idea that a feature tends to share the same context as its parent and siblings. Thus, we rely on a series of heuristics to i) rank parent candidates of each feature according to their semantic similarity and ii) compute clusters of conceptually similar features. These types of information can be interactively complemented or refined by a user, and if needed, an optimum branching algorithm can synthesize a complete FM. Specifically, our tool offers an interactive mode where the user can import a formula (e.g., in DIMACS format), synthesizes a complete FM and export the result in different formats. During the FM synthesis, the graphical user interface displays a ranking list of parent candidates for every feature, a list of clusters, a list of cliques (features that are always present together) and a graphical preview of the FM under construction (see Figure 2, E , F , G andH ). In addition, WebFML is built on top of FAMILIAR [START_REF] Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF] which provides numerous reasoning and scripting capabilities for FMs. Overall, the features available are the following:

• select or ignore a parent candidate in the ranking lists (see Figure 2, F );

• select a parent for a cluster (or a clique) within the cluster's features or any potential parent feature outside the cluster (see Figure 2, G and H ). The user can also consider a subset of a cluster when selecting the parent;

• undo a previous choice (see Figure 2,C );

• define the different heuristics and parameters of the synthesis (see Figure 2,B );

• automatically generate a complete FM according to previous choices and selected heuristics (see Figure 2, C );

• use FAMILIAR capabilities within an integrated console (see Figure 2, I );

• manage FAMILIAR script files and previously computed variables (see Figure 2, A and D ).

A typical usage is to perform some choices, generate a complete FM with the heuristics and the optimum branching algorithm and reiterate until having a satisfactory model.

Interactive edits of parent candidates and clusters

The ranking lists of parent candidates and the clusters form the main information during the synthesis. As the amount of information can be overwhelming, we propose a tree explorer view for manipulating and visualizing both parent candidates and clusters (see Figure 2, F , G andH ). A tree explorer view is scalable: it allows to focus on specific features or clusters while the other information in the explorer can be hidden. During the synthesis, the user interacts almost exclusively by clicking on the elements of these explorers. Clicking on a feature in parent candidate lists allows to select or ignore a parent candidate (see Figure 3a). Users can also click on a cluster to choose a parent for all the cluster's features among their common parent candidates (see Figure 3b). If the cluster contains the desired parent, the user can also click on this feature and select the children within the cluster. In both cases, the user can deselect some features to consider only a subset of the cluster. The same behaviour applies to cliques (see Figure 3c). Finally, we propose a graphical preview of the FM based on Dagre1 and D32 javascript libraries. It allows to summarize the previous choices and have a global and familiar view of the current result (see Figure 2,E ).

Implementation of heuristics

Hierarchical clustering is performed by the Hac3 library. The optimum branching algorithm for computing a complete FM is based on Tarjan's algorithm [START_REF] Tarjan | Finding optimum branchings[END_REF]. We developed six heuristics based on specialized libraries. Smith-Waterman and Levenshtein compute syntactical similarity based on words' morphology. They come from the Simmet-rics4 library. PathLength and Wu&Palmer heuristics rely on extJWNL5 which handles the communication between the lexical database WordNet [START_REF] Miller | Wordnet: a lexical database for english[END_REF] and our tool. Wikipedia Miner6 offers an API to browse Wikipedia's articles offline and compute their relatedness [START_REF] Milne | An open-source toolkit for mining wikipedia[END_REF]. We used this tool on the english version of Wikipedia and Wiktionary which form the last two heuristics.

RELATED WORK

There are numerous existing academic or industrial tools for specifying and reasoning about FMs. FeatureIDE [START_REF] Thüm | Reasoning about edits to feature models[END_REF][START_REF] Thüm | Featureide: An extensible framework for feature-oriented software development[END_REF] is an Eclipse-based IDE that supports all phases of featureoriented software development for the development of product lines (domain analysis, domain implementation, requirements analysis and software generation). FAMA [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF] is a framework for the automated analysis of FMs integrating some of the most commonly used logic representations and solvers. Our environment is compatible with most of these tools. However none of the existing tools propose support for synthesizing, merging, slicing, or refactoring FMs.

Techniques for synthesising an FM from a set of dependencies (e.g., encoded as a propositional formula) or from a set of configurations (e.g., encoded in a product comparison matrix) have been proposed [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF][START_REF] Janota | Model construction with external constraints: An interactive journey from semantics to syntax[END_REF][START_REF] She | Reverse engineering feature models[END_REF][START_REF] Zhang | Mining complex feature correlations from software product line configurations[END_REF]. An important limitation of prior works is that they neglected ontological aspects of an FM, i.e., the user support is either absent or limited for identifying an appropriate feature hierarchy. Without adequate guidance for users, the resulting hierarchy is likely to be far from an ideal result and/or the synthesis process can be daunting and time-consuming.

She et al. proposed specific heuristics based on textual feature descriptions for the operating system domain [START_REF] She | Reverse engineering feature models[END_REF]. Davril et al. [START_REF] Davril | Feature model extraction from large collections of informal product descriptions[END_REF] presented a fully automated approach, based on prior work [START_REF] Hariri | Supporting domain analysis through mining and recommending features from online product listings[END_REF], for constructing FMs from publicly available product descriptions found in online product repositories and marketing websites such as SoftPedia and CNET. The proposal is evaluated in the anti-virus domain.

Our techniques operate over a predefined set of features and dependencies. We do not assume any additional inputs for selecting the feature hierarchy.

Weston et al. [START_REF] Weston | A framework for constructing semantically composable feature models from natural language requirements[END_REF] provided a tool framework ArborCraft which automatically processes natural-language requirements documents into a candidate FM, which can be refined by the requirements engineer. Alves et al. [START_REF] Alves | An exploratory study of information retrieval techniques in domain analysis[END_REF], Niu et al. [START_REF] Niu | Concept analysis for product line requirements[END_REF], and Chen et al. [START_REF] Chen | An approach to constructing feature models based on requirements clustering[END_REF] applied information retrieval techniques to abstract requirements from existing specifications, typically expressed in natural language. These works do not consider precise logical dependencies and solely focus on ontological semantics. As a result users have to manually set the variability information. Moreover, a risk is to build an FM in contradiction with the actual dependencies of a system. As a summary, our environment addresses both configuration and ontological aspects of an FM.

CONCLUSION

We presented WebFML an environment with an interactive support for synthesizing feature models from various kinds of artefacts (e.g. propositional formula, dependency graph, FMs or product comparison matrices). A key feature of WebFML is to address both configuration and ontological aspects of feature models. Ranking lists, clusters and logical heuristics guide users throughout the interactive process to select a sound and meaningful hierarchy. WebFML not only open avenues for reverse engineering scenarios; slicing of a configuration process, merging of multiple product lines, or refactoring of an existing system are also made possible.

Our recent evaluation of the synthesis techniques showed that the interactive support of WebFML is crucial, otherwise the resulting hierarchy of the FM is far from the expectation. We also demonstrated that WebFML provides state-of-theart user support -either for fully synthesizing FMs or for assisting users through ranking lists and clusters [START_REF] Bécan | Breathing Ontological Knowledge Into Feature Model Management[END_REF].

Interestingly enough, a distributed effort involving several collaborators can even be considered to synthesize very large feature models. We believe the publicly available provision of the environment (see http://tinyurl.com/WebFMLDemo) is an important step towards effective reverse engineering or maintenance of highly configurable systems more and more reported in the industry or in the open source community.

Figure 2 :

 2 Figure 2: Interface of the environment during synthesis

Figure 3 :

 3 Figure 3: User interaction during FM synthesis

Java Wiki Programming Language Storage License PHP Open Source Proprietary License MySQL PostgreSQL

								Wiki
	EQ = {PostgreSQL <=> Proprietary License}		Programming Language		Storage	License
	RE = {Java => Programming Language,
	PHP => Programming Language,
	Programming Language => Java v PHP}
	EX = {Proprietary License => !Programming Language,
	PHP => !Java}	Mutex	Or	Mandatory	Java	PHP	MySQL	PostgreSQL	Proprietary License	Open Source
	0...1		Xor	Optional		EQ = {PostgreSQL <=> Proprietary License} EX = {Proprietary License => !Programming Language}
	(a) A FM f mu with a doubtful ontological semantics	(b) A FM f mg with a more appropriate ontolog-
					ical semantics
	Figure 1: For a same set of configurations, two possible yet different FMs
	of a wide range of academic or industrial feature modeling
	tools
							(e.g., based on Wordnet or Wikipedia)
					applicable without prior knowledge to the artefacts exposed
					above. WebFML also offers extensible mechanisms (plugins)
					to integrate specialized heuristics. Despite the availability

https://github.com/cpettitt/dagre

http://d3js.org/

http://sape.inf.usi.ch/hac

http://sourceforge.net/projects/simmetrics

http://extjwnl.sourceforge.net

http://sourceforge.net/projects/wikipedia-miner

Acknowledgements

This work is partially supported by the French BGLE Project CONNEXION.