Romain Arcila
email: romain.arcila@inrialpes.fr

S Kartik Buddha

Franck Hétroy
email: franck.hetroy@grenoble-inp.fr

Denis
email: fdenis@liris.cnrs.fr

Florent Dupont
email: florent.dupont@liris.cnrs.fr

Florence Denis

A Framework for Motion-Based Mesh Sequence Segmentation

Keywords: Mesh Sequence, Mesh Animation, Segmentation, Matching

In this paper, we present a complete framework to produce motion-based geometric segmentation of mesh sequences: each segment corresponds to a mesh region that tends either to move rigidly, or to be stretched in a uniform way. We take a sequence of meshes with varying number of vertices as input and match them by pairs. This allows us to find the approximated displacement vector of each vertex of the first frame all along the sequence. Using these displacement vectors, an initial segmentation is performed on the first pair of frames, clustering vertices into static, stretched and rigidly moving regions. This segmentation is then refined after each matching. Our segmentation is computed on the fly, and lets us find the exact frame when each transformation (rotation, translation, stretch) appears. We have validated our method both on dynamic meshes and unconstrained mesh sequences.

INTRODUCTION AND RELATED WORK 1.Introduction

In computer graphics, segmentation of surface meshes is an important and challenging problem which involves partitioning a mesh into smaller segments of homogeneous characteristics. By doing so, a simplified representation of the mesh is obtained. This representation is more meaningful and easier to analyse. Segmentation plays an important role in diverse applications like texture mapping [START_REF] Lévy | Least squares conformal maps for automatic texture atlas generation[END_REF], compression [START_REF] Karni | Spectral compression of mesh geometry[END_REF], mesh simplification [START_REF] Garland | Hierarchical face clustering on polygonal surfaces[END_REF] and 3D shape retrieval [START_REF] Zuckerberger | Polyhedral surface decomposition with applications[END_REF] among many others. The result of the segmentation required in each case may vary depending on the type of application. While segmentation of static meshes is a well-known topic (see [START_REF] Shamir | A survey on mesh segmentation techniques[END_REF] for a survey), segmentation of mesh sequences is a more recent research field. Here "segmentation" can have two different meanings: motionbased geometry segmentation aims at clustering vertices or faces based on their motions while temporal segmentation clusters meshes of the sequence (also called frames) into meaningful sub-sequences. In this paper, we focus on motion-based geometry segmentation.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

Related Work

Mesh sequences can be split into two categories. A dynamic mesh is a sequence with fixed number of vertices and fixed neighbourhood relationships between vertices. In other words, only the 3D coordinates of the vertices change through time. An unconstrained mesh sequence (or time-varying mesh or 3D video) is represented by a sequence of meshes where the number of vertices, as well as the number of faces and connectivity, may vary along the sequence. Typically, dynamic meshes are created from modelers and animation software, while unconstrained mesh sequence are captured from video or computed from (e.g. fluid) simulation.

A few methods for motion-based geometry segmentation of dynamic meshes have been proposed [START_REF] Lengyel | Compression of time-dependent geometry[END_REF][START_REF] Amjoun | Efficient compression of 3d dynamic mesh sequences[END_REF]. Some of them [START_REF] De Aguiar | Automatic Conversion of Mesh Animations into Skeleton-based Animations[END_REF][START_REF] Lee | Segmenting a deforming mesh into near-rigid components[END_REF]) segment a dynamic mesh into rigid components.

Segmentation of unconstrained sequence meshes is a difficult task since there is no one-to-one mapping between vertices of two successive frames. This mapping has to be explicitly computed for each pair of frames. Cuzzolin et al. [CMK + 08] and Yamasaki et al. [START_REF] Lee | Hierarchical mesh decomposition and motion tracking for time-varying-meshes[END_REF] have performed such segmentations for mesh sequences, however the former computes only protrusions (extremities) segmentation while the latter uses an additional skeleton. [START_REF] Sundaresan | Acquisition of articulated human body models using multiple cameras[END_REF] has been designed to solve this problem using voxel clustering, but it suffers from inherent voxelisation problems (low resolution leads to poor results while hight resolution leads to high computation time). [KSMH09, JZvK07, MHK + 08] compute the mapping between any two meshes, but their methods are not designed for sequences so they do not take the temporal coherency into account. Starck et al. [START_REF] Starck | Correspondence labelling for wide-timeframe free-form surface matching[END_REF] computes the matching for distant frames in a sequence, but uses additional video information. Varanasi et al. [START_REF] Varanasi | Temporal surface tracking using mesh evolution[END_REF] tracks the displacement of vertices of the first mesh all along the sequence, but does not provide a matching for all frames.

In this article, we propose a framework (Section 2) to perform a stretched and rigid motion-based geometry segmentation of a mesh sequence, i.e. with varying connectivity and variable number of vertices. A sequence of meshes, without global topological change (the genus of all meshes of the sequence are supposed to be identical), is taken as input. A matching is performed between each pair of meshes (Section 3), which allows to extract the approximated displacement vectors and compute segmentation on the fly (Section 4). A cluster in the resulting segmentation represents a connected region (patch) of the 3D object which either moves almost rigidly, or is stretched in a uniform way. Results are discussed in Section 5.

PIPELINE OVERVIEW

In this section, we describe the complete pipeline of the segmentation process (see Figure 1). The process can be roughly split, at each time step, into 2 parts:

• matching (Sect.3).

• creation or refinement of the segmentation (Sect.4). The algorithm takes as input a sequence of meshes with constant global topology. It registers the first mesh with the second. Displacement vectors between the vertices of the two frames are then computed using the results of the registration.

Mesh Sequence Segmentation

Based on the displacement vectors, an initial segmentation of the first mesh into (i) stretched (and translated), (ii) static and (iii) rigid regions is computed.

For each pair of successive frames in the sequence, we then apply the same matching process and compute the displacement vectors. The initial segmentation is then refined by analyzing the patches motion.

The segmentation of the sequence corresponds to the segmentation on the last frame, remapped on all frames of the sequence.

MATCHING PROCESS

The matching process consists of three successive stages: registration, projection and mapping, which are described in the following subsections. At the end of the matching process, we have the displacement vectors of the vertices of the first frame all along the sequence and the matching of vertices in frame i with vertices in frame i + 1 for 1 ≤ i < N.

Registration

It takes as input an unconstrained mesh sequence and registers it by pair of frames with the Coherent Point Drift algorithm (CPD) [START_REF] Myronenko | Non-rigid point set registration: Coherent point drift[END_REF]. CPD is a probabilistic method for non-rigid registration of point sets. This method is robust to noise and outliers. Registration is performed between the vertices of all adjacent framesvertices in frame F i are registered with those in frame F i+1 for i ranging from 1 to N-1 (see Fig 2 for the notation) to obtain registered point sets R i which are the best alignment of the vertices in F i with those in F i+1 . The number of points in the resulting registered point set R i is equal to the number of vertices in F i .

Projection

Each registered point set R i obtained from the previous step is projected onto the surface of the subsequent frame F i+1 so as to attain a better correspondence between the adjacent frames F i and F i+1 . This projection is performed in the following way:

• For each vertex on the surface of F i+1 , its normal vector to the surface of the mesh is estimated.

• For each point α in R i , the vertex β which is closest to it in F i+1 is first searched. For each projected point, the L2 norm with all the nodes on the surface is calculated and the node with the minimum norm is taken as the closest point of that projected point on the surface.

• Finally, every point α in R i is projected onto the surface of F i+1 along the normal vector of the corresponding closest point β on the surface of F i+1 . The projected point is denoted by P i .

Using the above method, every point in F i is projected onto the surface of F i+1 to obtain P i for i ranging from 1 to N -1. The next step is to find the mapping between the vertices of the two adjacent frames.

Mapping

For sequences with constant number of vertices throughout the sequence, the correspondence between vertices of adjacent frames is easy to obtain. Every vertex in a frame has a corresponding vertex in the other frames in this case. However, such correspondences are not valid anymore when the number of vertices varies at every frame. In such cases, to establish correspondences between two adjacent frames F i and F i+1 , each point in R i is considered separately. The vertex

β D i F i F i+1 R i P i Normal on R i Normal Figure 2: Matching Scheme.
in

F i+1 which is closest to a point R i (α) corresponds to the vertex F i (α).
In this way, a unidirectional mapping of all the vertices of F i with the vertices of F i+1 can be computed to obtain

F i+1 i , for i ∈ [1, N -1]
. Such a mapping is essential if the trajectory of a vertex in a frame has to be followed along the successive frames of the sequence.

Two possible scenarios arise when registering adjacent frames with unequal number of vertices. The first case is when the number of vertices in F i is greater than the number of vertices in F i+1 . In this case, more than one point in F i may be assigned to a vertex in F i+1 . On the other hand, in the case when F i has fewer vertices than F i+1 , some vertices in F i+1 may not have any corresponding vertices in F i . The unidirectional mapping obtained between all adjacent frames can be extended to find the mapping of the vertices in a frame in all the subsequent frames using a recursive procedure. For each vertex α in frame F i , the index of the corresponding vertex in frame F j is given by:

F j i (α) = F j j-1 ((F j-1 i (α))) where j ≥ i (1)
The displacement vectors D i for each vertex in F i are calculated as follows:

D i = P i -F i , i = 1 : N -1
, where the points of P i are the projected points of F i on the surface of F i+1 . Once these displacement vectors are obtained, the displacement map of each vertex in the first frame can be constructed using the correspondences from the F j i arrays. The displacement map is the mapping of vertices in the succeeding frames for each vertex in the first frame, i.e. the displacement map gives the corresponding vertex in any succeeding frame for each vertex in the first frame.

SEGMENTATION

Matching Process and Segmentation

In this section, we present our segmentation method. Our segmentation method relies on correct matching information (i.e. displacement vectors and matching points). As long as this information is provided, any matching method can be used (not only the one we described in section 3). For instance, we also test our segmentation method using [START_REF] Knossow | Inexact matching of large and sparse graphs using laplacian eigenvectors[END_REF], where the matching is computed on the embedding of the meshes using Laplacian embedding (which "unfold" mesh). Segmentation results using this matching methods are discussed in Sect.5.2.

Outline

Our segmentation is a motion-based segmentation. We cluster vertices in rigid components, but contrary to previous segmentation methods, we are also able to detect stretch motion. We are using a refinement method:

1. using the first two meshes and the associated displacement vectors, we compute an initial segmentation (section 4.4).

2. for all other frames of the sequence, we refine the previous segmentation by analyzing the current clusters and splitting them if necessary using displacement vectors and vertex matching (section 4.5).

This refinement approach allows us to:

• process long sequences with lots of vertices. We require only two meshes at a time in memory.

• track transformations. We know at which frame a cluster is created and its type of transformation.

The segmentation of the sequence is the segmentation computed on the last frame. This segmentation is then remapped on the whole sequence using the matching information (section 4.6).

Errors

In the segmentation process, we use a metric denoted as E T to sort clusters by errors. We use the method proposed by Horn [START_REF] Horn | Closed-form solution of absolute orientation using unit quaternions[END_REF] to compute the best possible transformation between two set of points P i and P j , where card(P i ) = card(P j ) and points from P i have direct correspondent in P j . Horn's method returns a translation C T and a rotation C R such as P j = C R * P i + C T . For (P i , P j ), E T can be defined as either:

• Average error: AE(P i , P j ) = 1

card(P i ) ∑ p i ∈P i C R p i +C T -p j .
• Max error: ME(P i , P j ) = max

p i ∈P i C R p i +C T -p j .
• Difference error: DE(P i , P j ) = AE(P i , P j ) -ME(P i , P j ).

Initial segmentation

The initial segmentation is applied on the first mesh F of the sequence. Using the displacement vectors obtained from the matching between the first two frames, we cluster vertices based on three categories, and clustering is applied successively:

1. static vertices: these vertices have no motion (clusters of static vertices are denoted as C static ).

2. stretched vertices: these vertices are in a stretched region (clusters of uniformly stretched vertices are denoted as C stretched ).

3. rigid vertices: motion of these vertices can be described by a rigid transformation (clusters of rigid vertices are denoted as C rigid ).

Clusters are computed as follows. Static vertices are defined by displacement vectors whose norms are under a threshold T static , vertices with a norm greater than this threshold and with collinear (and in the same direction) displacement vectors correspond to stretched vertices. They are gathered into connected regions. Rigid vertices are harder to compute. We use a modified version of the method described in [START_REF] Huang | Non-rigid registration under isometric deformations[END_REF]. To cluster them, we define the extended cluster Ci of C i as C i plus its n closest points (in our experiments, n = 3 is sufficient). The algorithm is:

1. Initialization: each vertex is a cluster.

2. For each cluster, compute the optimal transformation [START_REF] Horn | Closed-form solution of absolute orientation using unit quaternions[END_REF] which maps C of first frame to second frame. Points of second frame are reconstructed from points of C and their associated displacement vectors. Take the cluster C i with the smallest transformation error E t (defined in section 4.3).

3. For all clusters C j which intersect Ci , apply the transformation found for C i to each point of C j . If the error is under a threshold T trans f , merge C j to C i . If no merging happens, take the cluster with the smallest error apart from C i , and do the same. Here the error is defined as the maximum distance between the transformed point of C j and the displaced point of C j .

4. Repeat steps 2 and 3 while merging is possible.

As previously outlined, the order in which the clustering is performed is important. The algorithm first computes C static and C stretched . It then builds a submesh F s = F \ (C static ∪ C stretched ). Rigid clusters are computed at the end on F s , in order to avoid overlapping of rigid regions over static and stretched ones. To avoid small clusters, i.e whose size is inferior to 3% of the mesh, due to noise or small areas around articulations, we merge them to the neighbouring cluster which minimizes the error as in step 3 of the rigid clustering process.

At the end of the initial segmentation process, the mesh of the first frame is decomposed in clusters of different types based on the displacement vectors between the two first frames. The segmentation is then refined using following frames, after each matching.

Refinement

The refinement aims at finding new regions which may appear on a new frame. Each cluster is decomposed (if necessary) into sub-clusters. The process starts from the clusters found at the previous step, i.e. the initial segmentation for frame 2, or the previous refinement in the other cases. It also uses the displacement vectors computed during the matching process. The refinement is done in two steps:

• check previous clusters.

• find new clusters.

A quick checkout step is used to avoid to re-create the same cluster. We check that:

• for static clusters, all displacement vectors norms in a cluster are below the threshold T static ;

• for stretched clusters, displacement vectors are still collinear and with the same direction;

• for rigid clusters, the best transformation between the points of cluster C i at frame F and frame F + 1 is valid. This transformation is computed using Horn's method [START_REF] Horn | Closed-form solution of absolute orientation using unit quaternions[END_REF] (applied to points reconstructed from the previous frame and from the displacement vectors) If the associated error is above T trans f , the transformation is considered as not valid.

All clusters which are still valid are kept unchanged. All other clusters correspond to regions where new transformations are starting. These clusters are decomposed into sub-clusters:

• If the new transformation applies to a whole cluster, this cluster is kept and not decomposed.

• Else, this cluster is decomposed.

This decomposition is similar to the one applied in the initial segmentation: for each cluster C c of the list, the algorithm computes static vertices, stretched vertices and rigid vertices. As before, static and stretched subclusters are computed first and added to the sets of static C static and stretch C stretch clusters.

F s = F \ (C static ∪ C stretch ) is

Remapping

Once all frames have been segmented, we report the segmentation of the last frame on the whole sequence using matching information. As some points can be unmatched, when we report the segmentation from one frame to the other, we apply a region growing method to avoid holes in the segmentation. For each unmatched point p i , we search for the cluster C which contains the maximun number of points in p i neighbourhood and set p i in C.

RESULTS AND DISCUSSION

Matching

Matching results are shown in Figure 4 where the correspondences of vertices between different frames of the horse gallop sequence are displayed. The displacement vectors of these corresponding vertices in the succeeding frames are then used in the segmentation process. On a standard personal computer (core 2 duo, 2.33 GHz), matching of one mesh (8199 vertices) with another vertices (7254) takes 13 minutes. The implementation is performed with MATLAB using a fast implementation of the CPD algorithm based on a fast Gaussian transform. In the matching process, the registration of adjacent frames is the major bottleneck as compared to the projection and mapping parts.

Segmentation Setting of Thresholds and Errors

To handle noise present on unconstrained mesh sequence, we use the threshold T static . For the decimated horse sequence (see Fig. 8), we use a threshold of 1 × 10 -4 , the bounding box of the mesh is 12.3177 . The threshold T trans f corresponds to the motion amplitude tolerated for a cluster on dynamic mesh between two frames. For unconstrained mesh sequence, this threshold should incorporate the slight error of the projected points which contain a small error contrary to models created in a modeler. Segmentation can be refined using different values for T trans f : small values produce more clusters as shown in Fig. 6. This threshold does not depend on vertex density but depends on the amplitude movement between 2 frames.

In our experiments, the Difference Error should be preferred when dealing with dynamic meshes. Indeed, Difference Error avoids to merge clusters with large errors. Clusters with large errors in dynamic meshes are due to change in transformation. On presence of noise and outliers, the Difference Error is too sensible and Average Error becomes the best error type: large error can result from outliers/noise in clusters. Such cluster should not be discarded if it has few outliers. Fig. 5 shows the different errors applied on a dynamic mesh and on a dynamic mesh perturbed with some noise (noise is applied independently on each frame).

Results

Fig. 6 shows the result of our algorithm applies to a dynamic mesh compared to [START_REF] Lee | Segmenting a deforming mesh into near-rigid components[END_REF] and [START_REF] De Aguiar | Automatic Conversion of Mesh Animations into Skeleton-based Animations[END_REF]. As can be seen, our method yields similar results. The main difference with [START_REF] Lee | Segmenting a deforming mesh into near-rigid components[END_REF] deals with cluster's boundaries: they are not smooth. We do not apply a post-processing stage as boundaries are not clearly defined on an unconstrained mesh sequence (see next section for a discussion on boundaries).

Contrary to previous methods, we handle stretch deformations. We show some results of such clustering on Fig. 7. Some parts of the object follow a rigid transformation while others are stretched.

Our algorithm is able to segment unconstrained mesh sequences as shown in Fig. 8. Each frame of the horse sequence is randomly decimated, and we segment this sequence. The number of vertices varies from 2624 to 4696. Segmentation is similar to the dynamic one.

Discussion

Our whole process deals with two frames at a time, meaning:

• mesh sequences with a high number of frames and/or vertices can be processed.

• the apparition and the decomposition of each cluster is controlled. Boundaries There are two closely related issues on cluster boundaries: they are not smooth and boundaries of clusters on articulation are not necessarily on the middle of the articulation as with other methods. They can be around, a little bit after or before (see Fig. 9 for illustration). Clusters are merged while the transformation (see section 4.4) found can be applied, this transformation becomes invalid after/before the boundaries. As we deal with meshes with varying connectivity, boundaries move from one frame to another. As we want to work on these original sequences (i.e with no modification), this is acceptable. Otherwise, a postprocessing step can correct this problem by inserting points on boundaries in all frames.

Noise and outliers The presence of some outliers or badly matched points is similar to noise. Usage of aver-age error merge them with other vertices. The remaining outliers are on their own cluster, and these clusters are smalls. This means that they are handled by the forced merge of small clusters. However, in presence of many grouped outliers, our algorithm produces incorrect results, as they are clustered together (but the segmentation is coherent with the matching information). It also produces incorrect results when many badly matched points are present: it forces user to select large threshold value. This means that it can produce only a coarse segmentation. In this case the segmentation is correct on the first frame, but it is incorrectly remapped on following frames.

Errors coming from matching and outliers which cause a cluster subdivision at F i are passed on all following frames. This is due to the nature of our algorithm. Matching Methods We have chosen to use projected points to obtained the displacement vectors. The consequence is that we have "real" displacement vectors, but with an expensive computation cost. Using an algorithm as in [MHK + 08], which does not provide projected points, we have to use the matched point to compute the displacement vectors. This implies an error which is more important than with our method. On a dense mesh, this is not be important, as matched point are close to the projected one. However, on sparse meshes, the error can be big enough to either:

• give incorrect result.

• force user to use large T trans f (and obtained a coarse segmentation).

Implementation The prototype for the segmentation part is written in C++ using CGAL, while the matching part is written in Matlab.

Future Work The proposed method can be improved in several ways:

• we did not test our method with objects facing global topological changes. We do not see any trouble in handling them: for each pair of successive frames, detect topological changes between them and split clusters concerned by the topological change of the object;

• The algorithm currently works using two successive frames, which means that we can miss slow motions: if the deformation between two frames is too small, the checkout on the refinement process will always be true and the algorithm will not refine the cluster. The threshold T trans f limits this problem but working with a small time window (as it can easily fit in memory) can improve this. We have some preliminary results, but the main difficulty consists in automatically detecting the size of this time window. Time window may help to correct invalid cluster subdivision by inspecting following frames.

• Detect new motion type such as twist.

The main objective of our next work is to define a validation framework, using user validation and defining error criteria to validate mesh sequence segmentation [START_REF] Benhabiles | A framework for the objective evaluation of segmentation algorithms using a ground-truth of human segmented 3D-models[END_REF][START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF].

CONCLUSION

We have presented a complete framework to segment mesh sequences with varying number of vertices in rigid and stretch components. Our segmentation method works on the fly and allows us to track deformation all along the sequence. Extension to handle objects facing global topological changes, time window to segment slow motion and temporal matching to take advantage of temporal coherency are planned for the near future. This method can be integrated in an automatic production chain, however the threshold needs to be determined manually before. There is no limit to the number of vertices or frames that can be treated by our method, but since errors are passed from frame to frame, long sequence should be splitted into shorter ones.

MeshFigure 1 :

 1 Figure 1: Overall Pipeline of the segmentation.

Figure 3 :

 3 Figure 3: Refinement example: (a) Segmentation at time F. (b) Segmentation at time F + 1. Cluster B is refined into sub-cluster B and C because of the rotation.

  Comparison of error type on segmentation result. (a) Average Error, (b) Difference Error and (c) Max Error on dynamic mesh. (d) Average Error, (e) Difference Error and (f) Max Error on noisy mesh. Horse Segmentation: (a) [LWC06], (b) [dATTS08], (c) with our method. (d,e,f) Frames of the sequence. (g) Coarse, T trans f = 0.0015 and (h) refined, T trans f = 0.0007 result, to compare with (c), T trans f = 0.0009.

Figure 9 :

 9 Figure 9: Boundaries on articulation.

  built. Contrary to initial segmentation, the rigid clustering is not applied on F s , but on F

s ∩ C c , to make sure that the transformation applies on C c . These clusters are added to the set of rigid clusters (See Figure

3

).

This work is partially supported by the ANR (Agence Nationale de la Recherche) through MADRAS project (ANR-07-MDCO-015). A static mesh and mesh sequence repository can be found at http://www-rech.telecom-lille1.eu/madras/


Ioan Alexandru Ivan

Micky Rakotondrabe

Philippe Lutz

Nicolas Chaillet

Current integration force and displacement self-sensing method for cantilevered piezoelectric actuators

This paper presents a new method of self-sensing both of the displacement and the external applied force at the tip of piezoelectric cantilevers. Integrated electric current across piezoelectric actuators is compensated against material nonlinearities ͑creep, hysteresis͒ to provide reliable information. We propose to compensate the hysteresis by using the Prandtl-Ishlinskii static approach while an auto regressive and moving average exogenous ͑ARMAX͒ model is used to minimize the creep influence. The quasistatic estimation, electronic circuit, and aspects related to long-term charge preservations are described or referenced. As an experiment, we tested the actuator entering in contact with a fixed force sensor. An input signal of 20 V peak-to-peak ͑10% of maximum range͒ led to force self-sensing errors inferior to Ϯ8%. A final discussion about method accuracy and its limitations is made.

I. INTRODUCTION

Our previous work 1 discussed self-sensing of free cantilever displacement. In this paper, we introduce a new algorithm based on the same electronic schematic for evaluating unknown applied force at the tip of the actuated cantilevers. Related to 1 both the displacement and the applied force at the tip of the cantilevers are now observed, with the cost of a supplementary compensation of hysteresis and creep effects. The proposed approach can be adapted for long-term duration, up to several tens of seconds.

II. DISPLACEMENT AND FORCE DETECTION

We employ a cantilever of length L, width w, and thickness h. The setup is rather similar to the one already detailed in Ref. 1. Reference force was measured with a FT-S270 micromachined capacitive sensor ͑from FEMTO-tools com-pany͒ mounted on a XYZ microtranslation table for closecontact adjustment. Reference displacement was provided by a Keyence LC-2420 optical device. Both sensors were employed as reference in identification and error evaluation tests; their presence is not needed for self-sensing method.

A. Equation of the estimate force

Theoretical charge due to applied voltage V in and external force F ext is linear

Q = ͵ ͵ A dx 1 dx 2 = ͵ 0 L ͵ 0 w ͫ -e 31 h 2 12F ext Ywh 3 ͑L -x 1 ͒ + 4 33 V in h ͬ dx 2 dx 1 = -3e 31 s 11 L 2 h 2 F ext + 4Lw 33 V in h = ␤F ext + C P V in , ͑1͒
where ␤ is the force sensitivity coefficient and C P is the actuator capacitance. C R is an optional reference capacitor. 1 Displacement of the beam submitted to external voltage and force can be derived from

F est = - C ␤ V out + C R -C P ␤ V in - 1 R FP ␤ ͵ V in ͑t͒dt -1 ␤ ͵ i BIAS ͑t͒dt.

͑3͒

The above expression does not take into account nonlinear nature of piezoelectric ceramics that introduce large parts of uncertainty. For instance, measurements on a unimorph beam of 15ϫ 1 ϫ 0.2 mm 3 showed C P = 1.74 nC/ V and ␤ = 1.03 nC/ mN. Blocking force of such a beam was only 0.07 mN/V. This indicates that 1% of error ͑nonlinearity͒ in charge-to-applied voltage characteristic introduces 24% uncertainty in the estimation of force. Given that ferroelectric behavior of the PZT material shows even 15% of nonlinearity, a compensation of these unwanted effects is unavoidable. Hence, we will replace C P from Eq. ͑3͒ with more appropriate estimators. Hence, final expression of the estimate force will include two additional operators for nonlinear effects: F C ͑s͒ for creep and F H ͑s͒ for hysteresis compensation

F est = - C ␤ V out + C R ␤ V in - 1 R FP ␤ ͵ V in ͑t͒dt - 1 ␤ ͵ i BIAS ͑t͒dt -1 ␤ F C ͑s͒V in - 1 ␤ F H ͑s͒V in . ͑4͒

B. Equation of the estimate displacement

Formula for free ͑F ext =0͒ piezoelectric beam displacement is taken from 1

␦ free_est = - C ␣ V out + C R ␣ V in - 1 R FP ␣ ͵ V in ͑t͒dt -1 ␣ ͵ i BIAS ͑t͒dt, ͑5͒
where ␣ is called the displacement coefficient. When submitted to both external voltage and force, theoretical expression ͓Eq. ͑2͔͒ is prone to nonlinearities, it is better to estimate the displacement with the following formula:

␦ est = ␦ free_est -F est /k Z ,

͑6͒

where k Z is transverse mechanical stiffness of the beam.

C. Displacement and force estimator

The Simulink detection model of force and displacement implemented into a dSPACE real time controller sums several terms from Eqs. ͑4͒-͑6͒ and is shown in Fig. 1. As seen, a supplementary third-order low-pass Butterworth filter was introduced to cancel the noise of F est / k Z term from Eq. ͑6͒ which is far superior to ␦ free_est .

III. SELF-SENSING PARAMETER IDENTIFICATION

Identification for only displacement self-sensing method was previously discussed in Ref. 1. These parameters were bias current i BIAS , leaking resistance R FP , and displacement coefficient ␣. For simplicity reasons, we suppressed dielectric absorption compensation ͑Q DA ͒ but it can be reintroduced from Ref. 1 if more accuracy is required. We added a supplementary series of parameters intended for force selfsensing, such as force sensitivity ␤ and transverse stiffness k Z identifiable from an external force step ͑F ext 0, V in =0͒. Also hysteresis operator F H and creep transfer function F C have to be identified. These nonlinearities characterize the piezoelectric actuator behavior between applied voltage V in and free actuator bending ␦.

To compensate the hysteresis, we use the Prandtl-Ishlinskii ͑PI͒ approach because of its accuracy and ease of implementation and computation ͑Ref. 3͒. The compensation is performed by putting in parallel the system and the PI model ͑Fig. 2͒. In the PI model, a hysteresis is based on the play operator, also called backlash operator. A play operator of unity slope is defined by

V out ء ͑t͒ = max͕V in ͑t͒ -r,min͓V in ͑t͒ + r,V out ء ͑t -T͔͖͒, ͑7͒
where V out ء is the output voltage compensated against bias and leaking currents and summing -C R V in / C reference capacitor term. Parameter r is the threshold and T is the sampling period.

A hysteresis can be approximated by the sum of several play operators weighted by the gain ͑slope͒ w i . [START_REF] Krasnosel | Systems with Hysteresis ͑Springer[END_REF] Let n be the number of elements, so we have

V out ء ͑t͒ = F H ͑V in ͒ = ͚ i=1 n w i max͕V in ͑t͒ -r i ,min͓V in ͑t͒ -r i ,V out ء ͑t -T͔͖͒. ͑8͒
We choose n = 15 for precision and convenient complexity of the model, the parameters bw i =2r i and w i have been identified by using the steps presented in Ref. 3. The accuracy of F H ͑V in ͒ hysteresis operator increases with the total number n hyst of play operators-which reasonably equals some dozens. Identification of w i and r i ͑i =1, ... ,n͒ arrays is made with a couple triangular V in signals of fixed slope and different amplitudes. The slope should be low enough to avoid the effect of the dynamic part on the hysteresis shape but sufficiently high to avoid the effect of the creep part. [START_REF] Rakotondrabe | Complete open-loop control of hysteretic, creeped and oscillating piezoelectric cantilevers[END_REF] In our case, the slope was chosen at Ϯ20 V/s. The amplitude used for the identification is chosen to be 30 V peak-to-peak, which corresponds to the range use. Smaller amplitude signals are further used for identified operator error evaluation.

Creep effect is, like hysteresis, related to piezoelectric coefficients nonlinearity. The identification of the creep operator F C ͑V in ͒ is made with a linear time-invariant transfer function [START_REF] Rakotondrabe | Complete open-loop control of hysteretic, creeped and oscillating piezoelectric cantilevers[END_REF] and is performed on a ramped step input V in whose slope value is the same to that employed in hysteresis PI operator identification; V in = -10 V as in Fig. 3͑a͒. The response is observed for a long duration of time ͑Ն200 s if possible͒. The creep part V creep ͑t͒ ͓Fig. 3͑b͔͒ is separated by subtracting the signal with already identified terms ͑leaking, bias, hysteresis͒ and, afterwards, the model F C ͑V in ͒ is identified using the auto regressive and moving average exogenous ͑ARMAX͒ method and Matlab. It seems that from the third order, the error between the identified model and the experimental curve stops decreasing exponentially. We chose a model of fourth order

F C ͑s͒ = V creep ͑s͒ V in ͑s͒ = a 0 s 4 + a 1 s 3 + a 2 s 2 + a 3 s 1 + a 4 s 4 + b 1 s 3 + b 2 s 2 + b 3 s 1 + b 4 , ͑9͒
where a 0 , ... ,a 4 and b 1 , ... ,b 4 are numerator and denominator polynomial coefficients of creep transfer function.

IV. RESULTS AND DISCUSSION

The unimoph PZT on Ni cantilevered actuator ͑15ϫ 1 ϫ 0.28 mm 3 ͒ is brought near the force sensor ͑close to con-tact͒. Then, a series of periodic steps ͓Fig. 4͑a͔͒ ranging from 0 to Ϫ10 or Ϫ20 V is applied, making the actuator entering in contact and pushing the sensor. The recorded output V out is pictured in Fig. 4͑b͒. As described in previous sections, V out and V in will be used to estimate the deflection and the force.

Maximum-recorded force was of 1.15 mN. As seen from Fig. 5, error between estimated and measured force sums 0.16 mN, meaning 14% ͑from +8% to Ϫ6%͒.

There are some limitations in the method. Displacement performances results are, as expected, inferior to those reported in Ref. 1 but, in exchange, supplementary information about force could be provided. Also, as expected, force estimation is slightly less accurate in self-sensing actuator mode than in sensor-only mode ͑cantilever submitted only to external force͒ but the advantage of self-sensing consist in its double role: both actuator and sensing system. For instance, self-sensing method would provide useful displacement and/or force information from the arms of a microgripper.

The displacement range or dynamics of the actuator are not influenced by the self-sensing circuit, but as applied voltage increases, nonlinearities cause relative error to grow significantly, exceeding 50% for Ϯ40 V operation. To overcome that, more complex hysteresis operator compensation should be employed and extra close contact information would also help in ameliorating precision. Indeed, a very accurate hysteresis and creep modeling is required because 1% of error in charge estimation due to applied voltage may cause nearly a 20...30% error in force detection.

FIG. 2 .

 2 FIG. 2. Parallel compensation of nonlinear system.

FIG. 3 .

 3 FIG. 3. ͑Color online͒ ͑a͒ Applied Ϫ10 V signal for creep identification. ͑b͒ Experimental data and identified transfer function.

FIG. 5 .

 5 FIG. 5. ͑Color online͒ ͑a͒ Measured and estimated force. ͑b͒ Absolute error.

ACKNOWLEDGMENTS

This work is supported by the E.U. FP7 SP3-People Program under Grant No. PIEF-GA-2008-219412 ͑New Micro-Robotic Systems featuring Piezoelectric Adaptive MicroStructures for Sensing and Actuating, with Associated Embedded Control͒.


F Chapoton

On the number of points over finite fields on varieties related to cluster algebras

We compute the number of points over finite fields of some algebraic varieties related to cluster algebras of finite type. More precisely, these varieties are the fibers of the projection map from the cluster variety to the affine space of coefficients.

Introduction

Cluster algebras have been introduced by S. Fomin and A. Zelevinsky around 2000 [FZ02, FZ03, BFZ05, FZ07], and have since been a very active subject. Many connections have been found to combinatorics [START_REF] Fomin | Cluster algebras and triangulated surfaces. I. Cluster complexes[END_REF], Poisson geometry [START_REF] Fock | Cluster ensembles, quantization and the dilogarithm[END_REF] and representation theory [BMR + 06]. Cluster algebras are commutative algebras, and can therefore be considered as objects of algebraic geometry. In this article, we consider some algebraic varieties closely related to the spectrum of cluster algebras. As a first step towards computing their cohomology, we count their points over finite fields.

More precisely, we use as a starting point a theorem [BFZ05, Corollary 1.17] which gives a presentation by generators and relation of acyclic cluster algebras. We use this presentation to define, for each tree, a family of algebraic varieties depending on parameters in an affine space.

In the classical cluster algebra setting, this affine space of parameters corresponds to the so-called coefficients variables in cluster algebras. The fiber over a point in our affine space of parameters is a fiber of the map from the spectrum of the cluster algebra to the spectrum of its coefficient ring.

For simplicity, we restrict ourself to simply-laced cluster algebras of finite type, which are indexed by the usual A-D-E list of Dynkin diagrams. We have implicitly chosen to work with the alternating orientation of these Dynkin diagrams, but the results do not depend on the orientation.

We are also able to obtain more precise results in the case of type A. Here, we describe the cohomology with compact support, in the even case.

The interest of the results may be in the very simple shape of the answers in the generic case (formulas (6), (7) in type A and formulas (22), (24) in type D), which are nice polynomials in the cardinal q of the finite field F q . It would be very interesting to see if the cohomology with compact support is as simple as one may expect from these nice polynomials. We prove that this is indeed the case in type A n with n even.

General results

In this section, we introduce general definitions and tools valid for all trees. Later on, we will use these for finite-type simply-laced Dynkin diagrams.

Definition

Let T be a tree, i.e. a finite graph which is connected and simply connected. We will write st to denote that s and t are adjacent vertices of T .

Let α = (α t ) t∈T be a function on the set of vertices of T with values in some field K.

Let us call X T (α) the affine scheme over K defined by

x t x ′ t = 1 + α t s-t x s , (1)
for all vertices t of T . One can also consider this set of equations as defining a family of schemes over the base affine scheme Spec Z[(α t ) t∈T ]. We will study the fibers of this family. From now on, we will assume (unless explicitly stated otherwise) that the α t are invertible. This amounts to restrict the family to Spec Z[(α t , α -1 t ) t∈T ].

Remark 2.1 Instead of a tree T , one can also consider a disjoint union of trees F , in which case the variety X F (α) will be the product of the varieties associated with the connected components of F .

Reduction using domino tiling

Every tree T is a bipartite graph. Let us fix a choice of black and white vertices such that every edge has a white end and a black end.

Lemma 2.2 Let s and t be adjacent vertices. Let β be the function defined by

β s = 1, β u = α u /α s if u = s and u -t, β u = α u else.
Then X T (α) is isomorphic to X T (β).

Proof. One uses the change of variable x t = α s x t and x ′ t = x ′ t /α s .

Note that this operation only changes the values of the function on vertices that have the same color as s. In a pictorial way, the value at vertex s jumps over vertex t and get spread over the other neighbors of t.

A partial domino tiling of T is a subset of the set of edges such that every vertex appears at most once among the ends of the chosen edges. It is called full if every vertex appears exactly once.

Lemma 2.3 Let T be a tree with a full domino tiling. Then T has a white leaf.

Proof. By an easy induction on the number of vertices.

Proposition 2.4 Let T be a tree, endowed with a partial domino tiling. Every X T (α) is isomorphic to some X T (β) where β s = 1 for every vertex s which is covered by a domino.

Proof. The proof uses only Lemma 2.2 to modify the function α. One can therefore treat black and white vertices separately. Let us just prove the statement for white vertices, the case of black vertices being the same with colors exchanged.

Let C be the set of vertices covered by dominoes. The partial domino tiling of T defines for every white vertex s ∈ C a canonical black neighbor B(s).

Let us orient the edges of T from white to black inside the dominoes (from s to B(s)) and from black to white outside the dominoes.

Then the induced subgraph of T on the set C of vertices covered by dominoes is a disjoint union of trees with oriented edges. One has to flip every white vertex s ∈ C over the black vertex B(s) (which means using Lemma 2.2 to replace α by a modified function), in a well-chosen order. This order must be compatible with the partial order given by the orientation of edges : one has to start with white leaves (which exist by Lemma 2.3).

At the end of the process, one obtains a function β such that every white vertex in C has value 1 and such that X T (α) is isomorphic to X T (β).

Remark 2.5 For every tree, one can find a partial domino tiling where the only vertices which are not covered are leaves.

Induction by removal of leaves

Let T be a tree and let f be a leaf of T . Let g be the unique vertex adjacent to f . Let α be a function on T .

Let T ′ be the tree obtained from T by removing f . For every element β in the ground field K, let α ′ (β) be the function on T ′ defined by

α ′ g (β) = α g β, (2)
α ′ s (β) = α s if s = g. (3)
Let T ′′ be the tree or disjoint union of trees obtained from T by removing f and g. Let α ′′ be the function on T ′′ defined by

α ′′ s = -α s /α f if s -g in T, (4) α ′′ s = α s else. ( 5
)
Proposition 2.6 The scheme X T (α) is the disjoint union of the scheme A 1 × X T ′′ (α ′′ ) and of a variety fibered over A 1 \ {0} with fiber X T ′ (α ′ (β)) over β.

Proof. One simply has to separate points according to whether x f = 0 (which gives the first part) or not (which gives the variety fibered over A 1 \ {0}).

If one assumes x f = 0, the equation (1) for vertex f gives the invertible value -1/α f for x g . Then the equation (1) for vertex g gives a value for x ′ g . There remains a free variable x ′ f and the equations for T ′′ with function α ′′ . This corresponds to the product of the affine space A 1 and the variety X T ′′ (α ′′ )

If one now assumes that x f is invertible, then the equation (1) for vertex f gives a value to x ′ f . One can remove this equation; there remains the equations for T ′ with a function depending on the value of x f . If one moreover fixes the value of x f to be an invertible element β of K, then one gets the equations of X T ′ (α ′ (β)).

3 Type A

We will now consider the Dynkin diagrams of type A.

Number of points over finite fields

In type A n , the cluster algebra is generated by n cluster variables x 1 , . . . , x n (which form a cluster), the n adjacent cluster variables x ′ 1 , . . . , x ′ n and n coefficient variables α 1 , . . . , α n with the following relations:

x 1 x ′ 1 = 1 + α 1 x 2 , x 2 x ′ 2 = 1 + α 2 x 1 x 3 , . . . x n-1 x ′ n-1 = 1 + α n-1 x n-2 x n , x n x ′ n = 1 + α n x n-1 .
Let us call X An (α 1 , . . . , α n ) this variety. As before, we assume that the α i are invertible. Proposition 3.1 If n is even, then X An (α 1 , . . . , α n ) ≃ X An (1, 1, . . . , 1).

If n is odd, then X An (α 1 , . . . , α n ) ≃ X An (α, 1, . . . , 1), for some α depending only on the α i with i odd.

Proof. This is obtained by applying Proposition 2.4 to the obvious full domino tiling (even case) or to the partial domino tiling avoiding only the first vertex (odd case).

For short, we will denote X n (α) for X An (α, 1, . . . , 1). For the number of points of these varieties over finite fields, we will use the following notation: N An (α) is the number of points of X n (α). When n is even, we will also use N An for short. Proposition 3.2 If n is even, then

N An = q n+2 -1 q 2 -1 . ( 6
)
If n is odd and α = (-1) (n+1)/2 , then

N An (α) = (q (n+1)/2 -1)(q (n+3)/2 -1) q 2 -1 . ( 7
)
If n is odd, then

N An ((-1) (n+1)/2 ) = (q (n+1)/2 -1)(q (n+3)/2 -1) q 2 -1 + q (n+1)/2 . ( 8
)
Proof. By induction using leaf-removal (Proposition 2.6). The statement is clear if n = 0, in which case the variety X A0 ( ) is just a point. It is also immediate if n = 1. Let us first note that the statement implies (for n even or odd) that

α∈F * q N An (α) = q n+2 + (-1) n+1 q + 1 . ( 9
)
Assume that n is even. Then Proposition 2.6 becomes

N An = qN An-2 + α∈F * q N An-1 (α), (10)
which can be rewritten (using (9)) as

N An = qN An-2 + q n+1 + 1 q + 1 . ( 11
)
This implies the expected formula for N An . Assume that n is odd. Then Proposition 2.6 becomes

N An (α) = qN An-2 (-1/α) + (q -1)N An-1 , (12)
which can be rewritten as

N An (α) = qN An-2 (-1/α) + q n+1 -1 q + 1 . ( 13
)
Note that α = (-1) (n+1)/2 if and only if -1/α = (-1) (n-2+1)/2 . The induction hypothesis then implies the expected formulas for N An (α).

Let Y An be the union of all varieties X n (α) for α invertible. By a natural convention, Y A0 is just A 1 \ {0}. Let us note as a lemma the formula (9) that we have obtained in the proof of Prop. 3.2. Lemma 3.3 For every n ≥ 0, one has

α∈F * q N An (α) = q n+2 + (-1) n+1 q + 1 . ( 14
)
This is the number of points on Y An over the finite field F q .

Let now Z An be the union of all varieties X n (α) for any α (we do not assume here that α is invertible). Proposition 3.4 For every n ≥ 1, the space Z An is the disjoint union of Y An and Y An-1 . The number of points on Z An over the finite field F q is q n+1 . Proof. The proof of this decomposition is obvious: either α = 0 (and one obtains Y An-1 ) or not (in which case one gets Y An ). The counting result follows from Lemma 3.3. This result immediately suggests that Z An may just be an affine space. This is proved in the next section and will allow to compute some cohomology groups.

We will use later the following result.

Lemma 3.5 For every even n ≥ 1, the space Y An is isomorphic to the product of X n (1) with A 1 \ {0}.

Proof. This is a simple consequence of Lemma 2.2. One has clearly a fibration, and this is made trivial by a simple change of variables.

Cohomology with compact supports

Proposition 3.6 For every n ≥ 1, there is a surjective morphism φ from Z An+1 to Z An with fiber A 1 . For every n ≥ 1, there is an isomorphism

Z An ≃ A n+1 .
Proof. The morphism φ from Z An+1 to Z An is defined by forgetting the first equation (1):

x 1 x ′ 1 = 1 + αx 2 . ( 15
)
One simply has to shift down the indices of variables x i and x ′ i for i ≥ 2 and let x 1 play the role of α.

As it is not possible that both x 1 and x 2 vanish (by the second equation (1)), the first equation is the equation of a line in the plane with coordinates x ′ 1 , α. Therefore every fiber of φ is a line. One can easily check that Z A1 ≃ A 2 . Then the expected isomorphism follows by induction.

Corollary 3.7

As an open set of Z An , Y An is smooth.

Recall that the cohomology with compact support of the affine space A n is very simple: the only non-zero group is

H 2n c (A n ) ≃ Q(n)
, where Q(n) is the Tate Hodge structure of weight n. Proposition 3.8 For n ≥ 0, the non-zero cohomology groups with compact support of Y An are

H i+n+1 c (Y An ) ≃ Q(i), (16)
for 0 ≤ i ≤ n + 1.
Proof. The proof is by induction on n. The statement is true if n = 0. One then uses the long exact sequence in cohomology with compact support for the open-closed decomposition Z An = Y An ⊔ Y An-1 (see Prop. 3.4), together with Prop. 3.6.

One can then obtain the cohomology with compact support of X n (1) when n is even. Proposition 3.9 For n ≥ 0 even, the non-zero cohomology groups with compact support of X n (1) are

H i+n c (X n (1)) ≃ Q(i), (17)
for all even i between 0 and n.

Proof. By induction on n. The statement is true for n = 0 with the natural convention that X A0 ( ) is a point.

One uses two ingredients. The first one is the long exact sequence for the open-closed decomposition X n (1) = Y An-1 ⊔ A 1 × X n-2 . The second one is the Künneth isomorphism describing the cohomology of the product Y An ≃ A 1 \ {0} × X n (1) (see Lemma 3.5). We also need the fact that the cohomology with compact support of A 1 \ {0} is Q(0) in degree 1 and Q(1) in degree 2.

From the long exact sequence, one gets exact sequences

0 → Q(i) → H i+n c (X n (1)) → Q(i+1) → Q(i+1) → H i+n+1 c (X n (1)) → 0, ( 18
)
for even i between 0 and n.

One would like to conclude that

H i+n c (X An+2 ) ≃ Q(i) and H i+n+1 c (X An+2 ) ≃ 0.
Assume on the contrary that, for some even i, H i+n+1 c (X An ) ≃ Q(i + 1) and H i+n c (X An ) is an extension of Q(i) by Q(i + 1), hence has dimension 2. Then the Künneth formula would imply that H i+n+1 c (Y An ) has dimension at least 2, which is absurd, as

H i+n+1 c (Y An ) is Q(i) by Prop. 3.8.

Smoothness

Let us prove that the varieties X n (α) are smooth for generic α. Recall that α is assumed to be invertible. Proposition 3.10 For n even, X n (α) is smooth.

For n odd and α = (-1) (n+1)/2 , X n (α) is smooth.

For n odd and α = (-1) (n+1)/2 , X n (α) has a unique singular point: x i = x ′ i = 0 for odd i and x i = x ′ i = -(-1) (n+i)/2 for even i.

Proof. The proof is by induction on n. The statement is clear if n = 0, 1. Assume that there is a singular point on X n+2 (α).

The equations defining a singular point on X n+2 (α) are the n equations of X n+2 (α) together with the vanishing of all minors of rank n of the 2n×n matrix M n+2 (α) of partial derivatives of these n equations with respect to variables x 1 , . . . , x n , x ′ 1 , . . . , x ′ n . This matrix M n+2 (α) looks as follows:

       x ′ 1 -α 0 . . . 0 x 1 0 . . . 0 -x 3 x ′ 2 -x 1 0 0 x 2 0 0 -x 4 x ′ 3 -x 2 0 0 0 x 3 0 . . . . . . . . . . . . . . . . . . 0 . . . 0 -1 x ′ n 0 . . . 0 x n        (19)
Let us distinguish 2 cases and some sub-cases.

First case : x 1 = 0. Using the equations, this hypothesis implies that x 2 = -1/α and x ′ 2 = -α. Assume first that x ′ 1 = 0. Then the vanishing of all minors of the matrix M n+2 (α) reduces to the vanishing of all minors of the matrix M n (-1/α) (with a shift of indices by 2). So the singular point gives, by restriction to coordinates (x i , x ′ i ) i≥3 , a singular point on X n (-1/α). If n + 2 is even or n + 2 is odd and α = (-1) (n+2+1)/2 , this is absurd by induction hypothesis.

Proof. The proof uses leaf-removal (Proposition 2.6) and the knowledge of the numbers in type A.

In the case of E 6 , let us remove the leaf of the shortest branch. One gets, using Lemma 2.2 to compute the second term,

N E6 = qN A2 N A2 + β∈F * q N A5 (β). ( 31
)
One can compute this using Prop. 3.2 and Lemma 3.3.

In the case of E 7 , let us remove the leaf of the shortest branch. One gets

N E7 (α) = qN A2 N A3 (-1/α) + (q -1)N A6 . (32)
Therefore, by Prop. 3.2 applied to A 3 , one has to separate the case α = -1.

One can compute the different results using Prop. 3.2. In the case of E 8 , let us remove the leaf of the shortest branch. One gets (using Lemma 2.2 to compute the second term)

N E8 = qN A2 N A4 + β∈F * q N A7 (β). ( 33
)
One can compute this using Prop. 3.2 and Lemma 3.3.

If n+2 is odd and α = (-1) (n+2+1)/2 , there is only one solution by induction hypothesis: x i = x ′ i = 0 for odd i ≥ 3 and x i = x ′ i = -(-1) (n+i)/2 for even i ≥ 2. It is readily checked that the point (x i , x ′ i ) i≥1 is indeed a singular point on X n+2 (α).

Assume on the contrary that x ′ 1 = 0. Then the vanishing of all minors of the matrix M n+2 (α) reduces to the vanishing of all minors of an extended matrix which is made of M n (-1/α) plus one more column on the left:

In particular, by restriction to coordinates (x i , x ′ i ) i≥3 , we obtain a singular point on X n (-1/α).

If n + 2 is even or n + 2 is odd and α = (-1) (n+2+1)/2 , this is absurd by induction hypothesis.

If n+2 is odd and α = (-1) (n+2+1)/2 , there is only one solution by induction hypothesis:

for even i ≥ 2. One can then check that the extended matrix has a non-vanishing minor at this point, and therefore (x i , x ′ i ) i≥1 is not a singular point on X n+2 (α). This is absurd.

Second case : x 1 = 0. Then the vanishing of all minors of the matrix M n+2 (α) reduces to the vanishing of all minors of an an extended matrix which is made of M n+1 (x 1 ) (with a shift of indices by 1) plus one more column on the left:

In particular, by restriction to coordinates (x i , x ′ i ) i≥2 , we obtain a singular point on X n+1 (x 1 ).

If n + 2 is odd, this is absurd by induction hypothesis.

If n + 2 is even, then there is only one possible solution by induction hypothesis:

for odd i ≥ 3. One can then check that the extended matrix has a non-vanishing minor at this point, which is therefore not a singular point on X n+2 (α).

Type D

We will now consider the Dynkin diagrams of type D.

In type D n , the cluster algebra is generated by n cluster variables x 1 , x 2 , x 3 , . . . , x n (which form a cluster), the n adjacent cluster variables x ′ 1 , x ′ 2 , x ′ 3 , . . . , x ′ n and n coefficient variables α 1 , . . . , α n with the following relations:

Let us call X Dn (α 1 , . . . , α n ) this variety. As before, we assume that the α i are invertible.

Proposition 4.1 If n is even, then X Dn (α 1 , . . . , α n ) ≃ X Dn (α, β, 1, . . . , 1), for some α, β depending on the α i .

If n is odd, then X Dn (α 1 , . . . , α n ) ≃ X Dn (α, 1, . . . , 1), for some α depending on the α i .

Proof. This is obtained by applying Proposition 2.4 to the partial domino tiling avoiding the first two vertices (even case) or to the partial domino tiling avoiding only the first vertex (odd case).

Let us introduce some notation for the number of points of these varieties over finite fields. If n is odd, we will denote N Dn (α) the number of points of X Dn (α, 1, . . . , 1). If n is even, we will denote N Dn (α, β) the number of points of X Dn (α, β, 1, . . . , 1). Proposition 4.2 If n is odd and α = 1, then

If n is odd, then

If n is even, α = β, α = (-1) n/2 and β = (-1) n/2 , then

If n is even, and α = β differs from (-1) n/2 , then

If n is even, and α = β and α = (-1) n/2 , then

If n is even, and α = β = (-1) n/2 , then N Dn ((-1) n/2 , (-1) n/2 ) equals (q n/2 -1) 2 + 2(q -1)q n/2 + q 2 (q (n-2)/2 -1)(q n/2 -1)

Proof. The proof uses leaf-removal (Proposition 2.6) and knowledge of type A.

If n = 3, one has X D3 (α) ≃ X A3 (α) and the statement follows from type A.

If n ≥ 5 is odd, let us remove the leaf with value α. One gets, using Lemma 2.2 to compute the rightmost term,

According to results in type A, one therefore has to distinguish the case α = 1. One then compute using Prop. 3.2.

If n is even, let us remove the leaf with value α. One gets

According to Prop. 3.2, one has to distinguish according to three alternatives: β = α or not, α = (-1) n/2 or not, and β = (-1) n/2 or not. One can also use the symmetry exchanging α and β. In each case, one can compute the result using Prop. 3.2.

Remark 4.3 One may wonder, in type D n with n odd, if the homotopy type of X Dn (α) (for α = 1) is that of a sphere.

5 Type E

We will now consider the Dynkin diagrams of type E.

Using the general definition given for trees, one can introduce varieties X E6 (α), X E7 (α) and X E8 (α) depending on invertible parameters α.

Proposition 5.1 Every variety X E6 (α) is isomorphic to the variety X E6 (1, . . . , 1). Every variety X E7 (α) is isomorphic to the variety X E7 (1, . . . , 1, α), where α is the value on the last vertex on the long branch of E 7 . Every variety X E8 (α) is isomorphic to the variety X E8 (1, . . . , 1).

Proof. This follows from Proposition 2.4, using appropriate domino tilings.

Let us introduce some notation for the number of points of these varieties over finite fields. We will denote N E6 the number of points of X E6 (1, . . . , 1). and N E8 the number of points of X E8 (1, . . . , 1). We will denote N E7 (α) the number of points of X E7 (1, . . . , 1, α) where α is the value on the last vertex on the long branch of E 7 .

Proposition 5.2 The number of points are as follows:

N E6 = q 6 + q 4 + q 3 + q 2 + 1, N E7 (α) = q 7 + q 5q 2 -1 if α = -1, N E7 (-1) = q 7 + 2q 5 + q 3q 2 -1, N E8 = q 8 + q 6 + q 5 + q 4 + q 3 + q 2 + 1.

(30)


Christophe Paoli

Marie-Laure Nivet

Fabrice Bernardi

Laurent Capocchi

Simulation-based validation of VHDL descriptions using constraints logic programming *

This paper presents a simulation based validation approach for test vectors generation. We suggest to borrow techniques used successfully in the software testing and constraints logic programming areas. Our methodology is based on the three following steps: VHDL code modeling and analysis, constraints-based stimuli generation and test sequences generation.

Introduction

The verification that no error was introduced between the algorithmic level and the RTL level remains an important issue which requires an automation. We know this field of study under the name of functional validation or functional verification. IEEE [1][2] defines verification as the means of establishing the correspondence between a product and its specification, and validation as the means of insuring that a product achieves the function for which it was conceived. In the electronic designer and tester community, the term of verification, that is formal verification, refers to the methods consisting in proving that a circuit will behave as it is supposed to, whereas the term of validation, so called simulation based validation, refers to the methods consisting in exciting a description of circuit by a series of stimuli: the set of stimuli and the observed values is called test vectors.

In spite of recent progress, the formal verification which proposes to prove mathematically the correctness of a description is only realizable for small descriptions.

Indeed the automation of the method implies the exhaustive analysis of a very large space of inputs and is thus restricted to reduced parts of a description. So the simulation based validation is still the best method for design verification. The reader can refer to the various articles published in [START_REF]Formal Verification of Commercials ICs[END_REF] which present the last projections in formal verification.

Our interest here is in the approaches of the simulation based validation. The production of the test vectors is one of the principal problems of the simulation based validation. The disadvantages of this approach are that an exhaustive simulation is necessary to guarantee the exactitude of a description, and that the complexity of current descriptions makes this task unfeasible. The random generation of test vectors is relatively easy but does not guarantee the verification of all the functionalities of the description of the circuit. In general, the designers of circuits generate manually the test vectors according to their knowledge of circuit functionalities. The problem of the automatic generation of test vectors thus remains a subject largely studied by the scientific community.

In this paper, we suggest an approach of test vectors generation which borrows techniques used successfully in the software testing area and which uses a simulator developed within our laboratory. We present in the following section a state of art -which is not meant to be exhaustive -of the automatic test vectors generation. In the third section, we present our methodology to generate the test vectors. Results are presented in section 4 and the prospects are given in section 5.

State of art

Our intention is not to describe in details all the existing methods derived from the software testing area, but simply to present the most representative, to show their limits, and give the reasons which led us to develop our methodology.

Software testing is usually done at several levels. They are commonly referred to as unit testing, integration testing, and system testing. Theirs objectives are respectively:

to verify that individual units (the smallest compilable components) function correctly to test the integration of components and the communication between them to find defects that are attributable to the behavior of the system as a whole, rather than the behavior of individual components, and to test the software functions as a complete system. Whatever the level of development, the activity of test generally proceeds in two times:

selection of a set of input data (often called test set or test data) execution of the software with these input data and observation of its behavior. This observation is often carried out by a human being which must pronounce an "oracle" (i.e. it must decide if the results of the execution are correct).

Our study is at the unit level because we consider that a behavioral VHDL program is a module which can form part of a larger program. Concerning oracle, VHDL language [START_REF]VHDL, Language Reference Manual[END_REF] envisages the use of files of simulation, called test-bench, which make it possible to check and announce any error met during simulation.

The quality of the test data can be evaluated using metrics. The software metrics describe the properties of the code of the software. Their objective is to evaluate if the requirements for quality are satisfied during all the phases of the software life cycle. The metrics are measurements which make it possible to evaluate the complexity of a software and thus offering a help for the test.

The use of coverage metric [START_REF] Beizer | Software Testing Techniques[END_REF] constitutes an approach to test vectors generation. In [START_REF] Fallah | Functional vector generation for HDL models using linear programming and 3satisfaiability[END_REF][7], the test vectors generation is based on observability and instructions coverage metric [START_REF] Fallah | OCCOM: Efficient computation of observability-based code coverage metrics for functional verification[END_REF]. Tags are associated to each variable assignment in the RTL level Verilog description and must be propagated, as for the behavioral faults, towards an exit during simulation. The vectors are generated thanks to a hybrid algorithm SAT (problem of satisfaction of Boolean expression).

The method developed by Kapoor and Armstrong [START_REF] Kapoor | An Automatic Test Bench Generation System[END_REF] takes into account VHDL descriptions of RTL level and aims at the detection of design errors. It uses the CDFG (Control and Data Flow Graph) defined in [START_REF] Cho | B-algorithm: A Behavioral Test Generation Algorithm[END_REF] and generates test vectors starting from the instructions coverage criterion. Symbolic values are used to represent the signal values and their transitions. These values are affected by the user to justify the paths through the CDFG which make it possible to respect the instructions coverage criterion. A test-bench is finally generated in order to simulate description.

In [START_REF] Kalyanaraman | Behavioral Test Vector Generation in VHDL/WAVES Environment[END_REF] and [START_REF] Vemuri | Design Verification tests from Behavioral VHDL Programs[END_REF] execution paths for which one wishes to generate test vectors are specified through certain annotations, managed by the user, in VHDL behavioral description. Each annotated path is translated into constraints, a constraints solver is then used to produce the test vectors which allow their execution. The test vectors are finally converted into format WAVES [START_REF]IEEE Standard for waveform and vector exchange (WAVES) VHDL[END_REF] to facilitate the automatic generation of test-bench.

The methods of [START_REF] Shen | Verification of Processor Microarchitectures[END_REF] and [START_REF] Ho | Architecture validation for processors[END_REF] use concepts borrowed to the formal verification to extract from a Verilog description, a Finite State Machine (FSM), from which the test vectors are generated. Whereas the method of [START_REF] Shen | Verification of Processor Microarchitectures[END_REF] is based on the path coverage, the one developed in [START_REF] Ho | Architecture validation for processors[END_REF] is based on the transitions (change of state) coverage.

The approaches of [START_REF] Rudnick | Fast Sequential Circuit Test Generation Using High-Level and Gate-Level Techniques[END_REF] and [START_REF] Corno | Automatic Test Bench Generation for Validation of RT-Level Descriptions: An Industrial Experience[END_REF] take into account VHDL descriptions of RTL level. The first approach combines techniques used in the software testing area: instructions coverage criterion starting from a STG (State Transition Graph); and techniques used at the gate level (RTL synthesis tool). The generated test vectors make it possible to detect faults of low level, whereas the approach developed in [START_REF] Corno | Automatic Test Bench Generation for Validation of RT-Level Descriptions: An Industrial Experience[END_REF] aims at detecting design errors. This approach uses a genetic algorithm, which interacts with a VHDL simulator, and automatically generates test vectors respecting the branch coverage criterion.

The interested reader can refer to the various articles published in [START_REF]Functionnal Verification and Testbench Generation[END_REF] which present the last projections as regards functional verification and generation of testbench. The methods previously described can be the subject of criticisms and the following comments. In [START_REF] Kalyanaraman | Behavioral Test Vector Generation in VHDL/WAVES Environment[END_REF] and [START_REF] Vemuri | Design Verification tests from Behavioral VHDL Programs[END_REF] the designer must annotate the number of times that an instruction of control must be carried out. This implies a knowledge on the functionality of description and can give paths whose execution is impossible. However, an effective model of constraints was defined which makes it possible to model VHDL instructions crossed by a path. We used this model in our approach. The methods of [START_REF] Corno | Automatic Test Bench Generation for Validation of RT-Level Descriptions: An Industrial Experience[END_REF][6][7] [START_REF] Rudnick | Fast Sequential Circuit Test Generation Using High-Level and Gate-Level Techniques[END_REF], take into account HDL descriptions of RTL level which is lower than the algorithmic level. Moreover the approach of [START_REF] Rudnick | Fast Sequential Circuit Test Generation Using High-Level and Gate-Level Techniques[END_REF] is dependent of a synthesis tool. In [START_REF] Ho | Architecture validation for processors[END_REF] and [START_REF] Shen | Verification of Processor Microarchitectures[END_REF], the developed methods are applicable only for relatively small designs because of the state space size of the FSM, in spite of the improvements made in [START_REF] Shen | Verification of Processor Microarchitectures[END_REF].

To conclude this section, we can say that the static analysis of the code is not sufficient. As a matter of fact, in the presence of loops, the number of execution paths are potentially infinite. Furthermore some of them can be unfeasible. We think that a solution is to connect a simulator to the test vectors generator and thus evaluate the quality of the generated test vectors with pertinent metrics.

Our approach

In this section, we present our methodology to generate the test vectors. Our approach is limited to a subset of VHDL defined in [START_REF] Paoli | techniques issues du domaine du test de logiciels[END_REF].

Overview

As the various methods of software testing, the test of white box type seems most suitable for behavioral VHDL descriptions. This testing technique uses the structure of control of the program, i.e. the code, as a basis to develop or evaluate tests. When this strategy is used the program is seen as a white box in opposition to the test of the black box type which does not use any information on the structure of the coded program. By using this strategy, the tester selects the test data by the examination of the logic of the program. This approach is based on a graph of the program called control flow graph. A multitude of criteria of selection defined on this graph were suggested. The principal methods are the coverage of instructions, the coverage of branches and the coverage of paths. The coverage of instructions requires the execution of each instruction in the program at least once during the test. The coverage of branches requires that each branch of the program will be crossed at least once. A branch is a point in the program from which one or more sets of alternatives of program instructions are selected. The coverage of paths is the most rigorous method and most effective and consists in crossing all the paths which respects a certain criterion. These methods can be classified by means of the relation of inclusion: a criterion X is included in the criterion Y if any test set satisfying Y also satisfies X. One obtains that the coverage of instructions is included in the coverage of branches, it even included in the coverage of paths. However, the coverage of 100% of the paths is theoretically impossible to reach. As we said earlier, in the presence of loops, the number of paths of a control flow graph is potentially infinite. For this reason, several other criteria were defined with the aim of filling the gap between the branches coverage and the paths coverage. In this way we suggest to use a powerful test criterion called the structured testing criterion defined by Watson and McCabe [START_REF] Watson | Structured Testing: A testing Methodology using the cyclomatic Complexity Metric[END_REF]. In order to find data to apply to input port (stimuli) of the VHDL description we chose to represent paths, i.e. the crossed VHDL instructions, by systems of constraints.

The basic operations (cf. Figure 1) of our test vector generator approach consist in the three following steps: (i) VHDL code analysis, (ii) constraints-based stimuli generation, (iii) test sequences generation.

Figure 1. Global view of our approach

These steps are detailed in the three following subsections.

VHDL code analysis

The first part of our approach concerns VHDL code analysis. The goal of this step is to generate the graphs needed by the structured testing criterion generate and analyze the produced paths

The structured testing criterion uses the cyclomatic complexity [START_REF] Mccabe | A Complexity Measure[END_REF] as an index of the number of paths to be tested in a software module. This criterion is stronger than other common coverage criteria like statement coverage or branch coverage. The cyclomatic complexity, also called v(G), is a software metric based on the control flow graph (CFG). This complexity represents the number of linearly independent paths (called a "basis set") of the CFG. It is defined for each module by e-n+2, where e and n are respectively the number of edges and nodes in the CFG. These paths can be used to construct any other existing paths. The problem of finding an appropriate set of v(G) paths is solved using a powerful algorithm: the Poole's algorithm [START_REF] Poole | A Method to Determine a Basis Set of Paths to Perform Program Testing[END_REF]. The basis generated with such an algorithm will be referred to as primary basis.

Behavioral VHDL programs contain multiple communicating concurrent processes, delta delay mechanism for signal assignments and the concept of time which are not found in traditional software programming languages. Variables and signals keep their value through time and are not directly controllable as input ports. These VHDL features imply that some paths of the primary basis can not be exercised directly by their corresponding test vectors.

We have classified the paths of the primary basis in three sub-sets:

-The paths that need an event on an internal signal (any change in the current value of a signal). These paths of the basis do not start at the entry of the program. They must be combined with a path of the primary basis which starts at the entry of the program. We define this type of path as path to be modified. -The paths that traverse a decision node that implies a variable or an internal signal assigned in an other path. A decision node models any VHDL control instruction (e.g. an if statement). We define this type of path as path to be scheduled.

We have to construct a sequence of test vectors. This sequence must be executed before the test vector that exercises the path to be scheduled. -The path that can be exercises directly, because they do not contain references to internal signal or variable. They can be considered as the entry of the VHDL program. All sequences have to begin with one of these paths, we called primary paths.

In order to analyze the primary basis and to determine these three sub-sets, we use the Dependence Flow Graph (DFG). This graph is defined on the same nodes as the CFG. The edges of the DFG represent the dependencies between the program's statements. We have developed in [START_REF] Paoli | techniques issues du domaine du test de logiciels[END_REF] algorithms which generate the list of solution paths that allows to change the paths to be modified and the list of solution paths that allows to construct the sequences for the paths to be scheduled. All of them must begin with a primary path. We choose to keep all the solutions in a single list of solution paths. For each path many stimuli are possible and the choice between them is discussed in the section 3.4.

Constraints-based stimuli generation

The second part of our approach concerns the test data generation. We have to find data to apply to input port (stimuli) of the VHDL description. We chose to represent paths as a constraints system.

Vemuri and Kalynaraman [START_REF] Vemuri | Design Verification tests from Behavioral VHDL Programs[END_REF] have defined a method of test vectors generation for VHDL programs using a constraints model which have inspired our work. Their constraints model allows to take into account the VHDL delta delay mechanism for signal assignments and the concept of time which are not found in traditional software programming languages.

More recently, [23][24] have also suggested to solve the problem of the test generation using constraint programming. Let's start with some definitions.

A Constraint Satisfaction Problem (CSP) consists in:

a set of variables X={ x 1 , … , x n } for each variable x i , a finite set D i of possible values (its domain) and a set of constraints C={ C 1 , C 2 , ... , C m } restricting the values that the variables can simultaneously take.

A solution to a CSP is an assignment of a value from its domain to every variable, in such a way that every constraint is satisfied. We may want to find:

just one solution, with no preference as to which one all solutions an optimal, or at least a good solution, with a given objective (e.g., cost) to be maximized or minimized

The constraints can be solved by using a Constraints Logic Programming (CLP) language including a solver of constraints. If all the domains of the variables are finite and can be enumerated, then the constraints solver will find a solution if it exists. In fact, if the solver of constraint uses the concept of backtracking, so all the solutions can be obtained. Let us note that the force of a environment containing constraints is that the problem can be partially specified, leaving the environment computing the value of the variables.

In the context of test vector generation, i.e. the generation of data input from paths, we have two elements to model: the translation of VHDL objects (variable and signals) into constraint variables, and the definition of their domain the translation of VHDL instructions into constraints

We have developed algorithms in [START_REF] Paoli | techniques issues du domaine du test de logiciels[END_REF] which translate paths into a system of constraints composed by: domain constraints which define the domain of the variables and signals, relational constraints due to the statements crossed by a given path.

After the translation into a constraint programming language [START_REF]ILOG Solver 6.0 User's Manual[END_REF], we used the OPL studio solver to obtain all the solutions of the constraint system. We thus obtained a set of stimuli for each v(G) paths.

Test sequences generation

The third part of our approach concerns the test sequences generation. As explained in section 3.2 some paths, the paths to be scheduled, do not only need a stimuli but a sequence of stimuli. They can not be directly exiting, but are dependant of the execution of an other path. In order to find the valid sequence, we need to build a schedule graph. This graph represents the dependencies between the paths including notion of priority in execution.

As a result of the schedule graph analysis, we select a list of linked paths and for each path a specific stimuli. In order to validate the produced sequences, we connect a VHDL simulator developed in our laboratory: the BFS-DEVS behavioral fault simulator [START_REF] Capocchi | A DEVS-based Modeling and Behavioral Fault Simulator for RTLlevel digital circuits[END_REF]. This tool allows to simulate faulty definition but can also be used as a classic VHDL simulator. We use it in order to compare values of non controllable VHDL objects (internal signal and variable): the value obtained from the simulator and the one obtained from the solver. If these values are not equal, we compose another sequence according to the schedule graph until we find a solution. If there is no valid solution in the stimuli set, the path can not be excited.

Results

We have implemented the two first steps of the test vectors generator in Prolog and LISP languages [START_REF] Paoli | techniques issues du domaine du test de logiciels[END_REF][27] [START_REF] Paoli | Use of constraint solving in order to generate test vectors for behavioral validation[END_REF]. The Table 1 shows the first results we obtained on descriptions of ITC benchmarks [START_REF]International Test Conference benchmarks. Benchmarks from Politecnico di Torino[END_REF]. The first column corresponds to the names of the VHDL descriptions. We did not take into account from B16 to B19 and B21 descriptions cause they are structural types. The following four columns are related to programs features: number of lines (#l), number of processes (#p), number of input ports (#i) of output ports (#o). The other columns present the results obtained with our software after the first step that is code analysis: the cyclomatic complexity number (#v(G)) which represents the total number of paths to be exercised respecting the structured testing criterion, the number of primary paths (#pp), the number of paths to be scheduled (#ps) and the number of paths to be modified (#pm).

A quick analysis of these figures gives knowledge about the structure of the VHDL code and the way the processes are connected. For example in the case of the b22, the number #pm equal to zero shows that the processes are no connected as opposite to the b05 description.

In order to illustrate the second and the third step of our approach, we choose to focus on the b02 VHDL description. The results obtained after constraints generation and schedule graph analysis are shown in Table 2. The first column corresponds to the v(G) paths needed to test the b02 description: path 1 to path 13. The second column gives for each path the number of the stimuli couples obtained after the resolution of the constraint system. The last column presents the list of the solution paths that allows to construct the sequences for the paths to be scheduled. For example in the case of the path 12: eight couples of stimuli are possible. But a sequence has to be exercised before. This sequence has to be composed with stimuli couples of the path 13 or with stimuli couples of the path 3. If the primary path 13 is chosen, the number of stimuli couples that are possible is equal to 24.

The implementation of the third step, i.e. test sequences generation, is not finished. We have not made for the moment the link between the stimuli test generator and the VHDL simulator, but the results obtained seem already effective.

Conclusion and futures works

We have presented in this paper the test vectors generation problem in terms of executing a particular set of paths. We have used software testing techniques and constraint logic programming.

We have developed a software prototype we called GENESI for GENErator of StimulI. We must finish its implementation, particularly the test sequences generation step. But it already permit to help designers and testers to find valid test sequences.

In order to validate our approach, we feel the need for benchmarks of algorithmic level VHDL descriptions and the definition of a standard for a subset of VHDL for behavioral specification.

Our future investigations will concern: the study of different metrics for path or stimuli selection and measure the quality of the test sequences the design improvement of high level VHDL descriptions using graphical HDL tools, e.g. visualizing paths coverage on the graph the consequences of the writing quality of VHDL code on synthesized electronic circuit.

Table 1 . Results on ITC benchmarks.

 1

		#l	#p #I #o #v(G) #pp #ps #pm
	B01	111	1	4	2	19	3	16	0
	B02	71	1	2	1	13	3	10	0
	B03	142	1	6	1	19	3	16	0
	B04	103	1	6	1	12	3	9	0
	B05	333	3	3	6	52	3	12	37
	B06	129	1	4	4	17	3	14	0
	B07	93	1	3	1	15	3	12	0
	B08	90	1	4	1	11	3	8	0
	B09	104	1	3	1	11	3	8	0
	B11	119	1	4	1	23	3	20	0
	B13	297	5	5	7	56	14	42	0
	B14	518	1	34 54	164	3	161	0
	B20	1040	3	34 22	329	5	324	0
	B22	1547	4	34 22	492	7	485	0

Table 2 . Focus on b02 VHDL description

 2

	Path name	# stimuli couples	solution paths
	1	16	-
	2	16	-
	3	4	5-8
	4	4	5-8
	5	8	10
	6	8	7-4
	7	8	9
	8	4	11
	9	4	11
	10	4	6-12
	11	4	6-12
	12	8	13-3
	13	24	-

* A part of this research is founded by CTC (Collectivité Territoriale de Corse) under the contract number A-03-0842; Project 15-3740 "Développement d'un outil de test de circuit et amélioration de la testabilité des circuits" (2003-2004).