M Lamberti

Aurélien Maurel-Pantel

K Idrissa

F Lebon

Porosity estimation of a micro-cracked adhesive interface by µCT scanning: comparison between experimentally measured effective stiffnesses and those predicted by an imperfect interface model

Keywords: Adhesive bonding, CT-scans, Damage, Porosity, Kachanov-Sevostianov's material Correlation zone

The presence of defects in adhesive materials influences the mechanical behaviour of bonded composite structures. Indeed, the initial defects in the adhesive joint damage the mechanical properties of the interface and reduce the mechanical strength of the structure.

An in-depth study of the influence of initial porosity in the bonded joints on the mechanical properties of the rigid adhesive material has been experimentally measured. Different joint geometries are investigated by varying the thickness and the bonding area. A modified Arcan device is used to load the bonds in tension (initiation in Mode I). An imperfect interface model capable of considering the presence of initial diffuse cracks according to the Kachanov-Sevostianov material definition is then used to predict the mechanical properties of these adhesive joints. In this model, the presence of defects in the adhesive layer is described by an initial damage parameter: the porosity rate. Prior to testing, the porosity rates of the bonded joints are measured using µCT scans. Finally, the mechanical properties obtained experimentally are compared with those predicted by the imperfect interface model.

Introduction

Over the last decade, the use of adhesives in the mechanical and civil engineering sectors has grown exponentially due to their ability to easily and quickly bond different types of materials such as steel, aluminium, masonry and composites. The use of adhesive bonding in various industrial sectors is increasing significantly due to the increasing demand for the design of lightweight structures such as aircraft and vehicle body frames. Due to this factor, the joining techniques for joining advanced lightweight materials that are dissimilar, coated and difficult to weld have been thoroughly investigated in recent years [START_REF] He | A review of finite element analysis of adhesively bonded joints[END_REF]. Although adhesive bonding has been used as a traditional joining method for many centuries, it is only in the last seventy years that the science and technology of adhesive bonding has really progressed significantly [START_REF] Adams | Structural adhesive joints in engineering[END_REF].

In addition to civil engineering, the bonding technique has been increasingly used in structural strengthening and reinforcement of concrete elements by adding FRP sheet material, both in fully composite structures such as pedestrian bridges and in buildings where pultruded profiles have been joined together to form more complex cross-sections [START_REF] Lamberti | Influence of web/flange reinforcement on the GFRP bonded beams mechanical response: a comparison with experimental results and a numerical prediction[END_REF]. Moreover, the joints of this type are particularly suitable for the realisation of secondary structures such as parapets, stairs, railings in various types of construction; buildings, cooling towers and offshore installations. For these reasons, there has been a great interest in the scientific and industrial communities to have tools capable of describing and simulating the behaviour of adhesive bonds. Several approaches have been proposed in the literature to describe the behaviour of the bonded interface for different types of applications using analytical or finite element models. In these models, the description of damage is increasingly studied in order to simulate the loss of elastic properties of the interface, to simulate the evolution of these properties during the lifetime of the structure and to describe the failure processes of the assemblies. The most important characteristics for bonded joints to predict their mechanical performance are undoubtedly the stiffness and stress at failure of the bonded interface.

In the framework of continuum damage mechanics, internal damage can be assessed indirectly by the variation of material properties such as elastic coefficients [START_REF] Lemaitre | Mechanics of Solid Materials[END_REF][START_REF] Lemaitre | A Course on Damage Mechanics[END_REF]. A recent review of the subject is presented in [START_REF] Park | A review of continuum damage and plasticity in concrete: Part I-Theoretical framework[END_REF], from the initial papers of Kachanov [START_REF] Kachanov | Time of the rupture process under creep conditions[END_REF] and Rabotnov [START_REF] Rabotnov | On the Mechanism of Delayed Fracture[END_REF] to the most recent work, with emphasis on continuum damage of concrete and plasticity modelling. Fundamental aspects of damage mechanics with new derivations and remarks have recently been presented in the review [START_REF] Voyiadjis | Fundamental aspects for characterization in continuum damage mechanics[END_REF]. Numerical aspects of continuum damage mechanics, with special emphasis on mesh sensitivity, are reviewed in [START_REF] Li | A mesh objective continuum damage model for quasi-brittle crack modelling and finite element implementation[END_REF]. A recent continuous damage approach, based on the continuous-time fatigue model of Ottosen et al [START_REF] Ottosen | Continuum approach to high-cycle fatigue modeling[END_REF], is proposed in [START_REF] Lindström | Continuous-time, high-cycle fatigue model: Validity range and computational acceleration for cyclic stress[END_REF], where an analytical solution for the evolution of damage due to cyclic proportional loading is also given. The proposed approach has also been implemented in continuous-time topological optimisation fatigue problems [START_REF] Suresh | Acceleration of continuous-time, highcycle fatigue constrained problems in topology optimization[END_REF]. Damage modelling techniques can be divided into either local or continuum approaches. In the continuum approach, damage is modelled over a finite region, whereas in the local approach, damage is restricted to zero volume lines and surfaces and is often referred to as the cohesive zone approach [14].

Another approach is to use spring type imperfect interface models. These models are derived by introducing a stress-based micromechanical homogenisation [START_REF] Kachanov | Elastic solids with many cracks and related problems[END_REF][START_REF] Tsukrov | Effective moduli of an anisotropic material with elliptical holes of arbi-trary orientational distribution[END_REF][START_REF] Kachanov | On quantitative characterization of microstructures and effective properties[END_REF][START_REF] Sevostianov | Non-interaction Approximation in the Problem of Effective Properties[END_REF][START_REF] Mauge | Effective elastic properties of an anisotropic material with arbitrarily oriented interacting cracks[END_REF] to treat the damaged interphase within the matched asymptotic expansion method. The interface model is formulated assuming a three-dimensional isotropic interphase weakened by penny-shaped microcracks according to the Kachanov-Sevostianov material definition. The Kachanov-Sevostianov (KS) theory [START_REF] Kachanov | Elastic solids with many cracks and related problems[END_REF] consists in considering the presence of initial cracks inside an adhesive material. The main assumptions of the microcracked adhesive are the following: non-interaction between the crack, a constant stress vector along the crack and the effect of the crack edge in the stress field are ignored.

Furthermore, the peculiarity of this model is that it takes into account some of the most important bond variabilities such as thickness variation, porosity and initial damage [START_REF] Tsukrov | Effective moduli of an anisotropic material with elliptical holes of arbi-trary orientational distribution[END_REF][START_REF] Sevostianov | On some controversial issues in effective field approaches to the problem of the overall elastic properties[END_REF]. The KS type model has previously been successfully applied to cracked to foamed aluminium [START_REF] Tsukrov | Effective moduli of an anisotropic material with elliptical holes of arbi-trary orientational distribution[END_REF], composite materials [START_REF] Sevostianov | On some controversial issues in effective field approaches to the problem of the overall elastic properties[END_REF] and masonry structures [START_REF] Fouchal | An interface model including cracks and roughness applied to masonry[END_REF]. The accuracy of this model, which generally depends on the density of the cracks, is satisfactory up to quite small distances between cracks (distances much smaller than the crack width). The KS model includes a global parameter called the crack density, which is defined by the number and length of all cracks.

In this paper the influence of initial porosity in the bonded joint on the mechanical properties of the rigid adhesive material Sikadur-30 [START_REF] Maurel-Pantel | Modelling of a GFRP adhesive connection by an imperfect soft interface model with initial damage[END_REF] is measured experimentally. The initial defects affect the mechanical properties of the interface and thus the mechanical strength of the structure. In a first part, the mechanical properties of the adhesive are determined by tensile tests. In a second part, different joint geometries are investigated by varying the thickness and the bonding area. A modified Arcan device is used to test the bonded specimens in Mode I. Prior to testing, the porosity rates of the bonded joints are measured using µCT scans. In a third section, an imperfect interface model capable of accounting for the presence of initial diffuse cracks according to the Kachanov-Sevostianov material definition is then used to predict the mechanical properties of adhesive joints. In the model, the presence of defects in the adhesive layer is described by an initial damage parameter: the porosity rate. Finally, the mechanical properties obtained experimentally are compared with those predicted by the imperfect interface model.

Experimental characterization of the adhesive

Adhesive

The adhesive used is an epoxy two-component adhesive names Sikadur-30, available on the market and produced by Sika [23]. The two-component thixotropic structural adhesive reaches the strength capacity after the polymerisation process between a mixture of epoxy resin and special fillers, which ends after a curing of 7 days at temperatures ranging from 8° to 35°. The mechanical properties declared by the manufacturer are given in Table 1. Figure 3 shows the stress-strain curves up to failure. As expected, the adhesives exhibit elastic behaviour, slightly non-linear (due to damage evolution), up to brittle fracture. The Young's modulus, ultimate tensile stress and Poisson's ratio of the SikaDur-30 adhesive are measured and reported in Table 2. These results are close to those quoted by the manufacturer (Table 1).

Experimental characterization of bonded specimens

Bonding protocol

The bonded specimens are realised by joining two cylindrical elements in aluminium 2017 using SikaDur-30 adhesive. The mechanical properties of the aluminium material are summarised in Table 3. The bonded specimens were made to keep constant the total height, ttot, equal to 64 mm, given by the sum of the adhesive thickness ta, and the two cylindrical aluminium parts, tal, both variable in the present experimental study (Figure 4). Before bonding, to ensure the bonding effectiveness and to reduce measurement dispersion, the bonding surface quality is controlled by imposing a surface finish as the manufacturing final step.

The specified surface roughness is chosen to be equal to 0.1 µm. The aluminium surfaces are then perfectly cleaned with acetone. In order to achieve co-axiality between the two cylindrical aluminium parts, a mounting system was used as shown in Figure 5 (a) and Figure 5 (b).

The mounting device contains five semi-cylindrical parts, allowing more samples to be made at the same time. Initially, the aluminium parts are placed on the lower base and the adhesive mixture can be applied to the cylindrical surface. The other five aluminium halves are flanged into the fixture to facilitate positioning and promote co-axiality. A guide system allows the upper base to be positioned on the lower base and the thickness between the cylindrical samples to be calibrated. Once the mounting system has been assembled, it is necessary to wait seven days for the adhesive layer to polymerise completely at room temperature before removing the specimens. In order to achieve perfect control of the adhesive joint and better control the defects, an aluminium part, described in Figure 5 (c), was developed to calibrate the cylindricity of the adhesive joint and reduce its porosity.

The part is covered with Teflon tape, and two parts are assembled on either side of the adhesive joint.

Two holes allow the operator to inject the glue and evacuate the surplus. After a few hours of polymerisation, the parts are removed. A total of 60 samples of different adhesive thickness and surface were tested. Three different surfaces were considered, corresponding to diameters of 18, 14 and 10 mm respectively, and four different adhesive thicknesses, corresponding to 1, 2.5, 5 and 10 mm respectively. For each configuration, a minimum of five samples were tested to ensure an acceptable statistic.

Evaluation of adhesive joint porosities with µCT scans

In this section, the initial volumes of porosity in each bonded specimen are measured using µCT scans before to be tested. The bonded joints are scanned integrally using an X-ray source with a voxel size of 11 µm, a voltage of 150 Kev and a current of 200 µA. The imager has a resolution of 1920 x 1536 pixels. The device used is an EasyTom XL Ultra 150/160 (µCT) manufactured by RX Solution.

Figure 6 describes how the sample is placed in the tomograph machine.

At the end of the reconstruction, each slice of the µCt scan obtained has the thickness of a voxel (11 µm). Sikadur-30 is a filled adhesive, on the slice image the binders can be seen in grey, the colloidal fillers in white and the pores with the lower density appear in black, as shown in Figure 7. In these 3D CT scan images, diffuse porosity is observed for each thickness and diameter of the bond. In any case, it is difficult to make a quantitative assessment by looking only at the slices obtained by microtomography. To obtain a more quantitative measurement, the stack of slices is uploaded to an open source analysis software called Imorph [START_REF] Vicente | Characterization (2d-3d) of ceramic microfiltration membrane by synchrotron radiation: new and abraded membranes[END_REF]. This software allows to perform the segmentation between pores and adhesive matrix. The void phase described by the pores spatial distribution can be observed in Figure 8. Then the software allows to construct the boundary surfaces of the two phases and to calculate a porosity rate ρ in the volume of the joint V.

Figure 8 shows the 3D reconstruction of the pores obtained by the software for three different diameters of the adhesive samples. The number of pores appears to be very diffuse and visually quite important. The software is then able to quantify the volume of each phase. The values of the porosity rates calculated for the three thicknesses are given in Table 4. The average value of the porosity rate noted ρ seems to be independent of the bond surface or thickness. The value is constant around 5% and seems to be a specific property of the Sika Dur-30 adhesive and perhaps a consequence of the bonding process.

Experimental set-up

The experimental tensile static tests were carried out using the modified Arcan device with cylindrical specimens [START_REF] Maurel-Pantel | Comparison of three different adhesive joints using static and dynamic impact tests: Development of a new drop weight impact test rig incorporating a modified Arcan fixture[END_REF]. The device is made up of two half disks characterised by several attachment points along the circumference. These attachment points allow the device to be mounted on a standard tensile testing machine. The external flanges are used to position the specimen and are fastened by means of class 12.9 steel screws evenly distributed on the disk. To maintain a good stiffness gap, the vertical half discs are made of 40CMD8 steel and the horizontal flanges are made of 7075 aluminium.

A 3D CAD design of the Arcan unit is shown in Figure 9.

The static tensile tests were performed at the Mechanical and Acoustic Laboratory of the CNRS in Marseille using a universal tensile machine called "MTS 322 test frame" with a load capacity of 100 kN. The tests were carried out under displacement control at a quasi-static rate of 1 mm/min. The Arcan device was connected to the machine by means of a ball-and-socket joint capable of ensuring isostatism and alignment of the applied load (see Figure 10). During the experimental tests, the corresponding displacement and strain measurements of the adhesive thickness are continuously acquired by processing in-situ images taken by a DIC system from one side. A camera monitors the adhesive layer of the specimen during the loading process.

Fig.11. 3D DIC Analysis using Aramis software on cylindrical bonded samples

The strains are measured using an optical extensometer technique. The images are then analysed using the GOM ARAMIS 6.5 Direct Image Correlation (DIC) software, two points on the coupon surface are selected and the differential displacement between them is used to estimate the deformation of the specimen. The Aramis software was used to acquire the speckle pattern images from the camera. The acquisition frame rate was set to 3 frames per second (fps) for the uniaxial tensile test. The speckle pattern images acquired by the camera were then processed using the Aramis software. When processing these images, the subset size was set to 15 x 15 pixels. Global mean strain values (εxx; εyy; εxy) are obtained from the DIC analysis using Aramis software, an example is reported in Figure 11.

Experimental results

The experimental results for each thickness are given in Table 5. The identification label has the generic form ''D-T'', where ''D'' and ''T'' denote the bonded area relative to a diameter of 18 mm (D18), 14 mm (D14) and 10 mm (D10), respectively, and the bond thickness (1, 2.5, 5, 10 mm). Table 5 shows for each specimen its measured values of normal stress at failure, σu and normal stiffness KN, characterised by the specimen stress-strain curve. Figure 17c describes the average normal stress at failure as well as the standard deviation of the bonded joints for the 18 mm diameter surface at varying adhesive thicknesses (1, 2.5, 5, 10 mm). For the D18T1 specimens, the average normal stress is higher with respect to those of the other thicknesses and seems to decrease as a function of the thickness, as expected. For this diameter it was observed a very low dispersion.

Figures 17a and17b describe the average of the normal stress at failure as well as the standard deviation of the bonded joints for the 14 mm and 10 mm diameter surfaces at varying adhesive thickness (1, 2.5, 5, 10 mm). For both surfaces the trend of the normal stress at failure at varying adhesive thickness follows the same behaviour as previously discussed (D18). The decrease in diameter seems to increase the scatter in the experimental results.

Finally, in Figure 17d, the average normal stiffness KN of the interface is calculated with its standard deviation. The results show that the normal stiffness decreases with increasing thickness for each adhesive surface and also decreases with increasing surface area of the interface. For D18 the effect seems to be less important, and the value is almost constant. This leads to the conclusion that the normal stiffness of the interface is influenced by the geometric dimension of the bonded joint.

28]

Imperfect interface model

In the previous sections, several mechanical parameters of the epoxy adhesive and the bonded assembly have been measured and discussed. Two parameters are of great interest: the elastic properties of the adhesive and its porosity. In this section, the authors propose an imperfect interface model able to describe the properties of an adhesive joint with initial damage (initial porosity), in which these two parameters are useful for predicting the stiffness of the bonded assembly.

Initial damage property of Kachanov's material

The main idea is to define the model from a homogenised material containing microcracks. The microcrack density is assimilated to the porosity parameter using µCT scans. Among the different possibilities existing in the literature, we have chosen the Kachanov-Sevostianov (KS) model [START_REF] Kachanov | Elastic solids with many cracks and related problems[END_REF][START_REF] Tsukrov | Effective moduli of an anisotropic material with elliptical holes of arbi-trary orientational distribution[END_REF][START_REF] Sevostianov | On some controversial issues in effective field approaches to the problem of the overall elastic properties[END_REF], which has the advantage of being a simple and efficient model as demonstrated in literature [START_REF] Maurel-Pantel | Modelling of a GFRP adhesive connection by an imperfect soft interface model with initial damage[END_REF]. According to the Kachanov-Sevostianov theory, the description of the material starts from the evaluation of its initial damage. For this material, the effect of a given number of diffuse cracks can be assumed as the effect of a single large crack, which is able to describe the loss of adhesive stiffness as a function of the initial crack rate. In general, the KS model is of the form:

=

Where is the initial parameter (stiffness, viscosity, etc.), the "damaged" parameter, the crack density and a parameter that depends on the material and the on the shape of the crack. Classically,

= 100 × (2)
Where is the representative crack-length and the volume of material. Note that in practice is measured in %. The thickness of the adhesive is usually small (noted as ). Following the asymptotic technique presented in [START_REF] Rekik | Identification of the representative crack length evolution for a multi-level interface model for quasi-brittle masonry[END_REF][START_REF] Rekik | Homogenization methods for interface modeling in damaged masonry[END_REF], the parameter = , where corresponding to the bonding surface) can be eliminated by going to the limit. An imperfect interface model is then obtained (hereafter referred to as the KSi model). The mechanical parameters depend on the crack-length. For example, the normal stiffness is given by:

= ( ! ) (3)
Where # is the Young's modulus and $ the Poisson's ratio of the adhesive. Note that an evolution law of can be added (see [START_REF] Bonetti | A model of imperfect interface with damage[END_REF][START_REF] Lamberti | Cyclic behaviour modelling of GFRP adhesive connections by an imperfect soft interface model with damage evolution[END_REF][START_REF] Lamberti | Experimental characterization and modelling of adhesive bonded joints under static and non-monotonic fracture loading in the mode II regime[END_REF]). Details of the method are given in Appendices 1 and 2.

Prediction with the KSi model versus experimentally measured values

The µCT scans have shown the existence of an initial porosity in the adhesive joint, which can be considered as an initial damage. The KSi model can be used to predict the normal stiffness of the joint, the values are related in Table 6. From the experimental results described in the previous section, The Young's modulus E, the Poisson's ratio ν both are reported in Table 2 and the porosity rate is reported in Table 4. These parameters can be used to evaluate the normal stiffness of the joint. thickness. This appears to be consistent at this level as the model is based on an asymptotic method that considers a very small thickness compared to the size of the bonded structure. The experimental measurements show in Figure 17(d) suggest that the measured stiffness does not seem to be affected by the adhesive thickness beyond a certain surface value.

Figure 19 describes the percentage error between normal interface stiffnesses experimentally measured and those predicted by the KSi model as a function of the aspect ratio of the bonded structure. For the smallest thickness, the model shows a deviation of 15% for the D10 samples and 22% for the D14 samples. As the thickness increases, the difference between the model and the experiment increases until it reaches 80% for the three surfaces and the largest thicknesses. For the D18 samples a deviation of 85% is observed from the smallest thickness. As expected, the model gives reliable results for thin thicknesses, which is consistent with the asymptotic method of the imperfect interface model. This result is not verified for the D18 specimens, although they have an identical porosity rate. A closer view at the pore geometry in the microtomography images shows that the aspect ratio of the pores is different for the D18 samples. In fact, if the aspect ratio %, corresponding to the ratio between the small radius of the ellipsoid and the large radius of the ellipsoid % = & ' , is considered. Differences are observed, by example for samples D10 and D14 a ratio of about 0.9 is measured, whereas for sample D18 a ratio of about 0.65 is measured.

Conclusions

The methodology presented here tests the ability of the imperfect interface model to predict the mechanical properties of the interface of a bonded connection. Several bonded specimens with different geometries were prepared and tested under controlled laboratory conditions. The mechanical properties of the SikaDur-30 adhesive were also measured by tensile tests.

Microtomographic analysis of the adhesive layer porosity in samples showed that the porosity rate was constant for all the geometries considered. It therefore appears that the porosity rate is indeed a characteristic material parameter of the adhesive.

For small thicknesses the imperfect interface model results are in good agreement with the experimental ones as expected. This result was expected. Because the imperfect interface model is based on an asymptotic method which assumes that the adhesive thickness is very small compared to the size of the bonded structure. However, it is observed that for the largest surface area the deviations are very large while the porosity rate is identical. It seems that in this case the topology of pores is measured with a larger aspect ratio, which could explain the deviation from the model. Overall porosity therefore seems to be a necessary but insufficient parameter for describing initial damage.

The effect of pore topology and distribution appears to have an effect on the stiffness of the adhesive joint. In conclusion, for the moment, it seems reasonable to identify the values of these imperfect interface models by inverse identification methods, especially for large structures with complex loading.

To go further, it seems interesting to refine the description of the porosities in these models (number, orientation, topology, etc.). To better understand the variability due to the geometry of the adhesive joints and the method of implementation. Another method could be to introduce controlled defects in our bonded samples to better understand the response of the pore structure of the adhesive joint.

2. 2 Fig. 1 . 2 .

 212 Fig.1. Mould in Teflon used to make the sheets of adhesive material (a) before machining the specimens by water jet machining (b).

Fig. 3 .

 3 Fig.3. Evolution of stresses as a function of strain for specimens of SIKADUR 30 adhesive.

Fig. 4 .Fig. 5 .

 45 Fig.4. Cylindrical samples used for the mechanical tests.

Fig. 6 .Fig. 7 .Fig. 8 .

 678 Fig.6. Bonded specimen placed in the X-ray microtomograph chamber of the EasyTom XL Ultra 150/160 (µCT) manufactured by RX Solution

Fig. 9 .Fig. 10 .

 910 Fig.9. Arcan modified device for the test specimens (3D view)

Figures 12 to 15 Fig. 12 .Fig. 13 .Fig. 14 .Fig. 15 .Fig. 16 .

 151213141516 Figures 12 to 15 show the experimental failure mode (i.e. crack propagation in the adhesive joint)observed using a camera in the correlation zone described in Figure11. As can be seen also in Figure16, the failure mode in all specimens was cohesive, with the fracture propagating within the adhesive layer.

Fig. 17 .

 17 Fig.17. (a), (b) and (c) show the average normal stress at failure and the standard deviation of the bonded joints for a 10 mm, 14 mm and 18 mm diameter area for different adhesive thicknesses (1, 2.5, 5, 10 mm) respectively. (d) give the average normal stiffness KN of the interface for each geometric condition tested.

Fig. 18 .

 18 Fig.18. Normal stiffness evolution of a micro-cracked interface predicted with the KSi model and based on porosity evaluation from µCT scans.

Figure 18 shows

 18 Figure 18 shows the evolution of the normal stiffness of the micro-cracked interface as predicted by the KSi model and based on the porosity evaluation by µCT scans. The stiffnesses calculated by the model appear to be independent of the bond surface, but very strongly dependent on the bond

Fig. 19 .

 19 Fig.19. Percentage error for the three different diameters of bonded specimens between normal stiffnesses experimentally measured and those predicted by the KSi model as a function of the aspect ratio of the bonded structure.

Table 1 . Mechanical properties of the epoxy adhesive (SikaDur-30).

 1

	Value

Table 2 . Mechanical properties of SikaDur-30 adhesive measured experimentally. Young's Modulus ET (MPa) Tensile Strength σN (MPa) Poisson's Ratio ν

 2

	Average value	Standard Deviation	Average value	Standard Deviation	Average value	Standard Deviation
	11086	757.88	38.75	1.27	0.21	0.01

Table 3 . Mechanical Properties of Aluminium 2017.

 3

	Value

Table 4 . Porosity rate of bonded joints measured by µCT scanning (5 samples per condition).

 4

	Diameter (mm)	Thickness (mm)	Volume (mm 3 )	Average value	ρ (%)	Standard deviation
		1	78.54	5.05		0.99
		2.5	196.35	5.53		0.27
	10
		5	392.7	5.31		0.43
		10	785.4	5.48		0.91
		1	153.94	5.33		1.07
		2.5	384.85	5.00		0.26
	14
		5	769.69	5.26		0.71
		10	1539.38	5.51		0.23
		1	254.47	5.35		0.5
		2.5	636.17	5.1		0.96
	18
		5	1272.35	5.95		1.35
		10	2544.69	5.09		0.55

Table 5 -Experimental results: stiffness KN and normal stress at failure of bonded specimens

 5

	Test ID	KN (N/mm 3 )	σu (MPa)
		Average value	Standard deviation	Average value	Standard deviation
	D10T1	510	29.7	30.1	3.9
	D10T2.5	464.6	32.3	18.5	4.1
	D10T5	390	10.5	17.7	3.4
	D10T10	202.3	56.5	13	2.9
	D14T1	334.1	32.6	36	13
	D14T2.5	307.7	25.2	25.4	0.9
	D14T5	309.0	39.6	17.7	1.9
	D14T10	288	12.7	21.3	4.1
	D18T1	219.3	17.5	30.1	1.5
	D18T2.5	204.1	17.1	22.1	0.1
	D18T5	199.1	22.1	19.7	2.0
	D18T10	184	20.0	16.2	0.4

Table 6 Stiffness KN of adhesively bonded specimens predicted with KSi model

 6

	Test ID	KN (N/mm 3 )
	D10T1	430.3
	D10T2.5	157.3
	D10T5	81.9
	D10T10	39.6
	D14T1	407.8
	D14T2.5	174.0
	D14T5	82.7
	D14T10	39.4
	D18T1	406.1
	D18T2.5	170.7
	D18T5	73.1
	D18T10	42.7

Acknowledgement

This project has received funding from the European Union Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 843218-ASSO (Adhesive Connection for Secondary Structures in Offshore wind installations).

The authors thank Messrs Luca Giuliani and Mohamed Amine Ouelhazi, master's students at the Department of Mechanical Engineering at the University of Ferrara, for their assistance during the preparation and testing of the specimens. The authors would also thank the industry BW Ideol for its financial support.

Appendix 1: Homogenization of micro-cracked materials

The imperfect interface model presented in this paper is derived starting from a heterogeneous interphase, comprising an elastic material in which a microstructure is embedded. This appendix focuses on this kind of interphase materials. In our technique, the homogenization of this heterogeneous material follows a micromechanical approach. Usually, the homogenization techniques for microcracked media have been derived from more general formulations for dry pores, voids, cracks, etc. of various shapes, e. g. spherical, ellipsoidal, cylindrical, etc. The non-interaction approximation (NIA) to the problem of effective properties of a heterogeneous material considers that interactions between inhomogeneities are neglected. In the NIA micromechanical approach, a microstructural parameter is introduced, which gives a measure of the microcracks density (e.g. volume fractions). In order to determine the effective elastic properties of the heterogeneous material with voids (pores, cracks) and under the assumptions of linear elasticity and small perturbation, it is considered that on a Representative Elementary Volume (REV) of the material, the local second-order strain tensor (() is given by [START_REF] Hill | Elastic Properties of Reinforced Solids -Some Theoretical Principles[END_REF]:

where is the fourth-order compliance tensor of the matrix (without voids), * the macroscopic applied second-order stress tensor and ∆ the additional strain due to the presence of voids. The material is assumed to be linear elastic, thus the additional strain due to the voids is a linear function of the applied stress:

where H is a fourth-order compliance contribution tensor of the inhomogeneity. Generally speaking, the H tensor depends on the material, the void density and the shape of the voids. This kind of approach is also called stress-based approach. It can be proved for a simple crack . that:

where, V is the REV volume, n is the normal unit vector of the crack surface, ⨂ 4 is the symmetric tensorial product, and [υ] is the displacement discontinuity vector along .. Note that for a planar crack, the additional strain becomes:

where <> is the average along .. For a uniform macroscopic stress, the additional term can be written as:

where B is a second-order tensor which links < 012 > to the macroscopic stress. As H, the tensor B depends on the material, the void density and the shape of the voids.

As an example, in the three-dimensional case of an isotropic material weakened by a penny-shaped void of radius > (see Figure 20), the last equation reads [START_REF] Kachanov | Elastic solids with many cracks and related problems[END_REF]: where the coefficients GH depends on the material and the shape of the voids.

Appendix 2: Derivation of interface laws by asymptotic expansions for soft materials

A thin layer with cross-section S and uniform small thickness ≪ 1 is considered. The thin layer (interphase) is embedded between two bodies, named as adherents. The thin layer is supposed to be perfectly bonded to the adherents. The material in the thin layer is a microcracked material as defined in appendix 1. Classically, the layer being thin, it is natural to study the problem where the small thickness tends to zero and to replace the thin interphase by a surface (interface) whose is the interphase geometrical limit.

Figure 21: Asymptotic procedure (from [START_REF] Raffa | Micromechanical modeling of imperfect interfaces and applications[END_REF]), from interphase to interface

The study is done in five steps [START_REF] Lebon | Asymptotic analysis of some non-linear soft thin layers[END_REF][START_REF] Raffa | Derivation of a model of imperfect interface with finite strains and damage by asymptotic techniques: an application to masonry structures[END_REF]:

1. Asymptotic expansions of the mechanical fields (displacements, stress tensor, strain, tensor, etc.) with respect to the thickness.

2. Rescaling (from (a) to (b) in Figure 21). A blow up of the thin layer is done in the direction normal to the thickness surface.

3. Analysis of the equilibrium equations in the adherents and in the adhesive using expansions. The terms of each order of expansion are identified.

4. Matching linking initial and rescaled configurations.

5. Obtention of a model of interface on the final configuration (c in figure 21).

In this work, a homogenized microcracked material is considered (Figure 22). The volume of the REV is given by V = S. Note that, in appendix 1, Figure 20, S=L 2 ). In this case, the asymptotic expansion of tensor C has been found resulting in a soft material:


Adrien Pommellet
email: adrien@lrde.epita.fr

Daniel Stan
email: daniel.stan@epita.fr

Simon Scatton
email: simon.scatton@lrde.epita.fr

SAT-based Learning of Computation Tree Logic

Keywords: Computation Tree Logic, Passive learning, SAT solving

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Passive learning is the act of computing a theoretical model of a system from a given set of data, without being able to acquire further information by actively querying said system. The input data may have been gathered through monitoring, collecting executions and outputs of systems. Automata and logic formulas tend to be the most common models, as they allow one to better explain systems of complex or even entirely opaque design.

Linear-time Temporal Logic LTL [START_REF] Pnueli | The temporal logic of programs[END_REF] remains one of the most widely used formalisms for specifying temporal properties of reactive systems. It applies to finite or infinite execution traces, and for that reason fits the passive learning framework very well: a LTL formula is a concise way to distinguish between correct and incorrect executions. The LTL learning problem, however, is anything but trivial: even simple fragments on finite traces are NP-complete [START_REF] Fijalkow | The complexity of learning linear temporal formulas from examples[END_REF], and consequently recent algorithms tend to leverage SAT solvers [START_REF] Neider | Learning linear temporal properties[END_REF].

Computation Tree Logic CTL [START_REF] Clarke | Design and synthesis of synchronization skeletons using branching time temporal logic[END_REF] is another relevant formalism that applies to execution trees instead of isolated linear traces. It is well-known [START_REF] Baier | Principles of model checking[END_REF]Thm. 6.21] that LTL and CTL are incomparable: the former is solely defined on the resulting runs of a system, whereas the latter depends on its branching structure.

However, the CTL passive learning problem has seldom been studied in as much detail as LTL. In this article, we formalize it on Kripke structures (KSs): finite graph-like representations of programs. Our goal is to find a CTL formula (said to be separating) that is verified by every state in a positive set S + yet rejected by every state in a negative set S -.

We first prove that an explicit formula can always be computed and we bound its size, assuming the sample is devoid of contradictions. However, said formula may not be minimal. The next step is therefore to solve the bounded learning problem: finding a separating CTL formula of size smaller than a given bound n. We reduce it to an instance Φ n of the Boolean satisfiability problem whose answer can be computed by a SAT solver; to do so, we encode CTL's bounded semantics, as the usual semantics on infinite executions trees can lead to spurious results. Finally, we use a bottom-up approach to pinpoint the minimal answer by solving a series of satisfiability problems. We show that a variety of optimizations can be applied to this iterative algorithm. These various approaches have been implemented in a C++ tool and benchmarked on a test sample.

Related work. Bounded model checking harnesses the efficiency of modern SAT solvers to iteratively look for a witness of bounded size that would contradict a given logic formula, knowing that there exists a completeness threshold after which we can guarantee no counter-example exists. First introduced by Biere et al. [START_REF] Biere | Symbolic model checking without bdds[END_REF] for LTL formulas, it was later applied to CTL formulas [START_REF] Penczek | Bounded model checking for the universal fragment of ctl[END_REF][START_REF] Xu | Improved bounded model checking for the universal fragment of ctl[END_REF][START_REF] Zhang | Bounded semantics of ctl and sat-based verification[END_REF].

This approach inspired Neider et al. [START_REF] Neider | Learning linear temporal properties[END_REF], who designed a SAT-based algorithm that can learn a LTL formula consistent with a sample of ultimately periodic words by computing propositional Boolean formulas that encode both the semantics of LTL on the input sample and the syntax of its Directed Acyclic Graph (DAG) representation. This work spurred further SAT-based developments such as learning formulas in the property specification language PSL [START_REF] Roy | Learning interpretable models in the property specification language[END_REF] or LTL f [START_REF] Camacho | Learning interpretable models expressed in linear temporal logic[END_REF], applying MaxSAT solving to noisy datasets [START_REF] Gaglione | Learning linear temporal properties from noisy data: A maxsat-based approach[END_REF], or constraining the shape of the formula to be learnt [START_REF] Lutz | Specification sketching for linear temporal logic[END_REF]. Our article extends this method to CTL formulas and Kripke structures. It subsumes the original LTL learning problem: one can trivially prove that it is equivalent to learning CTL formulas consistent with a sample of lasso-shaped KSs.

Fijalkow et al. [START_REF] Fijalkow | The complexity of learning linear temporal formulas from examples[END_REF] have studied the complexity of learning LTL f formulas of size smaller than a given bound and consistent with a sample of finite words: it is already NP-complete for fragments as simple as LTL f (∧, X), LTL f (∧, F), or LTL f (F, X, ∧, ∨). However, their proofs cannot be directly extended to samples of infinite but ultimately periodic words.

Browne et al. [START_REF] Browne | Characterizing finite kripke structures in propositional temporal logic[END_REF] proved that KSs could be characterized by CTL formulas and that conversely bisimilar KSs verified the same set of CTL formulas. As we will show in Section 3, this result guarantees that a solution to the CTL learning problem actually exists if the input sample is consistent. Wasylkowski et al. [22] mined CTL specifications in order to explain preconditions of Java functions beyond pure state reachability. However, their learning algorithm consists in enumerating CTL templates of the form ∀F a, ∃F a, ∀G(a =⇒ ∀X ∀F b) and ∀G(a =⇒ ∃X ∃F b) where a, b ∈ AP for each function, using model checking to select one that is verified by the Kripke structure representing the aforementioned function.

Two very recent articles, yet to be published, have addressed the CTL learning problem as well. Bordais et al. [START_REF] Bordais | Learning temporal properties is np-hard[END_REF] proved that the passive learning problem for LTL formulas on ultimately periodic words is NP-hard, assuming the size of the alphabet is given as an input; they then extend this result to CTL passive learning, using a straightforward reduction of ultimately periodic words to lassoshaped Kripke structures. Roy et al. [START_REF] Roy | Inferring properties in computation tree logic[END_REF] used a SAT-based algorithm, resulting independently to our own research in an encoding similar to the one outlined in Section 4. However, our explicit solution to the learning problem, the embedding of the negations in the syntactic DAG, the approximation of the recurrence diameter as a semantic bound, our implementation of this algorithm, our test suite, and our experimental results are entirely novel contributions.

Preliminary Definitions

Kripke structures

Let AP be a finite set of atomic propositions. A Kripke structure is a finite directed graph whose vertices (called states) are labelled by subsets of AP.

Definition 1 (Kripke Structure

). A Kripke structure (KS) K on AP is a tuple K = (Q, δ, λ) such that:
-Q is a finite set of states; the integer |Q| is known as the size of K;

-δ : Q → (2 Q \ {∅}) is a transition function; the integer max q∈Q |δ(q)| is known as the degree of K; -λ : Q → 2 AP is a labelling function. An infinite run r of K starting from a state q ∈ Q is an infinite sequence r = (s i ) ∈ Q ω of consecutive states such that s 0 = q and ∀ i ≥ 0, s i+1 ∈ δ(s i ). R K (q)
is the set of all infinite runs of K starting from q.

The recurrence diameter α K (q) of state q in K is the length of the longest finite run (s i ) i=0,...,α K (q) starting from q such that ∀ i, j ∈ [0 . . α K (q)], if i ̸ = j then s i ̸ = s j (i.e. the longest simple path in the underlying graph structure). We may omit the index K whenever contextually obvious.

Note that two states may generate the same runs despite their computation trees not corresponding. It is therefore necessary to define an equivalence relation on states of KSs that goes further than mere run equality.

Definition 2 (Bisimulation relation). Let K = (Q, δ, λ) be a KS on AP. The canonical bisimulation relation ∼ ⊆ Q × Q is the coarsest (i.e. the most general) equivalence relation such that for any q 1 ∼ q 2 , λ(q 1 ) = λ(q 2 ) and ∀ q ′ 1 ∈ δ(q 1 ), ∃ q ′ 2 ∈ δ(q 2 ) such that q ′ 1 ∼ q ′ 2 .

Bisimilarity does not only entails equality of runs, but also similarity of shape: two bisimilar states have corresponding computation trees at any depth. A partition refinement algorithm allows one to compute ∼ by refining a sequence of equivalence relations (∼ i ) i≥0 on Q × Q inductively, where for every q 1 , q 2 ∈ Q:

q 1 ∼ 0 q 2 ⇐⇒ λ(q 1 ) = λ(q 2 ) q 1 ∼ i+1 q 2 ⇐⇒ (q 1 ∼ i q 2 ) ∧ ({[q ′ 1 ] ∼i | q ′ 1 ∈ δ(q 1 )} = {[q ′ 2 ] ∼i | q ′ 2 ∈ δ(q 2 )})
Where [q] ∼i stands for the equivalence class of q ∈ Q according to the equivalence relation ∼ i . Intuitively, q 1 ∼ i q 2 if their computation trees are corresponding up to depth i. The next theorem is a well-known result [1, Alg. 31]:

Theorem 1 (Characteristic number). Given a KS K, there exists i 0 ∈ N such that ∀ i ≥ i 0 , ∼ = ∼ i . The smallest integer i 0 verifying that property is known as the characteristic number C K of K.

Browne et al. [START_REF] Browne | Characterizing finite kripke structures in propositional temporal logic[END_REF] defined the characteristic number of a KS as the smallest integer C K ∈ N such that two states are not bisimilar if and only if their computation trees of depth C K are not corresponding. It is trivial to prove that the two definitions are equivalent.

Computation Tree Logic

Definition 3 (Computation Tree Logic). Computation Tree Logic (CTL) is the set of formulas defined by the following grammar, where a ∈ AP is any atomic proposition and † ∈ {∀ , ∃ } a quantifier:

φ ::= a | ⊤ | ¬φ | φ ∧ φ | φ ∨ φ | † X φ | † F φ | † G φ | † φ U φ
Given E ⊆ {¬, ∧, ∨, ∀X, ∃X, ∀F, ∃F, ∀G, ∃G, ∀U, ∃U}, CTL(E) is defined as the set of CTL formulas that only feature operators in E.

CTL formulas are verified against states of KSs (a process known as model checking). Intuitively, ∀ (all ) means that all runs starting from state q must verify the property that follows, ∃ (exists), that at least one run starting from q must verify the property that follows, X φ (next), that the next state of the run must verify φ, F φ (finally), that there exists a state of run verifying φ, G φ (globally), that each state of the run must verify φ, and φ U ψ (until ), that the run must keep verifying φ at least until ψ is eventually verified.

More formally, for a state q ∈ Q of a KS K = (Q, δ, λ) and a CTL formula φ, we write (q |= K φ) when K satisfies φ. CTL's semantics are defined inductively on φ (see [START_REF] Baier | Principles of model checking[END_REF]Def. 6.4] for a complete definition); we recall below the until case: Definition 4 (Semantics of ∀U, ∃U). Let K = (Q, δ, λ) be a KS, φ and ψ two CTL formulas, q ∈ Q, and † ∈ {∀ , ∃ }. Then:

q |= K † φ U ψ ⇐⇒ †(s i ) ∈ R K (q), ∃ i ≥ 0, (s i |= K ψ) ∧ (∀ j < i, s j |= K φ)
Bisimilarity and CTL equivalence coincide [START_REF] Baier | Principles of model checking[END_REF]Thm. 7.20] on finite KSs. The proof relies on the following concept:

Theorem 2 (Browne et al. [START_REF] Browne | Characterizing finite kripke structures in propositional temporal logic[END_REF]). Given a KS K = (Q, δ, λ) and a state q ∈ Q, there exists a CTL formula φ q ∈ CTL({¬, ∧, ∨, ∀X, ∃X}) known as the master formula of state q such that, for any q ′ ∈ Q, q ′ |= K φ q if and only if q ∼ q ′ .

To each CTL formula φ, we associate a syntactic tree T . For brevity's sake, we consider a syntactic directed acyclic graph (DAG) D by coalescing identical subtrees in the original syntactic tree T , as shown in Figure 1. The size |φ| of a CTL formula φ is then defined as the number of nodes of its smallest syntactic DAG. As an example, |¬a ∧ ∀X a| = 4.

∧ ¬ ∀X a a ∧ [4] ¬ [3] ∀X [2] a [1]
Fig. 1. The syntactic tree and indexed DAG of the CTL formula ¬a ∧ ∀X a.

Bounded semantics

We introduce the bounded temporal operators ∀F u , ∃F u , ∀G u , ∃G u , ∀U u , and ∃U u , whose semantics only applies to the first u steps of a run. Formally:

Definition 5 (Bounded semantics of CTL). Let K = (Q, δ, λ) be a KS, φ and ψ two CTL formulas, u ∈ N and q ∈ Q. The bounded semantics of CTL of rank u with regards to K are defined as follows for the quantifier † ∈ {∀ , ∃ }:

q |= K † F u φ ⇐⇒ †(s i ) ∈ R K (q), ∃ i ∈ [0 . . u], s i |= K φ q |= K † G u φ ⇐⇒ †(s i ) ∈ R K (q), ∀ i ∈ [0 . . u], s i |= K φ q |= K † φ U u ψ ⇐⇒ †(s i ) ∈ R K (q), ∃ i ∈ [0 . . u], (s i |= K ψ) ∧ (∀ j < i, s j |= K φ)
Intuitively, the rank u of the bounded semantics acts as a timer: (q |= K ∀G u φ) means that φ must hold for the next u computation steps; (q |= K ∀F u φ), that q must always be able to reach a state verifying φ within u steps; (q |= K ∀ φ U u ψ), that q must always be able to reach a state verifying ψ within u steps, and that φ must hold until it does; etc. This intuition results in the following properties:

Property 1 (Base case). ψ ⇐⇒ (q |= K † F 0 ψ) ⇐⇒ (q |= K † φ U 0 ψ) ⇐⇒ (q |= K † G 0 ψ). Property 2 (Induction). (q |= K † F u+1 φ) ⇐⇒ (q |= K φ) ∨ △ q ′ ∈δ(q) (q ′ |= K † F u φ), (q |= K † φ U u+1 ψ) ⇐⇒ (q |= K ψ) ∨ (q |= K φ) ∧ △ q ′ ∈δ(q) (q ′ |= K † φ U u ψ) , and (q |= K † G u+1 φ) ⇐⇒ (q |= K φ) ∧ △ q ′ ∈δ(q) (q ′ |= K † G u φ), where △ = ∧ if † = ∀ and △ = ∨ if † = ∃. Property 3 (Spread). (q |= K † F u φ) =⇒ (q |= K † F u+1 φ), (q |= K † G u+1 φ) =⇒ (q |= K † G u φ), and (q |= K † φ U u ψ) =⇒ (q |= K † φ U u+1 ψ).
Bounded model checking algorithms [START_REF] Zhang | Bounded semantics of ctl and sat-based verification[END_REF] rely on the following result, as it allows one to bound the study of CTL semantics to finite runs of a known length:

Theorem 3. Given q ∈ Q, for † ∈ {∀ , ∃ } and ▷ ∈ {F, G}, q |= K † ▷ φ (resp. q |= K † φ U ψ) if and only if q |= K † ▷ α(q) φ (resp. q |= K † φ U α(q) ψ).
A full proof of this result is available in Appendix A.

The Learning Problem

We consider the synthesis problem of a distinguishing CTL formula from a sample of positive and negative states of a given KS.

Introducing the problem

The sample must be first and foremost be self-consistent: a state in the positive sample cannot verify a CTL formula while another bisimilar state in the negative sample does not.

Definition 6 (Sample). Given a KS K = (Q, δ, λ), a sample of K is a pair (S + , S -) ∈ 2 Q × 2 Q such that ∀ q + ∈ S + , ∀ q -∈ S -, q + ̸ ∼ q -.
We define the characteristic number C K (S + , S -) of a sample as the smallest integer c ∈ N such that for every q + ∈ S + , q -∈ S -, q + ̸ ∼ c q -. Definition 7 (Consistent formula). A CTL formula φ is said to be consistent with a sample (S + , S -) of K if ∀ q + ∈ S + , q + |= K φ and ∀ q -∈ S -, q -̸ |= K φ.

The rest of our article focuses on the following passive learning problems: Definition 8 (Learning problem). Given a sample (S + , S -) of a KS K and n ∈ N * , we introduce the following instances of the CTL learning problem:

L CTL(E) (K, S + , S -). Is there φ ∈ CTL(E) consistent with (S + , S -)? L ≤n CTL(E) (K, S + , S -). Is there φ ∈ CTL(E), |φ| ≤ n, consistent with (S + , S -)? ML CTL(E) (K, S + , S -). Find the smallest φ ∈ CTL(E) consistent with (S + , S -).
Theorem 4. L CTL (K, S + , S -) and ML CTL (K, S + , S -) always admit a solution.

Proof. Consider ψ = q + ∈S + φ q + . This formula ψ is consistent with (S + , S -) by design. Thus L CTL (K, S + , S -) always admits a solution, and so does the problem ML CTL (K, S + , S -), although ψ is unlikely to be the minimal solution. ⊓ ⊔ Bordais et al. [START_REF] Bordais | Learning temporal properties is np-hard[END_REF] proved that L ≤n CTL (K, S + , S -) is NP-hard, assuming the set of atomic propositions AP is given as an input as well.

An explicit solution

We must find a formula consistent with the sample (S + , S -), an easier problem that Browne et al. [START_REF] Browne | Characterizing finite kripke structures in propositional temporal logic[END_REF]'s answer to Theorem 2. As we know that every state in S - is dissimilar to every state in S + , we will try to encode this fact in CTL form, then use said encoding to design a formula consistent with the sample. Definition 9 (Separating formula). Let (S + , S -) be a sample of a KS K = (Q, δ, λ). Assuming that AP and Q are ordered, and given q 1 , q 2 ∈ Q such that q 1 ̸ ∼ q 2 , formula D q1,q2 is defined inductively w.r.t. c = C K ({q 1 }, {q 2 }) as follows:

-if c = 0 and λ(q 1 ) \ λ(q 2 ) ̸ = ∅ has minimal element a, then D q1,q2 = a; -else if c = 0 and λ(q 2 ) \ λ(q 1 ) ̸ = ∅ has minimal element a, then D q1,q2 = ¬a; -else if c ̸ = 0 and ∃ q ′ 1 ∈ δ(q 1 ), ∀ q ′ 2 ∈ δ(q 2 ), q ′ 1 ̸ ∼ c-1 q ′ 2 , then D q1,q2 = ∃X q ′ 2 ∈δ(q2) D q ′ 1 ,q ′ 2
, picking the smallest q ′ 1 verifying this property;

-else if c ̸ = 0 and ∃ q ′ 2 ∈ δ(q 2 ), ∀ q ′ 1 ∈ δ(q 1 ), q ′ 1 ̸ ∼ c-1 q ′ 2 , then D q1,q2 = ∀X ¬ q ′ 1 ∈δ(q1) D q ′ 2 ,q ′ 1
, picking the smallest q ′ 2 verifying this property.

The formula S K (S + , S -) =

q + ∈S + q -∈S - D q + ,q -∈ CTL({¬, ∧, ∨, ∀X, ∃X}) is then called the separating formula of sample (S + , S -).
Intuitively, the CTL formula D q1,q2 merely expresses that states q 1 and q 2 are dissimilar by negating Definition 2; it is such that q 1 |= K D q1,q2 but q 2 ̸ |= K D q1,q2 . Either q 1 and q 2 have different labels, q 1 admits a successor that is dissimilar to q 2 's successors, or q 2 admits a successor that is dissimilar to q 1 's. The following result is proven in Appendix B: Theorem 5. The separating formula S K (S + , S -) is consistent with (S + , S -).

As proven in Appendix C, we can bound the size of S K (S + , S -): Corollary 1. Assume the KS K has degree k and c = C K (S + , S -), then:

-if k ≥ 2, then |S K (S + , S -)| ≤ (5 • k c + 1) • |S + | • |S -|; -if k = 1, then |S K (S + , S -)| ≤ (2 • c + 3) • |S + | • |S -|.

SAT-based Learning

The universal fragment CTL ∀ = CTL({¬, ∧, ∨, ∀X, ∀F, ∀G, ∀U}) of CTL happens to be as expressive as the full logic [1, Def. 6.13]. For that reason, we will reduce a learning instance of CTL ∀ of rank n to an instance of the SAT problem. A similar reduction has been independently found by Roy et al. [START_REF] Roy | Inferring properties in computation tree logic[END_REF].

Lemma 1. There exists a Boolean propositional formula Φ n such that the instance L ≤n CTL ∀ (K, S + , S -) of the learning problem admits a solution φ if and only if the formula Φ n is satisfiable.

Modelling the formula

Assume that there exists a syntactic DAG D of size smaller than or equal to n representing the desired CTL formula φ. Let us index D's nodes in [1 . . n] in such a fashion that each node has a higher index than its children, as shown in Figure 1. Hence, n always labels a root and 1 always labels a leaf.

Let L = AP ∪ {⊤, ¬, ∧, ∨, ∀X, ∀F, ∀G, ∀U} be the set of labels that decorates the DAG's nodes. For each i ∈ [1 . . n] and o ∈ L, we introduce a Boolean variable τ o i such that τ o i = 1 if and only if the node of index i is labelled by o. For all i ∈ [1 . . n] and j ∈ [0 . . i -1], we also introduce a Boolean variable l i,j (resp. r i,j ) such that l i,j = 1 (resp. r i,j = 1) if and only if j is the left (resp. right) child of i. Having a child of index 0 stands for having no child at all in the actual syntactic DAG D.

Three mutual exclusions clauses xor τ , xor l , and xor r guarantee that each node of the syntactic DAG has exactly one label and at most one left child and one right child. Moreover, three other clauses ar 0 , ar 1 , and ar 2 ensure that a node labelled by an operator of arity x has exactly x actual children (by convention, if x = 1 then its child is to the right). These simple clauses are similar to Neider's encoding [START_REF] Neider | Learning linear temporal properties[END_REF] and for that reason are only detailed in Appendix D.

Applying the formula to the sample

For all i ∈ [1 . ., n] and q ∈ Q, we introduce a Boolean variable φ q i such that φ q i = 1 if and only if state q verifies the sub-formula φ i rooted in node i. The next clauses implement the semantics of the true symbol ⊤, the atomic propositions, and the CTL operator ∀X.

i∈ [1. .n] q∈Q

(τ ⊤ i =⇒ φ q i ) (sem ⊤ ) i∈[1. .n] q∈Q a∈λ(q) (τ a i =⇒ φ q i ) ∧ a̸ ∈λ(q) (τ a i =⇒ ¬φ q i ) (sema) i∈[2. .n] k∈[1. .i-1] (τ ∀X i ∧ r i,k ) =⇒ q∈Q φ q i ⇐⇒ q ′ ∈δ(q) φ q ′ k (sem ∀X )
Semantic clauses are structured as follows: an antecedent stating node i's label and its possible children implies a consequent expressing φ q i 's semantics for each q ∈ Q. Clause sem ⊤ states that q |= ⊤ is always true; clause sem a , that q |= a if and only if q is labelled by a; and clause sem ∀X , that q |= ∀X ψ if and only if all of q's successors verify ψ. Similar clauses sem ¬ , sem ∧ , and sem ∨ encoding the semantics of the Boolean connectors ¬, ∧ and ∨ are only detailed in Appendix D, being straightforward enough.

For reasons detailed in Appendix F, we will encode the bounded semantics of the temporal operators ∀F u , ∀G u and ∀U u . For all i ∈ [1 . . n], q ∈ Q, and u ∈ [0 . . α(q)], we introduce a Boolean variable ρ u i,q such that ρ u i,q = 1 if and only if q verifies the sub-formula rooted in i according to the CTL bounded semantics of rank u (e.g. q |= ∀F u ψ, assuming sub-formula ∀F ψ is rooted in node i).

Thanks to Theorem 3 we can introduce the following equivalence clause:

i∈[2. .n] o∈{∀F,∀G,∀U} τ o i =⇒ q∈Q (φ q i ⇐⇒ ρ α(q) i,q ) (semρ)
Property 3 yields two other clauses whose inclusion is not mandatory (they were left out by Roy et al. [START_REF] Roy | Inferring properties in computation tree logic[END_REF]) that further constrains the bounded semantics:

i∈[2. .n] (τ ∀F i ∨ τ ∀U i ) =⇒ q∈Q u∈[1. .α(q)] (ρ u-1 i,q =⇒ ρ u i,q ) (ascentρ) i∈[2. .n] τ ∀G i =⇒ q∈Q u∈[1. .α(q)] (ρ u i,q =⇒ ρ u-1 i,q ) (descentρ)
The next clause states enables variable ρ u i,q for temporal operators only:

i∈[2. .n] o∈{∀F,∀G,∀U} ¬τ o i =⇒ q∈Q u∈[0. .α(q)] ¬ρ u i,q (noρ)
Properties 1 and 2 yield an inductive definition of bounded semantics. We only explicit the base case base ρ and the semantics sem ∀U of ∀U u , but also implement clauses sem ∀F and sem ∀G detailed in Appendix G.

i∈[2. .n] k∈[1. .i-1] o∈{∀F,∀G,∀U} τ o i ∧ r i,k =⇒ q∈Q (ρ 0 i,q ⇐⇒ φ q k ) (baseρ) i∈[2. .n] j,k∈[1. .i-1] (τ ∀U i ∧ li,j ∧ r i,k ) =⇒ q∈Q u∈[1. .α(q)] ρ u i,q ⇐⇒ φ q k ∨ φ q j ∧ q ′ ∈δ(q) ρ min(α(q ′ ),u-1) i,q ′ (sem ∀U )
Finally, the last clause ensures that the full formula φ (rooted in node n) is verified by the positive sample but not by the negative sample. Proof. Clauses xor τ to ar 2 allow one to infer the DAG of a formula φ ∈ CTL of size smaller than or equal to n from the valuations taken by the variables (τ o i ), (l i,j ), and (r i,j ). Clauses sem a to sem φ guarantee that the sample is consistent with said formula φ, thanks to Theorem 3 and Properties 1, 2, and 3.

q + ∈S + φ q + n ∧ q -∈S - ¬φ q - n (semφ)
⊓ ⊔

Algorithms for the Minimal Learning Problem

We introduce in this section an algorithm to solve the minimum learning problem ML CTL ∀ (K, S + , S -). Remember that it always admits a solution if and only if the state sample is consistent by Theorem 4.

A bottom-up algorithm

By Theorem 4, there exists a rank n 0 such that the problem L ≤n0 CTL ∀ (K, S) admits a solution. Starting from n = 0, we can therefore try to solve L ≤n CTL ∀ (K, S) incrementally until a (minimal) solution is found, in a similar manner to Neider and Gavran [START_REF] Neider | Learning linear temporal properties[END_REF]. Algorithm 1 terminates with an upper bound n 0 on the number of iterations required.

Input: a KS K and a sample S. Output: the smallest CTL ∀ formula φ consistent with S. n ← 0; repeat n ← n + 1; compute Φn; until Φn is satisfiable by some valuation v; from v build and return φ.

Algorithm 1: Solving ML CTL ∀ (K, S).

Embedding negations

The CTL formula ∃F a is equivalent to the CTL ∀ formula ¬ ∀G ¬a, yet the former remains more succinct, being of size 2 instead of 4. While CTL ∀ has been proven to be as expressive as CTL, the sheer amount of negations needed to express an equivalent formula can significantly burden the syntactic DAG. A possible optimization is to no longer consider the negation ¬ as an independent operator but instead embed it in the nodes of the syntactic DAG, as shown in Figure 2.

¬ ∃U ⊤ ¬ ∀X ¬ a ¬ ∃U [1] ⊤ [2]
¬ ∀X [START_REF] Bjørklund | Approximating longest directed paths and cycles[END_REF] ¬a [START_REF] Bordais | Learning temporal properties is np-hard[END_REF] Fig. 2. The syntactic DAG of ¬∃ ⊤ U ¬ ∀X ¬a, before and after embedding negations.

Note that such a definition of the syntactic DAG alters one's interpretation of a CTL formula's size: as a consequence, under this optimization, Algorithm 1 may yield a formula with many negations that is no longer minimal under the original definition of size outlined in Section 2.2.

Formally, for each i ∈ [1 . . n], we introduce a new variable ν i such that ν i = 0 if and only if the node of index i is negated. As an example, in Figure 2, ν 1 = ν 3 = ν 4 = 0, but ν 2 = 1 and the sub-formula rooted in node 3 is ¬ ∀X ¬a.

We then change the SAT encoding of CTL ∀ 's semantics accordingly. We remove the ¬ operator from clauses xor τ , ar 1 , and the set L of labels. We delete clause sem ¬ . Finally, we update the semantic clauses sem ⊤ , sem a , sem ∧ , sem ∨ , sem ∀X , and sem ρ . Indeed, the right side of each equivalence expresses the semantics of the operator rooted in node i before applying the embedded negation; we must therefore change the left side of the semantic equivalence accordingly, replacing the Boolean variable φ q i with the formula φq i = (¬ν i ∧ ¬φ q i ) ∨ (ν i ∧ φ q i ) that is equivalent to φ q i if ν i = 1 and ¬φ q i if ν i = 0. These changes are fully described in Appendix I.

Optimizations and alternatives

Minimizing the input KS. In order to guarantee that an input S is indeed a valid sample, one has to ensure no state in the positive sample is bisimilar to a state in the negative sample. To do so, one has to at least partially compute the bisimilarity relation ∼ on K = (Q, δ, λ). But refining it to completion can be efficiently performed in O(|Q| • |AP| + |δ| • log(|Q|)) operations [1, Thm. 7.41], yielding a bisimilar KS K min of minimal size.

Minimizing the input KS is advantageous as the size of the semantic clauses depends on the size of K, and the SAT solving step is likely to be the computational bottleneck. As a consequence, we always fully compute the bisimulation relation ∼ on K and minimize said KS.

Approximating the recurrence diameter. Computing the recurrence diameter of a state q is unfortunately a NP-hard problem that is known to be hard to approximate [START_REF] Bjørklund | Approximating longest directed paths and cycles[END_REF]. A coarse upper bound is α(q) ≤ |Q| -1: it may however result in a significant number of unnecessary variables and clauses. Fortunately, the decomposition of a KS K into strongly connected components (SCCs) yields a finer over-approximation shown in Figure 3 that relies on the ease of computing α in a DAG. It is also more generic and suitable to CTL than existing approximations dedicated to LTL bounded model checking [START_REF] Kroening | Efficient computation of recurrence diameters[END_REF].

Contracting each SCC to a single vertex yields a DAG known as the condensation of K. We weight each vertex of this DAG G with the number of vertices in the matching SCC. Then, to each state q in the original KS K, we associate the weight β(q) of the longest path in the DAG G starting from q's SCC, minus one (in order not to count q). Intuitively, our approximation assumes that a simple path entering a SCC can always visit every single one of its states once before exiting, a property that obviously does not hold for two of the SCCs shown here.

Encoding the full logic. CTL ∀ is semantically exhaustive but the existential temporal operators commonly appear in the literature; we can therefore consider the learning problem on the full CTL logic by integrating the operators ∃X, ∃F, ∃G, and ∃U, whose Boolean encoding is discussed in Appendix H. We also consider the fragment CTL U = {¬, ∨, ∃X, ∃G, ∃U} used by Roy et al. [START_REF] Roy | Inferring properties in computation tree logic[END_REF].

K q0 q1 q2 q3 q4 q5 q6 G 1 3 2 1 α(q0) = 3 α(q1) = 2 α(q2) = 1 α(q3) = 3 α(q4) = 1 α(q5) = 2 α(q6) = 0 β(q0) = 4 β(q1) = 3 β(q2) = 3 β(q3) = 3 β(q4) = 2 β(q5) = 2 β(q6) = 0
Fig. 3. An approximation β of the recurrence diameter α relying on SCC decomposition that improves upon the coarse upper bound α(q) ≤ |Q| -1 = 6.

Experimental Implementation

We implement our learning algorithm in a C++ prototype tool LearnCTL 4 , relying on Microsoft's Z3 due to its convenient C++ API. It takes as an input a sample of positive and negative KSs with initial states, then coalesced into a single KS and a sample of states compatible with the theoretical framework we described. It finally returns a separating CTL ∀ , CTL, or CTL U formula after a sanity check performed by model-checking the KSs against the learnt formula.

Benchmark Collection

We intend on using our tool to generate formulas that can explain flaws in faulty implementations of known protocols. To do so, we consider structures generated by higher formalisms such as program graphs: a single mutation in the program graph results in several changes in the resulting KS. This process has been achieved manually according to the following criteria:

-The mutations only consist in deleting lines.

-The resulting KS should be small, less than ∼ 1000 states.

-Any mutation should result in a syntactically correct model.

We collected program graphs in a toy specification language for a CTL model checker class implemented in Java. Furthermore, we also considered PROMELA models from the Spin model-checker [START_REF] Holzmann | The SPIN Model Checker -primer and reference manual[END_REF] repository. Translations were then performed through the Python interface of spot/ltsmin [START_REF] Duret-Lutz | From Spot 2.0 to Spot 2.10: What's new?[END_REF][START_REF] Kant | Ltsmin: High-performance language-independent model checking[END_REF].

Example 1. Consider the mutual exclusion protocol proposed by [START_REF] Peterson | Myths about the mutual exclusion problem[END_REF] and specified in PROMELA in Figure 6.1 that generates a KS with 55 states. We generate mutants by deleting one line of code at a time, ignoring variable and process declarations as they are necessary for the model to be compiled and the two assertion lines that are discarded by our KS generator.

Furthermore, removing the instruction ncrit--alone would lead to an infinite state space; thus, its deletion is only considered together with the instruction ncrit++. Finally, we set some atomic propositions of interest: c stands for at least one process being in the critical section (ncrit>0), m for both processes (ncrit>1), and t for process 0's turn. An extra dead atomic proposition is added by Spot/LTSMin to represent deadlocked states.

As summarized on Figure 6.1, every mutated model, once compared with the original KS, lead to distinguishing formulas characterizing Peterson's protocol: mutations m1, m2, and m3 yield a mutual exclusion property, m4 yields a liveness property, m5 yields a fairness property, and m6 yields global liveness formula.

m1 m2 m3 m4 m5 m6 ∀G ¬m ∀F c ∀G(¬ ∀G ∀F t)
∀G ¬dead bool turn , f l a g [START_REF] Biere | Symbolic model checking without bdds[END_REF] ; // t = " t u r n " ; m = " n c r i t >1" ; c = " n c r i t >0" byte n c r i t ; active [START_REF] Biere | Symbolic model checking without bdds[END_REF] proctype u s e r ( )

{ assert ( _pid == 0 | | _pid == 1 ) ; a g a i n : f l a g [ _pid ] = 1 ; t u r n = _pid ; ( f l a g [ 1 -_pid ] == 0 | | t u r n == 1 -_pid ) ;
n c r i t ++; assert ( n c r i t == 1 ) ; / * c r i t i c a l s e c t i o n * / n c r i t --; f l a g [ _pid ] = 0 ; goto a g a i n } Fig. 4. Peterson's mutual exclusion protocol in PROMELA and learnt formulas for each deleted instruction.

Quantitative evaluation

We quantitatively assess the performance of the various optimizations and CTL fragments discussed previously. To do so, we further enrich the benchmark series through the use of random mutations of hard-coded KSs: these mutations may alter some states, re-route some edges, and spawn new states, as detailed in Appendix J. We consider a total of 234 test samples, ranging from size 11 to 698 after minimization. We perform the benchmarks on a GNU/Linux Debian machine (bullseye) with 24 cores (Intel(R) Xeon(R) CPU E5-2620 @ 2.00GHz) and 256Go of RAM, using version 4.8.10 of libz3 and 1.0 of LearnCTL. Table 6.2 displays a summary of these benchmarks: β stands for the refined approximation of the recurrence diameter described in Section 5.3; ¬, for the embedding of negations in the syntactic tree introduced in Section 5.2. The average size of the syntactic DAGs learnt is 4.14.

Option β yields the greatest improvement, being on average at least 6 times faster than the default configuration; option ¬ further divides the average runtime by at least 2. These two optimizations alone speed up the average runtime by a factor of 12 to 20. The CTL fragment used, all other options being equal, does not influence the average runtime as much (less than twofold in the worst case scenario); (CTL U , β, ¬) is the fastest option, closely followed by (CTL ∀ , β, ¬).

Intuitively, approximating the recurrence diameter aggressively cuts down the number of SAT variables needed: assuming that α has upper bound d, we only need n • |Q| • d Boolean variables (ρ u i,q ) instead of n • |Q| 2 . Moreover, embedding negations, despite requiring more complex clauses, results in smaller syntactic DAGs with "free" negations, hence faster computations, keeping in mind that the last SAT instances are the most expensive to solve, being the largest. Unsurprisingly, (CTL ∀ , β, ¬) and (CTL, β, ¬) outperform (CTL U , β, ¬) when a minimal distinguishing formula using the operator ∀U exists: the duality relation between ∀U and ∃U is complex and, unlike the other operators, cannot be handled at no cost by the embedded negation as it depends the operator release.

Conclusion and Further Developments

We explored in this article the CTL learning problem: we first provided an explicit answer before relying on a SAT encoding inspired by bounded model-checking to iteratively find a minimal answer. We also introduced in Section 3 an explicit answer to the learning problem that belongs to the fragment CTL(¬, ∧, ∨, ∀X, ∃X). It remains to be seen if a smaller formula can be computed using a more exhaustive selection of CTL operators. A finer grained explicit solution could allow one to experiment with a top-down approach as well.

Moreover, we provided a dedicated C++ implementation, and evaluated it on models of higher-level formalisms such as PROMELA. Since the resulting KSs have large state spaces, further symbolic approaches are to be considered for future work, when dealing with program graphs instead of Kripke structures. In this setting, one might also consider the synthesis problem of the relevant atomic propositions from the exposed program variables. Nevertheless, the experiments on Kripke structures already showcase the benefits of the approxi- Runtime of (CTL U , β, ¬) in milliseconds Runtime of other options in milliseconds

Parameters (CTL∀, β, ¬) (CTL, β) (CTL, β, ¬) (CTL∀, β) (CTLU, β)
Fig. 6. Comparing (CTL U , β, ¬) to other options on every sample. mated recurrence diameter computation and of our extension of the syntactic DAG definition, as well as the limited relevance of the CTL fragment considered.

Another avenue for optimizations can be inferred from the existing SAT-based LTL learning literature: in particular, Rienier et al. [START_REF] Riener | Exact synthesis of ltl properties from traces[END_REF] relied on a topologyguided approach by explicitly enumerating the possible shapes of the syntactic DAG and solving the associated SAT instances in parallel. Given the small size on average of the formulas learnt so far and the quadratic factor impacting the number of semantic clauses such as sem ∀U due to the structural variables l i,j and r i,k , this approach could yield huge performance gains in CTL's case as well.

Finally, we would like to find the exact complexity class of the CTL learning problem. It is known to be NP-hard, but determining whether it is NP or not remains an open problem. We intuit that it is not, Kripke structures being a denser encoding in terms of information than lists of linear traces: as an example, one can trivially compute a LTL formula (resp. a CTL formula) of polynomial size that distinguishes a sample of ultimately periodic words (resp. of finite computation trees with lasso-shaped leaves), but the same cannot be said of a sample of Kripke structures. It remains to be seen if this intuition can be confirmed or infirmed by a formal proof.

By induction hypothesis, D

q ′ 1 ,q ′ 2 is well-defined, q ′ 1 |= D q ′ 1 ,q ′ 2 and q ′ 2 ̸ |= D q ′ 1 ,q ′ 2 . As a consequence, D q1,q2 is well-defined, q 1 |= ∃X q ′ 2 ∈δ(q2) D q ′ 1 ,q ′ 2 , and q 2 ̸ |= ∃X q ′ 2 ∈δ(q2) D q ′ 1 ,q ′ 2 .
We handle the case where ∃ q ′ 2 ∈ δ(q 2 ), ∀ q ′ 1 ∈ δ(q 1 ), q ′ 1 ̸ ∼ c q ′ 2 in a similar fashion. As a consequence, the property holds at rank c + 1.

Therefore, for each q + ∈ S + and each q -∈ S -, q + |= D q + ,q -and q -̸ |= D q + ,q -. Hence, q + |= S K (S + , S -) and q -̸ |= S K (S + , S -).

⊓ ⊔

C Proof of Corollary 1

First, given q + ∈ S + and q -∈ S -, let us bound the size of D q + ,q -based on their characteristic number c q1,q2 = C K ({q 1 }, {q 2 }).

c q1,q2 = 0 =⇒ |D q + ,q -| ≤ 2 as λ(q 1 ) ̸ = λ(q 2 ) c q1,q2 ≥ 1 =⇒ |D q + ,q -| ≤ (k + 1) + q ′ 2 ∈δ(q2) |D q ′ 1 ,q ′ 2 | for some q ′ 1 ∈ δ(q 1 ) or |D q + ,q -| ≤ (k + 1) + q ′ 1 ∈δ(q1) |D q ′ 1 ,q ′ 2 | for some q ′ 2 ∈ δ(q 2 )
We are looking for an upper bound (U n ) n≥0 such that ∀ n ∈ N, ∀ q + ∈ S + , ∀ q -∈ S -, if c q + ,q -≤ n, then |D q + ,q -| ≤ U n . We define it inductively:

U 0 = 2 U n+1 = k • U n + k + 1 Assuming k ≥ 2, we explicit the bound U n = (2 + k+1 k-1 ) • k n -k+1 k-1 ≤ 5 • k n . As ({q + }, {q -}) is a sub-sample of S, c q + ,q -≤ c and |D q + ,q -| ≤ U c ≤ 5 • k c .
We can finally bound the size of S K (S + , S -):

|S K (S + , S -)| ≤ (|S + | -1) • (|S -| -1) + q + ∈S + q -∈S - |D q + ,q -| ≤ |S + | • |S -| + |S + | • |S -| • U c ≤ (5 • k c + 1) • |S + | • |S -|
Yielding the aforementioned upper bound. If k = 1, then U n = 2 • n + 2 and the rest of the proof is similar to the previous case.

⊓ ⊔

D Encoding the Syntactic DAG

The clauses encoding the syntactic DAG are the following:

i∈[1. .n] o∈L τ o i ∧ o 1 ,o 2 ∈L o 1 ̸ =o 2 [¬τ o 1 i ∨ ¬τ o 2 i ] (xorτ ) i∈[1. .n] j∈[0. .i-1] li,j ∧ j,k∈[0. .i-1] j<k [¬li,j ∨ ¬l i,k ] (xor l ) i∈[1. .n] j∈[0. .i-1] ri,j ∧ j,k∈[0. .i-1] j<k [¬ri,j ∨ ¬r i,k ] (xorr) i∈[1. .n] a∈AP∪{⊤} [τ a i =⇒ (li,0 ∧ ri,0)] (ar0) i∈[1. .n] o∈{¬,∀X,∀F,∀G} [τ o i =⇒ (li,0 ∧ ¬ri,0)] (ar1) i∈[1. .n] o∈{∧,∨,∀U} [τ o i =⇒ (¬li,0 ∧ ¬ri,0)] (ar2)
Note in particular that clauses xor τ to ar 2 do not encode a single syntactic DAG of size n as they do not guarantee connectivity, but instead a forest of DAGs, as shown in Figure 7. However, we will only keep the DAG rooted in node n, being the only one later clause sem φ enforces semantic constraints on. Figure 7 displays a forest of DAGs resulting in formula φ = ∀ a U ¬b rooted in node 7.

∀U [START_REF] Clarke | Design and synthesis of synchronization skeletons using branching time temporal logic[END_REF] a [START_REF] Browne | Characterizing finite kripke structures in propositional temporal logic[END_REF] ¬ [START_REF] Bjørklund | Approximating longest directed paths and cycles[END_REF] b [START_REF] Biere | Symbolic model checking without bdds[END_REF] ∀X [START_REF] Bordais | Learning temporal properties is np-hard[END_REF] c [START_REF] Baier | Principles of model checking[END_REF] ⊤ [START_REF] Camacho | Learning interpretable models expressed in linear temporal logic[END_REF] Fig. 7. A valid forest of syntactic DAGs of size n = 7. The exponent stands for the index of each node.

E Encoding the Boolean Operators

The clauses encoding the semantics of the Boolean operators are the following:

i∈[2. .n] k∈[1. .i-1] (τ ¬ i ∧ r i,k ) =⇒ q∈Q (φ q i ⇐⇒ ¬φ q k ) (sem¬) i∈[2. .n] j,k∈[1. .i-1] (τ ∧ i ∧ li,j ∧ r i,k ) =⇒ q∈Q (φ q i ⇐⇒ [φ q j ∧ φ q k ]) (sem∧) i∈[2. .n] j,k∈[1. .i-1] (τ ∨ i ∧ li,j ∧ r i,k ) =⇒ q∈Q (φ q i ⇐⇒ [φ q j ∨ φ q k ]) (sem∨)
F A Spurious Fixed Point

The semantics of the temporal operators ∀F, ∀G and ∀U are significantly harder to model than ∀X or the Boolean connectors: consider that the inductive property (q |= ∀G a) ⇐⇒ (q |= a) ∧ q ′ ∈δ(q)

(q ′ |= ∀G a) holds. Yet the naive encoding

(τ ∀G 2 ∧ r 2,1 ) =⇒ q∈Q φ q 2 ⇐⇒ φ q 1 ∧ q ′ ∈δ(q) φ q ′ 2
may in some cases result in a spurious fixed point, as depicted in Figure 8.

K a q1 a q2 a q3
∀G [START_REF] Biere | Symbolic model checking without bdds[END_REF] a [START_REF] Baier | Principles of model checking[END_REF] φ q 1 1 = 1 φ q 2 1 = 1 φ q 3 1 = 1 φ q 1 2 = 0 φ q 2 2 = 0 φ q 3 2 = 0 Intuitively, while every state of K verifies the atomic proposition a, each state q that belongs to the loop can claim it does not verify ∀G a (i.e. φ q 2 = 0) as its successor q ′ claims it does not either (since φ q ′ 2 = 0), hence complying with the naive semantic equivalence clause outlined previously.

G Encoding the Universal Operators

The clauses encoding the semantics of the temporal operators ∀G and ∀F are the following:

i∈[2. .n] k∈[1. .i-1] (τ ∀F i ∧ r i,k ) =⇒ q∈Q u∈[1. .α(q)]
ρ u i,q ⇐⇒ φ q k ∨ q ′ ∈δ(q) ρ min(α(q ′ ),u-1) i,q ′ (sem ∀F )

i∈ [2. .n] k∈ [1. .i-1] (τ ∀G i ∧ r i,k ) =⇒ q∈Q u∈[1. .α(q)] ρ u i,q ⇐⇒ φ q k ∧ q ′ ∈δ(q) ρ min(α(q ′ ),u-1) i,q ′ (sem ∀G )

H Encoding the Existential Operators

The existing syntactic clauses xor τ , ar 1 , and ar 2 as well as the clauses sem ρ , ascent ρ , descent ρ , no ρ , and base ρ regulating the bounded semantics should be updated to take the existential operators ∃X, ∃F, ∃G, and ∃U into account. Then the following clauses encoding the existential semantics should be added:

i∈[2. .n] k∈[1. .i-1] (τ ∃X i ∧ r i,k ) =⇒ q∈Q φ q i ⇐⇒ q ′ ∈δ(q) φ q ′ k (sem ∃X ) i∈[2.
.n] k∈ [1. .i-1] (τ ∃F i ∧ r i,k ) =⇒ q∈Q u∈[1. .α(q)] ρ u i,q ⇐⇒ φ q k ∨ q ′ ∈δ(q) ρ min(α(q ′ ),u-1) i,q ′ (sem ∃F )

i∈ [2. .n] k∈ [1. .i-1] (τ ∃G i ∧ r i,k ) =⇒ q∈Q u∈[1. .α(q)] ρ u i,q ⇐⇒ φ q k ∧ q ′ ∈δ(q) ρ min(α(q ′ ),u-1) i,q ′ (sem ∃G )

i∈ [2. .n] j,k∈ [1. .i-1] (τ ∃U i ∧ li,j ∧ r i,k ) =⇒ q∈Q u∈[1. .α(q)] ρ u i,q ⇐⇒ φ q k ∨ φ q j ∧ q ′ ∈δ(q) ρ min(α(q ′ ),u-1) i,q ′ (sem ∃U )

I Updated Clauses with Embedded Negations

We consider the following updated semantic clauses:

i∈[2. .n] j∈[1. .i-1] (τ ∀X i ∧ li,j) =⇒ q∈Q [(¬νi ∧ ¬φ q i ) ∨ (νi ∧ φ q i )] ⇐⇒ q ′ ∈δ(q) φ q ′ j ( s em ∀X ) i∈[1. .n] q∈Q (τ ⊤ i =⇒ [(¬νi ∧ ¬φ q i ) ∨ (νi ∧ φ q i )]) ( s em ⊤ )
i∈ [1. .n] q∈Q a∈λ(q) (τ a i =⇒ [(¬νi ∧ ¬φ q i ) ∨ (νi ∧ φ q i )])

∧ a̸ ∈λ(q)
(τ a i =⇒ ¬[(¬νi ∧ ¬φ q i ) ∨ (νi ∧ φ q i )]) ( s ema)

i∈ [2. .n] j,k∈ [1. .i-1] (τ ∧ i ∧ li,j ∧ r i,k ) =⇒ q∈Q ([(¬νi ∧ ¬φ q i ) ∨ (νi ∧ φ q i )] ⇐⇒ [φ q j ∧ φ q k ])

( s em∧) i∈[2.
.n] j,k∈ [1. .i-1] (τ ∨ i ∧ li,j ∧ r i,k ) =⇒ q∈Q ([(¬νi ∧ ¬φ q i ) ∨ (νi ∧ φ q i )] ⇐⇒ [φ q j ∨ φ q k ])

( s em∨) i∈[2.
.n] o∈{∀F,∀G,∀U}

¬τ o i =⇒ q∈Q ([(¬νi ∧ ¬φ q i ) ∨ (νi ∧ φ q i )] ⇐⇒ ρ α(q)
i,q ) ( s emρ)

J Generating a test sample with mutations

Given a KS K = (Q, δ, λ) and k ∈ N * , we design a k-mutant K ′ = (Q ′ , δ ′ , λ ′ ) of K by randomly applying these mutation rules k times to a copy of K, as shown in Figure 9:

Mutating states. Pick a random state q ∈ Q and randomly pick a new label λ ′ (q) ∈ 2 AP such that λ ′ (q) ̸ = λ(q). Mutating outgoing edges. Pick two random states q ∈ Q and q ′ ∈ δ(q), remove q ′ from δ ′ (q), and add instead if it exists a new destination q ′′ to δ ′ (q) such that q ′′ ̸ ∈ δ(q). Creating mutant states. Pick two random states q ∈ Q and q ′ ∈ δ(q), remove q ′ from δ ′ (q), add a new state q ′′ to Q ′ such that q ′′ ∈ δ ′ (q), q ′ ∈ δ ′ (q ′′ ), and λ ′ (q ′′ ) is a random element of 2 AP K a q q q ′ q ′′ q q ′ K ′ b q q q ′ q ′′ q q ′ q ′′ Fig. 9. The original KS K and the resulting effect of mutation rules on K ′ .

4. 3

 3 Solving the SAT instance We finally define the formula Φ n as the conjunction of all the aforementioned clauses. Assuming an upper bound d on the KS's recurrence diameter, this encoding requires O(n 2 + n • |AP| + n • |Q| • d) variables and O(n • |AP| + n 3 • |Q| • d + n • |AP| • |Q|) clauses, not taking transformation to conjunctive normal form into account. By design, Lemma 1 holds.

Fig. 5 .

 5 Fig. 5. Number of timeouts at ten minutes | arithmetic mean (in milliseconds) on the 178 samples that never timed out of various options and fragments.

Figure 6 .

 6 Figure 6.2 further displays a log-log plot comparing the runtime of the most relevant fragments and options to (CTL U , β, ¬). For a given set of parameters, each point stands for one of the 234 test samples. Points above the black diagonal favour (CTL U , β, ¬); points below, the aforementioned option. Points on the second dotted lines at the edges of the figure represent timeouts.

Fig. 8 .

 8 Fig. 8. Naive semantics result in the incorrect claim that q1 ̸ |= ∀G a.

A Proof of Theorem 3 ∀F. Assume that q |= ∀F φ. Let us prove that q |= ∀F α(q) φ. Consider a run r = (s i ) ∈ R(q). By hypothesis, we can define the index j = min{i ∈ N | s i |= φ}. Now, assume that j > α(q). By definition of the recurrence diameter α,

. By definition of j, ∀ i ∈ N, s ′ i ̸ |= φ in order to preserve the minimality of j. Yet r ′ ∈ R(q) and q |= ∀F φ. By contradiction, j ≤ α(q). As consequence, (q |= ∀F φ) =⇒ (q |= ∀F α(q) φ) holds.

Trivially, (q |= ∀F α(q) φ) =⇒ (q |= ∀F φ) holds. Hence, we have proven both sides of the desired equivalence for ∀F.

∀G. Assume that q |= ∀G α(q) φ. Let us prove that q |= ∀G φ. Consider a run r = (s i ) ∈ R(q) and j ∈ N. Let us prove that s j |= φ.

State s j is obviously reachable from q. Let us consider a finite run without repetition u = (s ′ i ) i∈[0.

.k] such that s 0 = q and s ′ k = s j . By definition of the recurrence diameter, k ≤ α(q). We define the infinite runs v = (s i ) i>j and r ′ = u • v. Since r ′ ∈ R(q) and q |= ∀G α(q) φ, s k |= φ, hence s j |= φ. As a consequence, (q |= ∀G α(q) φ) =⇒ (q |= ∀G φ).

Trivially, (q |= ∀G φ) =⇒ (q |= ∀G α(q) φ) holds. Hence, we have proven both sides of the desired equivalence for ∀G. ∃F and ∃G. Formula ∃F φ (rep. ∃G φ) being equivalent to the dual formula ¬ ∀G ¬φ (resp. ¬ ∀F ¬φ), the previous proofs immediately yield the desired equivalences.

∀U and ∃U. We can handle the case of ∀ φ U ψ in a manner similar to ∀F: we prove by contradiction that the first occurrence of ψ always happens in less than α(q) steps. And the semantic equivalence for ∃ φ U ψ can be handled in a fashion similar to ∀G: an existing infinite run yields a conforming finite prefix without repetition of length lesser than or equal to α(q).

B Proof of Theorem 5

Given two dissimilar states q 1 , q 2 ∈ Q, let us prove by induction on the characteristic number c q1,q2 = C K ({q 1 }, {q 2 }) that q 1 |= D q1,q2 and q 2 ̸ |= D q1,q2 .

Base case. If c q1,q2 = 0, then by definition λ(q 1 ) ̸ = λ(q 2 ) and by design D q1,q2 is a literal (i.e. an atomic proposition or the negation thereof) verified by q 1 but not by q 2 . Inductive case. Assume that the property holds for all characteristic numbers smaller than or equal to c ∈ N. Consider two states q 1 , q 2 ∈ Q such that c q1,q2 = c + 1. By definition of the refined equivalence relation ∼ c+1 , ∃ q ′ 1 ∈ δ(q 1 ), ∀ q ′ 2 ∈ δ(q 2 ), q ′ 1 ̸ ∼ c q ′ 2 , hence c q ′ 1 ,q ′ 2 ≤ c.