B M Mclaughlin

Teck-Ghee Lee

J A Ludlow

E Landi

M S Pindzola S D Loch

C P Ballance

published or not. The documents may come   L'archive ouverte pluridisciplinaire

A large-scale R-matrix calculation for electron-impact excitation of the Ne 2+ , O-like ion B M McLaughlin 1,2 †, Teck-Ghee Lee 3 , J A Ludlow 3 , E Landi 4 , S D Loch 3 , M S Pindzola 3 and C P Ballance 3 ‡, 1 gentre for heoretil etomiD woleulr nd yptil hysis @gewyAD hool of wthemtis nd hysisD he hvid ftes fuildingD U gollege rkD ueen9s niversity felfstD felfst fU IxxD u 2 snstitute for heoretil etomi nd woleulr hysisD rrvrd mithsonin genter for estrophysisD wEIRD gmridgeD we HPIQVD e 3 heprtment of hysisD euurn niversityD euurnD ev QTVRWD e 4 heprtment of etmospheriD yeni nd pe ienesD niversity of wihignD enn eror ws RVIHWD e Abstract.

he (ve tΠ levels within np 2 or np 4 ground stte omplex provide n exellent testing ground for the omprison of theoretil line rtios with strophysilly oserved vluesD in ddition to providing vlule eletron temperture nd density dignostisF he low temperture nture of the line rtios ensure tht the theoretilly derived vlues re sensitive to the underlying tomi struture nd eletronEimpt exittion rtesF revious E mtrix lultions for the yElike xe ionD xe 2+ D exhiit spurious struture in the ross setions t higher eletron energiesD whih my 'et wxwellin verged rtes even t low temperturesF purthermoreD there is n sene of omprehensive exittion dt etween the exited sttes tht my provide newer dignostis to ompliment the more estlished lines disussed in this pperF o resolve these issuesD we present oth smllEsle STElevel freitEuli @fA lultion nd lrgeEsle SSR levels Emtrix sntermedite goupling prme rnsformtion @sgpA lultion tht extends the sope nd vlidity of erlier tetyw lultions oth in terms of the tomi struture nd sttering ross setionsF yur results provide omprehensive eletronEimpt exittion dt set for ll trnsitions to higher n-shellsF he fundmentl tomi dt for this yElike ion is susequently used within ollisionl rditive frmework to provide the intensity line rtios ross rnge of eletron tempertures nd densities of interest in strophysil oservtionsF eg numersX QPFVHp Short title: Electron impact excitation of Ne 2+ ions Revised: J. Phys. B: At. Mol. & Opt. Phys: 14 June 2011

Introduction

Electron-impact excitation rates are a fundamental component of collisional radiative modelling. In particular, the excitation rates for O-like Ne (Ne 2+ ), the focus of this paper, are applicable in diagnosing the spectral lines not only from astrophysical observations but also from fusion plasma studies. It has been shown that transitions within the rst ve levels of an atom with the np 4 ground conguration can provide a valuable diagnostic of the electron temperature [1] and the electron density [2]. Recently, an updated electron-impact excitation calculation of Munoz et al. [3] for the 3s 2 3p 4 ground state complex of O-like Ar (Ar 2+ ) found that the plasma diagnostics were particularly sensitive to near threshold resonances, and therefore, Ne 2+ may oer a similar diagnostic potential, but without the high sensitivity to single near threshold resonance as found in the Ar 2+ case.

Neon plays an important role in a variety of astrophysical phenomena, being the most abundant rare gas in the universe after helium. Forbidden Ne III lines have been observed in a variety of astrophysical plasmas. The lines at 36 µm and 3869 Å, due to forbidden 3 P 0 → 3 P 1 and 1 D 2 → 3 P 2 transitions within the ground conguration, have been observed in H II regions by a number of authors [4,5,6,7]. The Ne III 3869 Å line is also present in Ne-rich laments in the Supernova Cas A remnant [8,9] and can be used to investigate the neon abundance and its spatial distribution throughout the remnant.

In terms of laboratory measurements, the identication of Ne III lines were reviewed by Persson et al. [10] and the low lying terms are depicted in Fig 1 .  The present R-matrix calculation now includes shells of suciently high principal quantum numbers for a direct comparison with signicantly more of their listed lines. More recently, James and co-workers [11] measured electron-impact excitation cross sections for transitions in the far ultraviolet wavelength range between 1200 and 2700 Å using an electron-ion impact collision chamber. Daw et al. [12] have measured a pair of lines within the ground-state complex. The spin forbidden line 1 S 0 → 3 P 1 and the quadrupole 1 S 0 → 1 D 2 line oer diagnostic potential. Finally, Fig 2 illustrates the transitions of interest in the planetary nebulae NGC 3918 [13] for Ne III. The wavelength of the astrophysically observed transitions are labelled in units of Angstroms.

An overview of the various theoretical models investigating electron impact excitation of Ne 2+ is summarized in the introduction of McLaughlin and Bell [14]. This includes the work of Seaton [15,16,17] in the 1950s, and continues through a progression of the perturbative calculations (e.g., and distorted wave [19] in 1960s-1970s) yet only for transitions within the 1s 2 2s 2 2p 4 ground state complex. These were followed by early R-matrix calculations of Pradhan [20] and Butler and Mendoza [21] using a program of Saraph [22,23] to transform LScoupled K-matrices into level-level cross sections using the JAJOM code. This work included six states in the close coupling expansion and clearly illustrated the sensitivity of excitation rates when adopting either theoretically calculated or experimentally observed energy level values.

Between 1999 and 2001, McLaughlin and co-workers in a couple of papers [14,24] extended this model to 28 LS terms or 56 levels arising from the following 1s 2 2s 2 2p 4 , 2s2p 5 , 2s 2 2p 3 3l(l=0-2), 2s 2 2p 3 4s congurations, with the extra 4p, 4d orbitals used only as an improvement in the description of the target's states. However, as evident in Fig. 5 of Ref. [14] there is a breakdown in their calculation for the 28 terms model, manifesting as broad unphysical 2 eV resonances in transitions from the 3 P 0 ground state term. Unsurprisingly, this leads to corresponding unphysical increase in the eective collision strength (see Fig. 6 in Ref.[14]) at approximately 10 4.5 Kelvin. We point out that a less elaborate six-level model does not exhibit the same problem as indicated in Ref. [14].

Therefore, it would not be unreasonable, given the increase in computational power over the last decade to pursue a full Breit-Pauli R-matrix calculation for the 56 levels under consideration that would resolve and correct this problem. However, our present studies revealed that the 6 congurations listed above, actually give rise to a possible 49 terms or 95 levels. This imbalance between the congurationinteraction of the target and those levels actually used in the close coupling expansion will give rise to secondary, but a less pronounced set of pseudo-resonances above 3 Rydbergs. Therefore, to correct and also expand the scope of Ne 2+ R-matrix calculations currently in the literature we have carried out an Intermediate Coupling Frame Transformation (ICFT) [25] calculation for 554 levels. As illustrated in Ref. [3], the use of the ICFT method gives cross sections that are extremely close to a Breit-Pauli (BP) calculation if both employing the same target congurations.

The remainder of the paper is organized as follows. In section 2 we outline our small Breit-Pauli R-matrix and a large scale level ICFT R-matrix calculation used in the current study. Section 3, gives results for selected collision strengths and eective collision strengths and compares the BP and ICFT calculations. A small collisional radiative calculation is then performed in section 4, to predict observed astronomical line ratios. Finally, in the summary, we assess the impact of this now complete data set on the predictive modelling of Ne 2+ line ratios.

Details of calculations

In the smaller R-matrix Breit-Pauli model, the atomic orbitals employed were generated from the atomic structure code CIV3 [26]; in which the orbitals were energy-optimized on the lowest 28 terms; details can be found in the earlier work of 24]. A subset of 28 LS terms constructed from the following conguration list; 1s 2 2s 2 2p 4 , 1s 2 2s2p 5 , 1s 2 2s 2 2p 3 3 and 1s 2 2p 6 give rise to 56 ne-structure levels which were used in the close-coupling expansion. Extra diuse 4p and 4 d pseudo-orbitals were used only to improve the target states, but also ensured a larger R-matrix box of 15.2 a.u. A total of forty basis orbitals were used to represent the continuum basis, easily spanning the energy range from threshold to 20 Rydbergs.

In the larger ICFT calculation, the target radial wavefunctions were generated using GASP (Graphical Autostructure Package) [27], which is a java front-end for the atomic-structure code AUTOSTRUCTURE [28]. The orbitals were generated within an Thomas-Fermi-Dirac-Amaldi potential, using slightly modied lambda scaling parameters as given by Landi and Bhatia [29]. Specically we used λ 1s = 1.0, .11 and λ 4f = 1.06. However, we are able to include all 24 congurations : 2s 2 2p 4 , 2s2p 5 , 2p 6 , 2s 2 2p 3 3s, 2s 2 2p 3 3p, 2s 2 2p 3 3d, 2s 2 2p 3 4s, 2s 2 2p 3 4p, 2s 2 2p 3 4d, 2s 2 2p 3 4f , 2s2p 4 3s, 2s2p 4 3p, 2s2p 4 3d, 2s2p 4 4s, 2s2p 4 4p, 2s2p 4 4d, 2s2p 4 4f , 2p 5 3s, 2p 5 3p, 2p 5 3d, 2p 5 4s, 2p 5 4p, 2p 5 4d and2p 5 4f resulting in 554 levels; which were subsequently included in close-coupling expansion of the scattering calculation. The energies of the low lying 2s2p 5 terms were much improved over the earlier reported 1, where it is seen that the rst 33 level energies agree to within an average of 1.26% with the NIST values.

λ 2s = 1.3, λ 2p = 1.09, λ 3s = 1.13, λ 3p = 1.15, λ 3d = 1.11, λ 4s = 1.12, λ 4p = 1.1, λ 4d = 1
The advantage of applying the ICFT method is that the R-matrix inner region is essentially carried out in LS coupling, including only the mass-velocity and Darwin terms. Since we are primarily focusing on line ratios between transitions within the ground state complex, we used only 20 continuum basis functions for each continuum angular momenta to keep the dimensions of the Hamiltonian matrix to a more manageable size. The inclusion of the 4p, 4d and 4f as spectroscopic orbitals did increase the extent of the R-matrix box to 22.88 a.u, an increase of over 50% in comparison to the Breit-Pauli value. The scattering calculations were then performed with our set of parallel R-matrix programs [31,32], which are modied versions of the serial RMATRIX I programs [33]. Partial waves with total angular momentum from L = 0-35 were calculated, with the Burgess-Tully top-up method used to account for higher partial wave contributions. However, considering the temperatures of astronomical interest here this should be more than sucient to converge our excitation rates.

In the outer region, the calculation of the cross sections was split into two energy regions. Region 1 spans the energy range from the rst excitation threshold up to the ionization threshold, whereas region 2 spans the energy range from from the ionization limit to four times the threshold. In region 1, for both the BP and ICFT models, we used a ne energy mesh of 40,000 points to resolve the ne Rydberg resonance structure. To account for the limited contribution of the higher partial waves to the low energy cross sections, we interpolated a coarse mesh of 200 energy points and added this to the ne mesh cross section. In region 2, above the ionisation limit, where a coarse mesh is applicable, only 200 energy points were also used for both the exchange and non-exchange calculations. The resulting total collision strengths were subsequently Maxwellian averaged across a range of electron temperatures and the eective collision strengths [34] archived for modelling. For comparison with the 56 level BP calculation, the collision strength le of the 554 level ICFT model was reduced to include only those transitions between the lowest 56 levels.

Collision strengths and eective collision strengths

In Fig. 3, a representative set of collision strengths for transitions within the ground state 2s 2 2p 4 multiplet is given. It has been shown in previous studies, such as those of Grin et al. [25] and Munoz et al. [3] that both ICFT and BP calculations for atomic ions should provide essentially identical results, provided that the number of terms/levels included in the conguration-interaction and close-coupling expansions are the same.

However, this is evidently not the case for the BP calculation shown in Fig. 3, as although the background collision strengths between the ICFT and the BP are similar, there are spurious resonances in the BP calculation, especially at approximately 10 Rydbergs. In fact, perhaps less obviously, for the BP model there should not be any resonance structure above 3.2 Rydbergs, as that is the last threshold included in that model. Such spurious resonances in the BP calculations would need to be removed if reliable rates are to be produced. Lastly, it should also be noted that the BP background collision strength is higher than ICFT.

The cumulative eect of these dierences is reected in the corresponding eective collision strengths [34] shown in Fig. 4. Over a wide range of electron temperatures, the 56 level BP eective collision strengths are consistently higher than the benchmark 554 level ICFT values. However, in terms of line ratios, a low density model using the coronal approximation involves the ratio of the eective collision strengths, which can lead to smaller than expected dierences in the predicted line ratios, see the results in section 4.

Figure 5 shows the 2s 2 2p 3 3s( 3 S 1 )→ 2s 2 2p 3 3p( 3 P 2,1,0 ) collision strengths as a function of electron energy. In this case, although small dierences can be seen, the 554 levels ICFT and 56 levels BP calculations are in reasonable accord with each other. This level of agreement (i.e., ∼15-25%) was expected and typical for the collision strengths calculated as more target states are included in the scattering calculation. As anticipated, in Fig. 6, the corresponding eective collision strengths are indeed in good agreement between the two calculations.

Emissivity Modelling

Temperature and density sensitive energy intensity ratios between transitions among the ground state 3s 2 3p 4 multiplet have been studied for Ar III [2, 3]. Here we examine the corresponding energy intensity ratios for transitions among the ground state 2s 2 2p 4 multiplet of Ne III. The eective collision strengths are processed through the ADAS suite of codes (http://www.adas.ac.uk) with the rst 5 levels in both the 56 level BP and 554 level ICFT calculation, moved to NIST energies and NIST Einstein Acoecients where available. The NIST values are taken primarily from the work of Froese Fischer and Tachiev [35] and Kramida and Nave [36]. The wavelengths for the various transitions used in the emissivity modelling are given in gure 4.

For the temperatures and densities of interest, cascades from higher levels are not signicant. Therefore, although both the ICFT and BP collisional rates include those involving the rst 56 levels, only the transitions within the ground state complex are important for the following line ratios. Both datasets used the same A-values for transitions within the ground conguration.

We rst examine the temperature sensitive energy intensity ratio

R 1 = (N 4 A 4→1 /λ 4→1 ) + (N 4 A 4→2 /λ 4→2 ) N 5 A 5→4 /λ 5→4 (1)
with N i the population in energy level i, A i→j the Einstein A coecient for a transition between energy levels i and j and λ i→j the corresponding wavelength for the transition. Note that the index numbers for the levels are given in Table 1.

The BP and ICFT results are shown in Fig. 7. The BP and ICFT results are in good agreement with each other even though the BP eective collision strengths for these transitions were higher than the ICFT results. This is due to a cancellation of errors in the ratio. Due to the fact that the BP eective collision strengths for transitions within the ground conguration are in general higher than the ICFT ones, the BP model has increased emissivities for all of the transitions. While this does not result in a large change in the line ratios, one would see a dierence when looking at absolute intensities of individual spectral lines. The results from the BP model provides larger emissivities which can aect measurements of the Ne elemental abundances, since such measurements are obtained using the absolute emissivity, or the ratio with the emissivity of a completely dierent ion/element. The measurements based on the BP results would lead to a lower Ne abundance.

Next we consider the density sensitive energy intensity ratio

R 2 = N 4 A 4→1 /λ 4→1 N 2 A 2→1 /λ 2→1 (2)
with the BP and ICFT results shown in Fig. 8. The R 2 ratio for the BP and ICFT results agree closely with each other and show a strong density dependence between electron densities of 10 4 and 10 8 cm -3 . As for the R 1 ratio, the R 2 ratio for Ne III shows a wider range of variation than the R 2 ratio for Ar III. Therefore, although systematically the two systems are both excellent density diagnostics, the Ne III is the marginally better option.

Summary

A large scale electron-impact excitation calculation of this O-like ion was carried out to investigate high energy irregularities in the cross sections of an earlier Rmatrix calculation and the subsequent impact on line ratios. We have resolved these issues, and have benchmarked eective collision strengths for use in the modelling of laboratory and astrophysical plasmas. As an illustration of an application of these eective collision strengths, a study was undertaken into the viability of applying the same Ar III line ratios [3] to the Ne III case. Overall, the O-like ion, Ne III, exhibits great promise in diagnosing the temperature and density of Ne III in planetary nebulae plasmas, being more sensitive than the equivalent Ar III line ratios.

Our eective collisions strengths for the 554 level ICFT R-matrix calculation shall be made available on the Oak Ridge National Laboratory Atomic Data website (http://www-cfadc.phy.ornl.gov/data_and_codes) and in the ADAS database (http://www.adas.ac.uk).

Acknowledgements

It is a pleasure to thank Professor A Dalgarno FRS, for drawing our attention to this problem and the need for accurate atomic data required for the modelling of planetary nebulae. T-G Lee, C P Ballance and J A Ludlow were supported by US Department of Energy (DoE) grants through Auburn University. E Landi acknowledges support from NASA grants NNX10AM17G and NNX11AC20G. B M McLaughlin acknowledges support by the US National Science Foundation through a grant to ITAMP at the Harvard-Smithsonian Center for Astrophysics. The computational work was carried out at the National Energy Research Scientic Computing Center in Oakland, CA, USA and on the Tera-grid at the National Institute for Computational Sciences (NICS) in Knoxville, TN, USA, which is supported in part by the US National Science Foundation.

I he oertis w wD hufour t nd runt IWVU tF oyF estronF oF gnF 81 IWS P ueenn p nd gonlon i IWWQ estrophysF tF 410 RPT Q wunoz furgos t wD voh hD fllne g nd foivin p PHHW estronomy nd estrophysis 500 IPSQ R impson t D golgn tD uin rD irikson i p nd rs w IWWS estrophysF tF 444 UPI S uin rD impson t D rs w nd irikson i p IWWI estrophysF tF 374 STR T fldwin t eD perlnd q tD wrtin qD gorin w D got eD eterson f w nd lettek e IWWI estrophysF tF 374 SVH U golgn tD rs w D irikson i pD uin rD impson t nd ussell IWWQ estrophysF tF 413 PQU V winkowski dio estronomyF snX rFgF n de rulstD iditorD se ympF volF RD gmridge niversityD gmridge @IWSUAD pF IHU W pesen e IWWH estrophysF tF 99 IWHR IH ersson D hlström gEqD t¤ nsson v nd hi oo r y IWWI hysF evF e 43 RUWI II tmes q uD unik s nd ejello t w IWWS estrophysF tF 455 UTW IP hw eD rkinson rD mith v nd glmi e q PHHH estrophysF tF 533 . @golour onlineA i'etive ollision strengths otined y verging the ollision strengths over wxwellin temperture distriution for the eletronsF esults re shown for the trnsitions @A 2s 2 2p 4 : 3 P 2 -3 P 1 D @A 2s 2 2p 4 : 3 @golour onlineA gollision strengths for the trnsitions @A 2s 2 2p 3 3s 3 S 1 -2s 2 2p 3 3p 3 P 1 D @A 2s 2 2p 3 3s 3 S 1 -2s 2 2p 3 3p 3 P 0 D @A 2s 2 2p 3 3s 3 S 1 -2s 2 2p 3 3p 3 P 2 s funtion of the inident eletron energyF he solid lk line indites the SSR level sgp results nd the dshed red line indites the ST level freitEuli resultsF . @golour onlineA i'etive ollision strengths otined y verging the ollision strengths over wxwellin temperture distriution for the eletronsF esults re shown for the trnsitions @A 2s 2 2p 3 3s 3 S 1 -2s 2 2p 3 3p 3 P 1 D @A 2s 2 2p 3 3s 3 S 1 -2s 2 2p 3 3p 3 P 0 D @A 2s 2 2p 3 3s 3 S 1 -2s 2 2p 3 3p 3 P 2 s funtion of the eletron temperture @uAF he solid lk line indites the SSR level sgp results nd the dshed red line indites the ST level freitEuli resultsF . @golour onlineA R 2 line rtio s funtion of eletron density for eletron tempertures of @A SHHHu @A VHHHu @A ISHHHuD nd @dA QHHHHuF he solid lk line shows the results using the SSR level sgp Emtrix lultion nd the dotEdshed lue line shows the result using the ST level freitEuli E mtrix lultionF

P 2 -3 P 1 D @A 2s 2 2p 4 : 3 P 2 -1 D 2 D @A 2s 2 2p 3 : 3 P 1 -1 D 2 nd @dA 2s 2 2p 4 : 1 D 2 -1 S
P 2 -1 D 2 D @A 2s 2 2p 3 : 3 P 1 -1 D 2 nd @dA 2s 2 2p 4 : 1 D 2 -1 S 0 s

Figure 1 .Figure 2 Figure 3 .

 123 Figure 1. xe sssD energy level digrm @levels given in eA showing the oserved low lying levels of xesss from the lortory work of ersson et al. IHF

  Figure3. @golour onlineA gollision strengths for the trnsitions @A 2s 2 2p 4 : 3 P 2 -3 P 1 D @A 2s 2 2p 4 : 3 P 2 -1 D 2 D @A 2s 2 2p 3 : 3 P 1 -1 D 2 nd @dA 2s 2 2p 4 : 1 D 2 -1 S 0 s funtion of the inident eletron energyF he solid lk line indites the SSR level sgp results nd the dshed red line indites the ST level freitEuli resultsF

  Figure 5.

  Figure6. @golour onlineA i'etive ollision strengths otined y verging the ollision strengths over wxwellin temperture distriution for the eletronsF esults re shown for the trnsitions @A 2s 2 2p 3 3s 3 S 1 -2s 2 2p 3 3p 3 P 1 D @A 2s 2 2p 3 3s 3 S 1 -2s 2 2p 3 3p 3 P 0 D @A 2s 2 2p 3 3s 3 S 1 -2s 2 2p 3 3p 3 P 2 s funtion of the eletron temperture @uAF he solid lk line indites the SSR level sgp results nd the dshed red line indites the ST level freitEuli resultsF

Figure 7 .

 7 Figure7. @golour onlineA R 1 line rtio s funtion of eletron temperture for n eletron density of Ne = 1 × 10 3 m 3 F he solid lk line shows the results using the SSR level sgp Emtrix lultion nd the dotEdshed lue line shows the result using the ST level freitEuli Emtrix lultionD with the energies nd trnsition rtes for the (rst S levels in oth Emtrix lultions shifted to xs energies nd trnsition rtesQH for the modelling lultionsF

Table 1 .

 1 e smple omprison of our theoretil energies from the SSRElevel modelD in ydergsD for the (rst QQ levels of xe sss with the xs QH tulted vluesF

	Level No. Conguration Term a	Energy	Energy ∆(%) b Th. Order
				(Experiment) (Theory)
	1	2s 2 2p 4	3 P 2	0.00000	0.00000	0.00	1
	2	2s 2 2p 4	3 P 1	0.00585	0.00569	2.74	2
	3	2s 2 2p 4	3 P 0	0.00839	0.00837	0.24	3
	4	2s 2 2p 4	1 D 2	0.23548	0.25804	9.58	4
	5	2s 2 2p 4	1 S 0	0.50806	0.49160	3.24	5
	6	2s 1 2p 5	3 P 2	1.86163	1.91958	3.11	6
	7	2s 1 2p 5	3 P 1	1.86694	1.92512	3.12	7
	8	2s 1 2p 5	3 P 0	1.86987	1.92791	3.10	8
	9	2s 1 2p 5	1 P 1	2.63792	2.80123	6.19	9
	10	2p 3 3s	5 S 2	2.82384	2.81852	0.19	10
	11	2p 3 3s	3 S 1	2.91087	2.91399	0.11	11
	12	2p 3 3p	5 P 1	3.17481	3.15680	0.57	12
	13	2p 3 3p	5 P 2	3.17509	3.15720	0.56	13
	14	2p 3 3p	5 P 3	3.17558	3.15781	0.56	14
	15	2p 3 3s	3 D 3	3.21799	3.21957	0.05	17
	16	2p 3 3s	3 D 2	3.21825	3.21940	0.04	16
	17	2p 3 3s	3 D 1	3.21844	3.21934	0.03	15
	18	2p 3 3p	3 P 1	3.25096	3.26061	0.30	18
	19	2p 3 3p	3 P 0	3.25105	3.26065	0.30	19
	20	2p 3 3p	3 P 2	3.25106	3.26075	0.30	20
	21	2p 3 3s	1 D 2	3.26169	3.26701	0.16	21
	22	2p 3 3s	3 P 1	3.41259	3.37052	1.23	23
	23	2p 3 3s	3 P 0	3.41260	3.37048	1.23	22
	24	2p 3 3s	3 P 2	3.41266	3.37064	1.23	24
	25	2p 3 3s	1 P 1	3.46123	3.42538	1.04	25
	26	2p 3 3p	1 P 1	3.53537	3.51826	0.48	26
	27	2p 3 3p	3 D 1	3.54523	3.52981	0.43	27
	28	2p 3 3p	3 D 2	3.54533	3.53017	0.43	28
	29	2p 3 3p	3 D 3	3.54596	3.53137	0.41	29
	30	2p 3 3p	3 F 2	3.56670	3.55916	0.21	30
	31	2p 3 3p	3 F 3	3.56684	3.55965	0.20	31
	32	2p 3 3p	3 F 4	3.56703	3.56029	0.19	32
	33	2p 3 3p	1 F 3	3.57947	3.57865	0.02	33
	a 2S+1 L J
	b absolute percentage dierence relative to NIST values
	CIV3 values [26], with only the rst 1 D 2 level at a 9.6% dierence being the greatest
	outlier relative to NIST energy level values [30]. A representative sample of the full
	554 level calculation, is illustrated in Table

  vIUW IQ glegg i D torey t nd rrrington t IWVT wonF xotF F estronF oF 221 TI IR wvughlin f w nd fell u v PHHH tF hysF fX etF wolF yptF hysF 33 SWU IS eton w t IWSQ roF F oF e 218 QSS IT eton w t IWSS roF F oF e 264 RHH IU eton w t IWSV evF wodF hysF 30 WUW IV flh w IWTV ennF estrophysF 31 QII IW gzyzk tD uruger uD rph r i nd hemming t IWTU roF hysF oF 92 IIRT PH rdhn e u IWUR tF hysF fX etF wolF yptF hysF 17 vSHQ PI futler u nd wendoz g IWVR wonF xotF oyF estronF oF 208 IU PP rph r i IWUV gomputF hysF gommunF 15 PRU PQ rph r i nd iissner gomputF hysF gommunFD to e pulishedF PR wvughlin f wD hw e nd fell u v PHHP tF hysF fX etF wolF yptF hysF 35 PVQ PS qri0n h gD fdnell x q nd indzol w IWWV tF hysF fX etF wolF yptF hysF 31 QUIQ PT riert e IWUS gomputF hysF gommunF 11 IRI PU eeD http://vanadium.rollins.edu/GASP/GASP.html PV fdnell x IWWU tF hysF fX etF wolF yptF hysF 30 I PW vndi i nd fhti e u PHHS etF ht nd xulF ht les 89 IWS QH lhenko D urmid e iD eder tD nd xs eh em @PHIIAD xs etomi petr htseD xtionl snstitute of tndrds nd ehnologyD qithersurgD whD e @http: //physics.nist.gov/asd3A QI witnik h wD qri0n h gD fllne g nd fdnell x PHHQ tF hysF fX etF wolF yptF hys 36 UIU QP fllne g nd qri0n h g PHHR tF hysF fX etF wolF yptF hys 37 PWRQ QQ ferrington u eD iissner nd xorrington r PHHS gomputF hysF gommunF 92 PWH QR iissner D wrtins de e D xussumer rD rph r i nd eton w IWTW wonF xotF F estronF oF 146 TQ QS proese pisher g nd hiev q PHHR etF ht xulF ht les 87 I QT urmid e i nd xve q PHHT iurF hysF t h 37 I

  funtion of the eletron temperture @uAF he solid lk line indites the SSR level sgp results nd the dshed red line indites the ST level freitEuli resultsF he wvelengths in engstroms for the vrious trnsitions re lso inluded for ompleteness

	30
	20						ICFT 554 levels BP 56 levels
	10
	Collision strength	0.3 0 0.3 0 2 4 6 8	0.4 0.4	0.5 0.5	0.6 0.6	0.7 0.7	0.8 0.8	0.9 0.9	1 1
		0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
				Electron energy (Rydbergs)


Christos Chouaid
email: christos.chouaid@sat.aphp.fr

Faith Nathan

Kristine Pemberton

Thomas Morris

A Phase II, randomized, multicenter study to assess the efficacy, safety and tolerability of zibotentan (ZD4054) in combination with pemetrexed in patients with advanced non-small cell lung cancer

Keywords: Zibotentan, endothelin, NSCLC, cancer, clinical trial

A phase II, randomized, multicenter study to assess the efficacy, safety, and tolerability of zibotentan (ZD4054) in combination with pemetrexed in patients with advanced non-small cell lung cancer

Introduction

Lung cancer has the highest mortality rate of all cancers, with non-small cell lung cancer (NSCLC) accounting for approximately 85% of all lung cancers [START_REF] Jemal | Cancer statistics, 2009[END_REF]. The majority of patients with NSCLC present with locally advanced inoperable or metastatic disease. Historically, patients who are not candidates for definitive locoregional therapy, receive a finite number of cycles of first-line chemotherapy with platinum doublets [2]. Second-line treatment options include pemetrexed, which has been reported to have similar efficacy and a favorable safety profile compared with docetaxel [START_REF] Hanna | Randomized phase III trial of pemetrexed versus docetaxel in patients with nonsmall-cell lung cancer previously treated with chemotherapy[END_REF]. The epidermal growth factor receptor (EGFR) tyrosine kinase inhibitors erlotinib and gefitinib have also demonstrated monotherapy activity in previously treated patients with advanced NSCLC. Erlotinib demonstrated an improvement in overall survival (OS) of 2 months in a placebo-controlled Phase III trial in the secondline setting [START_REF] Shepherd | Erlotinib in previously treated non-small-cell lung cancer[END_REF], and more recently, gefitinib was shown to be non-inferior to docetaxel in terms of OS [START_REF] Kim | Gefitinib versus docetaxel in previously treated non-small-cell lung cancer (INTEREST): a randomised phase III trial[END_REF] and demonstrated a longer progression-free survival in pretreated patients with advanced NSCLC who had an EGFR mutation [START_REF] Douillard | Molecular predictors of outcome with gefitinib and docetaxel in previously treated non-small-cell lung cancer: data from the randomized phase III INTEREST trial[END_REF]. Although several new treatments have been identified, there has been minimal improvement in median survival of patients with NSCLC [START_REF] Katzel | Recent advances of novel targeted therapy in non-small cell lung cancer[END_REF].

Endothelin-1 (ET-1), acting through the endothelin A (ET A ) receptor, is implicated in the development of several cancer types through activation of pathways involved in proliferation, migration, invasion, epithelial-mesenchymal transition, osteogenesis, and angiogenesis, while activation of the endothelin B (ET B ) receptor may induce cell death by apoptosis, promote ET-1 clearance and inhibit tumor progression [START_REF] Growcott | Preclinical anticancer activity of the specific endothelin A receptor antagonist ZD4054[END_REF].

Tumor tissues from patients with NSCLC have been shown to express ET-1, which has been correlated with poor prognosis in patients with this disease [START_REF] Boldrini | Expression of endothelin-1 is related to poor prognosis in nonsmall cell lung carcinoma[END_REF]. Furthermore, ET B receptor mRNA expression is reduced in NSCLC tissues [START_REF] Knight | Epigenetic silencing of the endothelin-B receptor gene in nonsmall cell lung cancer[END_REF].

Therefore, specific blockade of the ET A receptor may be a potential target for the treatment of patients with NSCLC.

Zibotentan (ZD4054) is a specific ET A receptor antagonist, which has demonstrated antitumor activity, both as a single agent and in combination, in a range of preclinical cancer models [START_REF] Growcott | Preclinical anticancer activity of the specific endothelin A receptor antagonist ZD4054[END_REF]. A promising signal for improved survival was observed in a Phase II monotherapy trial in patients with metastatic castration-resistant prostate cancer (CRPC) [START_REF] James | Final safety and efficacy analysis of the specific endothelin A receptor antagonist zibotentan (ZD4054) in patients with metastatic castration-resistant prostate cancer and bone metastases who were pain-free or mildly symptomatic for pain: a double-blind, placebo-controlled, randomized Phase II trial[END_REF][START_REF] Fizazi | Specific endothelin-A receptor antagonism for the treatment of advanced prostate cancer[END_REF]. Zibotentan is being further assessed in a large Phase III clinical trial program in men with CRPC [START_REF] James | Final safety and efficacy analysis of the specific endothelin A receptor antagonist zibotentan (ZD4054) in patients with metastatic castration-resistant prostate cancer and bone metastases who were pain-free or mildly symptomatic for pain: a double-blind, placebo-controlled, randomized Phase II trial[END_REF][START_REF] Fizazi | Specific endothelin-A receptor antagonism for the treatment of advanced prostate cancer[END_REF]. Zibotentan efficacy is also being tested in a number of other cancer types.

The primary objective of this study was to evaluate the relative effect of zibotentan plus pemetrexed versus pemetrexed alone on OS in patients with locally advanced or metastatic non squamous NSCLC who had failed first-line platinum-based chemotherapy. OS was selected as the primary endpoint in this study because a survival advantage was observed following treatment with zibotentan in a Phase II study of patients with castration-resistant prostate cancer. Secondary objectives included assessment of the number of patients with a disease progression event, time to clinical progression (TTP), and safety and tolerability of the combination regimen.

Methods

Study design and participants

In this double-blind, placebo-controlled, Phase II study, patients aged ≥18 years of age with locally advanced or metastatic NSCLC without predominantly squamous histology, and a World Heath Organization performance status of 0-2, who had failed one prior platinum-based chemotherapy regimen were enrolled. This study was restricted to patients with predominantly non-squamous NSCLC histology as pemetrexed is now approved in Europe for the treatment of advanced nonsquamous NSCLC only. Exclusion criteria included treatment with pemetrexed within the last 12 months, prior therapy with an ET A or ET B receptor antagonist, radiotherapy to the primary tumor within 4 weeks of study entry, use of CYP450 inducers within 2 weeks of randomization (dexamethasone was permitted as premedication for pemetrexed), brain metastases or spinal chord compression unless treated and stable without steroids for 1 month, and any significant bone marrow, renal or hepatic impairment.

Patients were randomized in a 1:1 ratio to receive once-daily zibotentan 10 mg plus 3-weekly pemetrexed 500 mg/m 2 or once-daily placebo plus 3-weekly pemetrexed 500 mg/m 2 . All patients also received the appropriate supplementary medications.

Patients were evaluated every week for the first 3 weeks of the study, and then on a 3-weekly basis whilst continuing on study medication until data cut-off for survival was reached. In addition, there was one intermediate mandatory tumor assessment visit (MTAV) to assess disease progression, which occurred approximately 3 months following the randomization of the last patient. This study was designed as a randomized screening study to quantify the level of risk entailed for further development. Thus, the type I and type II errors were adjusted to be less constrained so that the targeted treatment benefit would be apparent while the sample size remained reasonable [START_REF] Rubinstein | Design issues of randomized phase II trials and a proposal for phase II screening trials[END_REF]. A study with at least 80% power to detect a hazard ratio (HR) of 0.50 at the 2-sided, 20% significance level required approximately 38 death events. Assuming a median survival of 8 months for pemetrexed [START_REF] Hanna | Randomized phase III trial of pemetrexed versus docetaxel in patients with nonsmall-cell lung cancer previously treated with chemotherapy[END_REF], recruitment of 64 patients in 9 months was expected to yield approximately 38 death events after approximately 12 months following randomization of the last patient.

All patients provided written informed consent. The study was approved by the independent ethics committee for each trial center, and was conducted in accordance with the Declaration of Helsinki [START_REF]Declaration of Helsinki. Ethical principles for medical research involving human subjects[END_REF].

Assessments

OS was calculated as the interval from the date of randomization to the date of death from any cause. The efficacy of zibotentan in combination with pemetrexed was evaluated by assessment of objective disease progression measured using Response Evaluation Criteria In Solid Tumors (RECIST) version 1.0 [START_REF] Therasse | New guidelines to evaluate the response to treatment in solid tumors. European Organization for Research and Treatment of Cancer, National Cancer Institute of the United States, National Cancer Institute of Canada[END_REF] and/or TTP on or before the intermediate MTAV, and death by any cause. Safety and tolerability were evaluated by recording the incidence of adverse events (AEs) according to the Common Toxicity Criteria for AEs (CTCAE) version 3.0, and by monitoring b-type natriuretic peptide (BNP), weight, hematology and clinical chemistry.

Statistical analysis

OS data were analyzed using a Cox proportional hazards regression model with a factor accounting for treatment group. To evaluate the secondary objective of the efficacy of zibotentan in combination with pemetrexed versus pemetrexed alone, a primary event count analysis, TTP analysis and a sensitivity analysis were performed. The primary event count analysis compared the number of patients who had progressed or died by the MTAV using a logistic-regression model with a complementary log-log function, including a factor for treatment group. The TTP analysis was performed in support of the progression event count analysis using a

Cox proportional hazards regression model with a factor accounting for treatment group. A sensitivity analysis was performed, which assumed that the patients without a MTAV in the zibotentan and placebo groups had progressed and not progressed, respectively. The estimated HR, 80% confidence interval (CI) and P-value for OS and the efficacy analyses were calculated.

Results

Between 12 August 2008 and 17 January 2010 (data cut-off), 66 patients were randomized and completed the study. Thirty patients (45%) received zibotentan plus pemetrexed and 36 (55%) received placebo plus pemetrexed. All subjects were Caucasian and the mean (SD) age was 58 [START_REF] Knight | Epigenetic silencing of the endothelin-B receptor gene in nonsmall cell lung cancer[END_REF] and 57 [START_REF] Fizazi | Specific endothelin-A receptor antagonism for the treatment of advanced prostate cancer[END_REF] years in the zibotentan and placebo groups, respectively (Table 1). The majority of patients (83%) in both arms had a WHO performance status of 1 and had adenocarcinoma, reflecting the predominance of this histology type, however, there were a number of patients with undifferentiated or large cell tumor types (Table 1). There were some minor baseline differences between treatment groups including time since diagnosis of advanced disease <1 year (zibotentan 53% and placebo 81%), metastasis in distant lymph nodes and bone (zibotentan 47% and 30%, respectively; placebo 36% and 19%, respectively), habitual smokers (zibotentan 17% and placebo 31%) and previous taxane therapy (zibotentan 40% and placebo 31%). A total of 26 patients (87%) in the zibotentan group and 32 patients (89%) in the placebo group discontinued treatment prior to the data cut-off. After disease progression subsequent cancer therapy was administered to six patients receiving zibotentan (n=1 chemotherapy, n=3 radiotherapy, n=1 radiotherapy plus targeted therapy, n=1 targeted therapy plus immunotherapy) and 11 patients receiving placebo (n=4 chemotherapy, n=2 radiotherapy, n=1 targeted therapy, n=1 osteoclast inhibitor, n=1 chemotherapy plus radiotherapy, n=1 radiotherapy plus chemotherapy, n=1 targeted therapy plus immunotherapy). At data cut-off, eight patients (n=4 in each group) were continuing on study therapy as they were judged to be deriving a clinical benefit by the investigator.

At the data cut-off, a total of 44 deaths had occurred, 20 and 24 in the zibotentan and placebo groups, respectively. Of these, 18 deaths in the zibotentan group and 22 deaths in the placebo group were disease-related, not due to an AE with an outcome of death. There was no significant difference in OS between the zibotentan and placebo treatment groups (HR, 1.13; 80% CI 0.77, 1.67; P=0.69; Figure 1a). The primary event count analysis indicated that there was no difference between the two treatment groups in the number of patients with a disease progression event on or before the MTAV (19 [63%] in the zibotentan group and 26 [72%] in the placebo group) (HR, 0.78; 80% CI 0.52, 1.18; P=0.44). For this analysis, patients were assumed to not have progressed if they were not assessed at the MTAV (five patients in the zibotentan group and two patients in the placebo group were not assessed). Following an additional sensitivity analysis, which assumed that the patients without a MTAV in the zibotentan group had progressed and the patients in the placebo group without a MTAV had not progressed, the HR was 1.26 (80% CI 0.85, 1.87; P=0.46). The median TTP was longer in the zibotentan group (110 days) compared with the placebo group (87 days; Figure 1b).

Investigator assessed RECIST responses were evaluated in 18 patients in the zibotentan group and 30 patients in the placebo group. Two patients in the placebo group had a partial response and 13 patients in each group had stable disease. The remaining patients who were assessed had progressive disease (five patients in the zibotentan group and 15 patients in the placebo group).

For patients receiving once-daily zibotentan 10 mg and pemetrexed, mean (range) exposure was 136 (7-427) and 135 (21-428) days for zibotentan and pemetrexed, respectively. Patients receiving placebo plus pemetrexed had mean (range) exposures of 139 and 137 (21-401) days, respectively. The majority of patients in both treatment groups reported at least one AE (zibotentan 76.7%; placebo 69.4%). The majority of AEs were of CTCAE grade 1 or 2; eight patients (27%) in the zibotentan group and 12 patients (33%) in the placebo group had an AE of CTCAE grade ≥3 (Table 2). The most commonly reported AE in both treatment groups was anemia, which was reported in 23% of patients in the zibotentan group and 25% of patients in the placebo group. Other commonly reported AEs were nausea (17%) and peripheral edema (13%) in the zibotentan group and neutropenia (14%) in the placebo group. Four patients (13%) in the zibotentan group and seven patients (19%) in the placebo group experienced a serious AE, none of which were considered to be related to the study treatment. Four patients, two in each treatment group, had a serious AE that led to death (zibotentan, pancytopenia and dyspnea; placebo, febrile bone marrow aplasia and upper gastrointestinal hemorrhage). Two (7%) patients receiving zibotentan discontinued treatment due to AEs (headache and dyspnea) and three (8%) patients receiving placebo discontinued treatment due to AEs (brain metastasis ['metastases to central nervous system' was reported as an AE], febrile bone marrow aplasia and abdominal pain, anemia, renal failure and upper gastrointestinal hemorrhage).

Discussion

In this study, there was no evidence of efficacy of zibotentan in patients with locally advanced or metastatic NSCLC as indicated by the similar OS and progression results between patients receiving zibotentan plus pemetrexed versus those receiving placebo plus pemetrexed. The additional sensitivity analysis, which assumed that the patients without a MTAV in the zibotentan group had progressed and patients in the placebo group had not progressed demonstrated that the primary analysis was potentially biased in favor of the zibotentan treatment group, confirming the lack of efficacy of zibotentan in this patient population. Some small differences in the baseline characteristics of patients between the two treatment groups were observed, however this was to be expected in a study of this size. Of these imbalances, some characteristics (ex-smoker, habitual smoker, female gender) favored zibotentan whilst others (time since diagnosis of advanced disease <1 year) favored placebo. These differences were not considered to have had an impact on the results of the study.

The majority of trials in advanced NSCLC have, due to time constraints, used TTP as the primary clinical endpoint. However, results from this study have demonstrated that an OS result can be gained in this patient population in a relatively short timeframe. This suggests that time limitation may not be a valid rationale for using TTP as the primary endpoint in trials of patients with advanced NSCLC, and that OS could feasibly be utilized as the primary endpoint in this patient population with, TTP as a secondary endpoint.

No new safety concerns were identified for zibotentan in this study, the AE profile was consistent with previous clinical trials of this agent and other ET A receptor antagonists [START_REF] James | Final safety and efficacy analysis of the specific endothelin A receptor antagonist zibotentan (ZD4054) in patients with metastatic castration-resistant prostate cancer and bone metastases who were pain-free or mildly symptomatic for pain: a double-blind, placebo-controlled, randomized Phase II trial[END_REF][START_REF] Carducci | A phase 3 randomized controlled trial of the efficacy and safety of atrasentan in men with metastatic hormone-refractory prostate cancer[END_REF]. The safety profile of pemetrexed monotherapy was also reflective of earlier experience [START_REF] Russo | Pemetrexed single agent chemotherapy in previously treated patients with locally advanced or metastatic non-small cell lung cancer[END_REF], and the safety profile of the combination regimen was consistent with that of each agent used as a monotherapy with no additional safety concerns identified.

In conclusion, this study does not appear to demonstrate any survival or progression advantage of zibotentan 10 mg in combination with pemetrexed for patients with advanced NSCLC (adenocarcinoma) in the second-line setting. While this could reflect the low number of patients in the study, the absence of any favorable trends do not support further clinical development in this disease setting. The safety profile of zibotentan in this study was consistent with previous studies and no new toxicity or tolerability issues were identified.

Figure legend Fig. 1

 legend1 Figure legend

Table 1 .

 1 Patient characteristics

	Zibotentan (n=30)	Placebo (n=36)

Table 2 .

 2 Adverse events reported by ≥10% patients in either treatment group

		Patients with AEs, n (%)
		Zibotentan plus	Placebo plus
		pemetrexed	pemetrexed
	Adverse events (AEs)	(n=30)	(n=36)
	Any AE	23 (76.7)	25 (69.4)
	Anemia	7 (23.3)	9 (25)
	Nausea	5 (16.7)	2 (5.6)
	Peripheral edema	4 (13.3)	1 (2.8)
	Decreased weight	3 (10)	3 (8.3)
	Rash	3 (10)	1 (2.8)
	Headache	3 (10)	1 (2.8)
	Increased brain natriuretic peptide	3 (10)	0
	Neutropenia	1 (3.3)	5 (13.9)

Acknowledgments

We thank Dr Claire Routley from Mudskipper who provided editorial assistance funded by AstraZeneca.


Pierre Boutillier

Journées Francophones des Langages Applicatifs JFLA12 A relaxation of Coq's guard condition

In a convenient language to handle dependent algebraic data types, this article describes how commutative cuts are used to tackle dependency in pattern matching. It defines a new termination criteria by structural guard condition that allows commutative cuts. Everything exposed scales directly to the Coq proof assistant and describes its implementation. The proof of strong normalisation does not and is still work to do.

Introduction

Proof assistants come with many technical subtleties that any user have to learn before being able to convince a computer of anything non trivial. One example is type checking in Coq where termination checking plays an important role. Termination checking is made up of the application of rules that ensure that one argument of a fixpoint decreases by some measure. These rules are called guard conditions.

At such a point, knowing exactly what algorithm is behind the test is the very minimum expected to be able to polish the code in order to make it fit the requirements. Of course, a description is not enough. The task sometime ends to be very acrobatics while an other technical issue asks for proof in a very precise way that the termination checker does not like. The criteria designed should consequently be compatible with techniques from other part of the system.

The Coq proof assistant is able to check guard on recursive function that rely on over recursive function and allow you to get rid of the empty case while you deal with an non empty list but there is no way to do both at the same time. Here is an example that did not work before our relaxation 1 : fix map2 f n (v1 v2: Vect n) -→ match (v1,v2) with |(Vnil,Vnil) ⇒ Vnil |(Vcons h1 _ t1, Vcons h2 _ t2) ⇒ Vcons (f h1 h2) _ (map2 _ t1 t2) end Rigorously, the situation in Coq is more complicated than the one described here because constructors can take functions as arguments and can be polymorphic. Nevertheless, up to specific conditions on these extra possibilities 2 , termination issues are basically the same in the two systems.

Difficulties gathering together the part of an expressive logic are even bigger when you try to prove its consistency. Actually, proofs made by model exhibition deal with everything all-at-once. In Coq, the section of code to trust is well delimited but optimisation that go further than the proved part of the system are not formally described. This article will neither find a way to make modular proof of consistency nor offer a proof for the whole system but it will describe the exact implementation of a termination checker smart enough to handle programs generated by other part of Coq. The idea is to reduce the term a bit more than 1 Syntax is explained in detail section 1 2 Strict positivity of inductive definitions and forbid of polymorphic recursive arguments what the type preserving reduction would do but it does not depend on other judgements than itself to do so.

Reaching this goal will first require a presentation of the language tackled and its semantic, a survey of methods used elsewhere in the code that impacts termination checking and a exhibition of the termination checking technique used as well as its limitation in its previous introduction.

Afterwards, choice has been made to expose only the final algorithm and not to describe several systems. Anyway, the description is incremental. Consequently, the first part taken alone as well as the two first parts taken alone offers consistent systems by adding structural rules for unwritten constructions.

Language

In typed functional programming languages (e.g. Standard ML [START_REF] Milner | The Definition of Standard ML -Revised[END_REF], Haskell [START_REF]Haskell 98 Language and Libraries: The Revised Report[END_REF], Ocaml [START_REF] Leroy | The Objective Caml system, documentation and user's manual -release 3[END_REF]), it is common to define algebraic data structures such as the unary representation of natural numbers or the unit type. Nat is described by the set of constructors that allow to build elements of the type. For instance, 3 is represented as S (S (S 0)). Elements of these kinds of types are decomposed by pattern matching and fixpoints illustrated in Figure 1.

Type Unit := | () : Unit type Nat := | 0: Nat | S : Nat -→ Nat match t with |0 ⇒ S 0 |S n ⇒ n end fix double x -→ match x with |0 ⇒ 0 |S n ⇒ S (S (double n)) end
Available types in these languages sometime limit the user. To be more expressive, different extensions using dependent types have been studied either in the context of type theory (MLTT [START_REF] Martin-Löf | An intuitionistic theory of types[END_REF], CIC [START_REF] Th | Inductively defined types[END_REF], UTT [START_REF] Luo | Computation and reasoning: a type theory for computer science[END_REF], . . . ) or in the context of programming languages (GADT [START_REF]Haskell wiki on generalized algebraic datatypes[END_REF], Cayenne [START_REF] Augustsson | Cayenne a language with dependent types[END_REF], Dependent ML [START_REF] Xi | Dependent ML an approach to practical programming with dependent types[END_REF]). Recently, some languages even merge both point of views such as Agda [START_REF] Norell | Dependently typed programming in Agda[END_REF] or Epigram [START_REF] Mcbride | Epigram[END_REF]. Here, we consider algebraic data-structures with indices [START_REF] Dybjer | Inductive families[END_REF]. A typical representative of it is the type of list of Boolean values carrying its length:

type Vect : Nat -→ ⋆ := | Vnil : Vect 0 | Vcons : Bool -→ forall (n: Nat), Vect n -→ Vect (S n)
As an example of expressiveness added by the use of indices, we can enforce a list to be non empty and consequently write a function that returns the tail of a list without having to consider the case of an empty list.

fun n (v: Vect (S n)) -→ match v with |Vcons h n t ⇒ t end Two formal approaches are known to allow the type checking of such expressions. The lighter one, derived from [START_REF] Th | Pattern Matching with Dependent Types[END_REF], is used in dependently typed programming language [START_REF] Pientka | Beluga: A framework for programming and reasoning with deductive systems (system description)[END_REF][START_REF] Norell | Dependently typed programming in Agda[END_REF]. Type checking of pattern matching is viewed as a coverage analysis. (This relies on unification.)

The second approach is used in the proof assistant Coq [START_REF] Bertot | Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions[END_REF], whose logic is the Calculus of Inductive Constructions (CIC). It does not depend on unification. The underlying idea is to see pattern-matching as a dependent elimination scheme canonically attached to inductive types. In particular, the predicate on which the scheme is applied is given explicitly to the type-checker as a type annotation. From the computational point of view, the annotation says how the type gets specialised in the branches of a pattern matching [START_REF] Coquand | Inductive definitions and type theory: an introduction (preliminary version)[END_REF].

It leads to see match n as k in Nat return T with |0 ⇒ a |S m ⇒ b end as a particular syntax for case fun k-→T a (fun m -→ b) n where case P is a generic combiner of type P 0 -→ forall (m: Nat), P (S m) -→ forall (k: Nat), P k for objects in Nat. [START_REF] Goguen | Eliminating dependent pattern matching[END_REF] show the two systems have the same theoretical strength except that the first admits Streicher axiom K (or Unicity of Identity Proof) as a reduction rule. In any other situation, any dependent pattern-matching typable in the first system can be simulated in the second system by inserting equality constraints in type annotations.

Nevertheless, Goguen, McBride and McKinna

It is in fact not mandatory to rely on equality constraints. In many cases, a symbolic evaluation can be obtained by inserting appropriate pattern matching in the type annotation itself [START_REF] Chlipala | An introduction to programming and proving with dependent types in Coq[END_REF][START_REF] Boutillier | Cloisonnement des contenus calculatoire et logique du filtrage dépendant en théorie des types et application aux coupures commutatives[END_REF]

match v as v' in Vect n' return     match n' with |0 ⇒ Unit |S n0 ⇒ Vect n0 end     with |Vnil ⇒ () |Vcons h m t ⇒ t end
Taking advantages of how the coverage analysis is constrained by patterns in the first approach, we introduce a more compact notation written "as x in I -→ p return T" where a list of linear patterns ( -→ p ) over the type of the matched term, a name (x) to abstract the matched term, a type (T) abstracted over the first items.

Outside of the match, x is the actual term (v in the example) and -→ p are matched against the arguments of the type of v resulting in a substitution (here n' is instantiated by m). Inside, constructors whose type does not follow the pattern (below Vnil) are impossible branches. For handling valid constructors (Vcons there), pattern variables are filled with the relevant term. As a result, the complete definition of tail is:

match v as v' in Vect (S n') return Vect n' with |Vnil |Vcons h m t ⇒ t end
This match represents the application of a customised scheme of type (forall h m t, P m (Vcons h m t)) -→ forall n (v: Vect (S n)), P n v Throughout this paper, we consider a tiny language which emphasises the specific subtleties of dependent pattern matching in Coq. It deals with term dependency but neither type dependency nor polymorphism and is similarly expressive as λΠ or LF.

The syntax of this language is split into five categories:

Linear patterns (p) first are required for pattern matching return clause. Their linearity is not syntactically enforced but is required to be able to encode our return clause by a match when pattern matching is allowed in types.

Algebraic kinds (K) are either the sort ⋆ or the dependent product of an algebraic type and a K.

Types (T ) are algebraic types and dependent products of an algebraic type and a type.

Terms (t) are those Church-style lambda calculus extended with recursive definitions, constructors and pattern matching.

Contexts (∆) are made of algebraic types definitions and abbreviations for terms.

p ::= x | C -→ p K ::= ⋆ | forall (x: I -→ t ), K T ::= I -→ t | forall (x: I -→ t ), T t ::= a | x | t t | fun x: I -→ t -→t | fix T f -→ d x-→t | C | match t as x in I -→ p return T with . . . |C -→ y ⇒ t . . . end ∆ ::= ε | ∆; let a = t: T | ∆; type I : K := . . . |C: T . . .
For readability we do not write the return clause, the type of variables or the kinds in type definitions when they are obvious in context. Similarly, we use names for variables but the issues with α-conversions are left implicit. Because a constructor cannot have functions as arguments, our algebraic types enter the category of strictly positive families [START_REF] Morris | Constructing strictly positive families[END_REF] and can be seen as inductive types.

If let a = t: T occurs in ∆, ∆(a) denotes t and ∆[a] denotes T.

As in standard type theories, type checking is up to evaluation which is defined by the following standard rewriting rules applied anywhere in the term and not only at toplevel:

δ reduction a → ∆(a) β reduction (fun x: T -→ u) v → u[v/x] ι reduction match C i -→ u as x in I -→ p return T with . . . |C j -→ x ⇒ v j . . . end → v i ---→ [u/x] µ reduction (fix T f -→ d x -→ u) -→ t (C -→ v ) → u[C -→ v /x] --→ [t/d][fix T f -→ d x -→ u/f]
Further than the implicit we make here for readability reason, dependent pattern matching with explicit type annotation syntax is heavy and so is especially the Coq internal syntax. For this reason, the user can employ a lighter language, and, pattern matching thus given is compiled in the inner syntax. This compiler relies on techniques that we will explain in the next section, before exhibiting a solution to handle them.

Dependent pattern matching

In dependent settings, two facts complicate pattern matching when compared to the simply-typed case: the types of other objects in the context depend of matched term types and the type of a matched term is not necessarily the one built by constructors of the corresponding inductive type.

Here is a survey of how pattern matching is handled in a system based on induction scheme point of view.

When matching the type of the constructor of a branch against the pattern over type given in the in clause, three cases can happen:

• The type matches the given pattern and is able to provide a correct answer according to pattern variable instantiation. E.g. Vcons in Tail.

• The type is explicitly out of that pattern because two different constructors clash. E.g. Vnil in example. In this case, the branch does not answer anything because it cannot correspond to the matched term.

• There is a third case where the given pattern is more precise than the type of the constructor. This would happen, for instance, if we add an extra constructor Vbig to Vect of type forall n, Vect (double n) because Double n can be either 0 or S ? depending on n value. This situation is forbidden by our typing rules and should be bypassed by weakening the pattern. With that extra constructor, Nothing better can be done than

fun v: Vect S k -→ match v as x in Vect m return P m x with |Vnil ⇒ . . . |Vcons n0 v0 ⇒ . . . |Vbig n0 ⇒ . . . end
Discriminating between these cases is done by pattern matching (when allowed in types) using the pattern provided in pattern matching return type clause.

Maintaining the link between types of a matched term and the rest of the context is done by β-expansion around the match. Interleaving β and ι cuts are called Commutative cuts and plays a crucial role in our development.

In a simply-typed setting, (match u with . . . |C -→ x ⇒ fun y -→ f y . . . end) t can be rewritten in match u with . . . |C -→ x ⇒ f t . . . end and vise-versa. In a dependent setting t and y may not have exactly the same type. So, it must not be reduced.

For example, take two vectors a and b of the same length. If you match over a, in branches, its type will be the one of the constructor. Your only possibility to keep the link between the two types is to put b somewhere in the return clause like

(match a as v in Vect n return (Vect n -→ [. . . ]) with |Vnil ⇒ fun b': Vect 0 -→ [. . . ] |Vcons h m t ⇒ fun b': Vect (S m) -→ [. . . ] end) b
Here is a major reason why commutative cuts are interesting to tackle in the type checker. Coq pattern matching compilation process is based on this transformation but the generated term is refused afterwards by the type checker as soon as recursion is involved.

To be complete, a third smart technique [START_REF] Sozeau | Un environnement pour la programmation avec types dépendants[END_REF] works wonderfully. Generalising equality between types arguments of the matched term and the one of constructors allows to lose no information.

Equality is the special algebraic type that says that everything is equal to itself: and eq stores everything.

On the one hand, such terms need dependent equality and consequently K axiom in the general case. On the other hand, proofs over equality block computation in open terms evaluation context, that is used in proofs.

To figure out what we mean on examples, take plus over Nat defined by induction on the first argument, then n + S m = S n + m has to be proved by induction. As a result, when a pattern matching over a Vect type-checks in the Vcons case thanks to this proof, the ι then βreduction of (match Vcons h m t with . . . end (eq_refl (S m)) works but you are left with a term (proof_of_plus_Smn_nSm(t)) that does not reduce.

Hopefully, for linear patterns over constructors, which is a common circumstance, everything can be done by pattern matching in the return clause and no explicit equality is required.

Structural guard condition

Going back to reduction rules page 4, asking for arguments that begin with a constructor in the rule about fixpoint unfolding is essential. Otherwise, reducing open terms may lead to infinite loops. For instance, we would have the following chain of reduction:

double x → match x with |0 ⇒ 0 |S n ⇒ S (S (double n)) end → match x with |0 ⇒ 0 |S n ⇒ S (S (match n with |0 ⇒ 0 |S n' ⇒ S (S (double n')) end)) end →
Yet we need termination for decidability of comparison. Sized types (see e.g. [START_REF] Abel | A predicative analysis of structural recursion[END_REF][START_REF] Abel | Termination checking with types[END_REF]) and structural guard condition (see e.g. [START_REF] Giménez | Structural recursive definitions in type theory[END_REF]) are two kinds of criteria ensuring termination. We focus on the last one which means that the number of constructors of a fixpoint argument must strictly decrease at each recursive call. For instance, double is guarded because the argument of the recursive call has one less constructor than its parent.

Taken alone, the criterion is too limited. To be convinced, consider figure 2. div2 is correct but we will not realise it if app_pred is not unfolded and the obtained expression is not reduced to the last expression which is structurally guarded. In other words, some β-ι-δ-reduction steps may be needed to reveal that recursive calls are guarded. In Coq, since the very beginning of CIC implementation, a structural guard condition is used over terms in head normal form to ensure fixpoint termination. Theoretically, a structural guard condition is limited compared to sized types. However, it is challenging to formulate a more expressive approach that can scale up to large examples. Nevertheless, it has three main practical drawbacks that we are going to address: 1. It allows not strictly (but weakly) terminating definitions such as fix f x -→ (fun _ -→ S 0) (f 0) , that loop if you eagerly rewrite the arguments but are correct after performing β-reduction steps that erase some subterms.

let app_pred f x = match x with |0 ⇒ 0 |S n ⇒ f n end fix div2 x -→ match x with |0 ⇒ 0 |S n ⇒ app_pred div2 n end fix div2 x -→ match x with |0 ⇒ 0 |S n ⇒ match n with |0 ⇒ 0 |S n' ⇒ div2 n' end end

Commutative cuts (defined page 5) are not handled.

As seen section 2, in a dependent setting, such a reduction rule does not preserve the type and match v in Vect (S k) return Vect k -→ Vect k with |Vnil ⇒ 0 |Vcons h n t ⇒ fun w: Vect n -→ w end v2 must not be reduced to match v in Vect (S k) return Vect k with |Vnil ⇒ 0 v2 |Vcons h n t ⇒ v2 end by evaluation.

Though they are safe for termination, only an ad-hoc hack allows some of them in Coq version 8.4. They are not properly supported and this is the motivation of the current work.

3. Commutative cuts can also involve the name of the fixpoint itself, as in fix g n -→ (match n with |0 ⇒ ()|S x ⇒ fun f -→ f x end) g that should be considered guarded.

Though this example is artificial, it does correspond to a common Coq failure which is not understood by users when writing tactic-defined fixpoints.

A guard condition for our system that scales up directly to Coq will now be described incrementally. First, we will describe rules that we always find when testing structural guards. Afterwards, we will add judgements to simulate ι and µ. In the end, we will show how the remaining rules end to build our own reduction machine for β, and exhibit a more permissive guard condition that ensures strong normalisation.

Basis of structural guard condition

To begin with, this part describes the rules of fundamental cases of a structural guard condition. After evaluation of the fixpoint body, these rules are sufficient. Consequently, it draws a correct picture of what was done in Coq up to version 8.3. Our added value will come in the next sections.

To check a structural guard condition, two kinds of judgements are needed. The first one written Γ ⊢ f t ◮ a gives the specification of subterm of a term t using a specification of subterm a , for now, either < which stands for subterm or ≤ for recursive argument or ⊥ for anything else, an environment Γ to give the specification of subterm of each free variable of t and the name f of the checked fixpoint.

Then, the main judgement guarded definition, written Γ ⊢ f t # for terms and Γ ⊢ f T # for types, expresses that every recursive call to f is guarded in t or T respectively.

Concretely, ensuring that the recursive call to f is guarded in the definition fix T f -→ d x -→ t reduces to finding a derivation whose conclusion is ---→ d ◮ ⊥, x ◮≤ ⊢ f t # using the following rules:

• An applied constructor or inductive type is guarded if every of its arguments is guarded.

• A recursive call is guarded iff its last argument has the specification < and all its arguments are guarded.

• A variable is guarded and has the specification it has in Γ.

• A dependent product, as any type, is never a subterm. Hence there is neither a rule IndSpec nor ProdSpec one.

Guard check consists in recursive calls.

• More interesting, in the case of match, we define a strengthen operation ( ␣ ) on specifications of subterm by < = ≤ = < and ⊥ = ⊥. We look for the specification of the matched term and we affect its strength version to each variable of the pattern.

Of course, all pattern variables are not allowed as recursive arguments but typing handles it for us.

• In addition, to get the specification of subterm of a match expression, we look for the specification of every branch and concatenate them.

Consequently, we introduce an operation Π over specifications where ⊥ is a zero, and < a unit.

Constructor . . . Γ ⊢ f t # . . . Γ ⊢ f C . . . t . . . # Ind . . . Γ ⊢ f t # . . . Γ ⊢ f I . . . t . . . # Fix . . . Γ ⊢ f u # . . . Γ ⊢ f t # Γ ⊢ f t ◮ < Γ ⊢ f f -→ u t # VarSpec Γ ⊢ f x ◮ Γ(x) Var x = f Γ ⊢ f x # Prod . . . Γ ⊢ f t # . . . Γ ⊢ f T # Γ ⊢ f forall (x: I -→ t ), T # Match Γ, -------→ y ∈ p ◮ ⊥, z ◮ ⊥ ⊢ f T # Γ ⊢ f t ◮ a . . . Γ, -----→ x ◮ a ⊢ f b i # . . . Γ ⊢ f match t as z in I -→ p return T with . . . |C i -→ x ⇒ b i . . . end # MatchSpec Γ ⊢ f t ◮ a . . . Γ, -----→ x ◮ a ⊢ f u i ◮ a i . . . i a i = b Γ ⊢ f match t with . . . |C i -→ x ⇒ u i . . . end ◮ b FixSpec Γ ⊢ f v ◮ b Γ, g ◮ ⊥, ---→ d ◮ ⊥, x ◮ b ⊢ f u ◮ a Γ ⊢ f fix T ′ g -→ d x-→u -→ t v ◮ a
Standard rule of a syntactic structural guard condition

• While looking for the recursive call of f in the body of g, we can affect the specification of v to x since a recursive argument length can only decrease. Remark that guard checks are made one after the other and g correctness is not mixed with the one of f .

Be more careful with inductive eliminators

In the previous implementation, a fixpoint's body was reduce to its normal form before being checked. rules presented until now were consequently enough. Cuts are now handled manually. A lot of bureaucracy is added but, as we will see in Section 6, simulating reduction by ourselves increases the power of the system. To begin with, we tackle ι and µ reductions. Of course, an applied constructor is not and shall not be a subterm in order to keep things finite. Relaxing the condition is incompatible with the fact that a fixpoint unfolds itself if its argument starts by a constructor (see page 6).

But an applied constructor is not a term like the others. Imagine that you end with

match S n with |0 ⇒ evil |S m ⇒ good end
You would be glad to mark evil as dead code and only look for the good branch.

For this purpose, rules involving inductive constructions become more than strict recursive calls. Before that, the specification of subterm data-structure becomes recursive and is extended with a notion of constructor specification:

Constructor C whose arguments gives the specifications -→ a of the arguments of the constructor.

In the same time, Π has to be extended as expected. For anything but the exact same constructor

C, C -→ a • s = ⊥ and C -→ a • C -→ b = C --→ a • b
Then, judgements have the material to reduce ι-µ cuts. Actually, the applied constructor C i is and is the only kind of term to be a term of specification C i . As a result, substituting a pattern-matching over a term with specification C i -→ a by its C i branch or a fixpoint whose argument's specification has the same structure by its body are exactly the simulation of the reduction rules in the judgement.

ConstructorSpec . . . Γ ⊢ f t ◮ a . . . Γ ⊢ f C -→ t ◮ C -→ a Iota Γ ⊢ f u ◮ C i . . . a . . . Γ, . . . x ◮ a . . . ⊢ f t Ci # . . . Γ, . . . x ◮< . . . ⊢ f t Cj # . . . Γ ⊢ f match u with . . . |C -→ x ⇒ t . . . end # Fix' Γ ⊢ f v ◮ C -→ s . . . Γ ⊢ f u ◮ b . . . Γ, ---→ d ◮ b, x ◮ C -→ s ⊢ f t # Γ ⊢ f f -→ u v # for fix T f -→ d x -→ t

The machinery

We now focus on the way to check guard up to β-equivalence. We achieve β-reduction through the use of ad-hoc rules in order allow more definition. The judgements are enriched as it is commonly done in an abstract machine of a substitution σ where "values" of variable will be stored if necessary for future check. We will explain what we mean at the end of the section.

a stack s to store arguments between the moment where we tackle the application and the related lambda. Actually, there can be a pattern matching between application and the abstraction. This is the exact point where commutative cuts are applied.

By values and arguments we actually mean closures, to avoid problems with variable capture. Syntax of full judgements are

(Γ, σ) ⊢ f s | t ◮ a (Γ, σ) ⊢ f s | t #
Rules given until here are the same except that they carry s and σ without any other modification.

Remaining behaviours to explain are:

• Application feeds the stack. This way, check of arguments are delayed to time of use.

• Consequently, a defined variable must call the check of its value.

• A lambda transfers from a non empty stack to the substitution.

• If the stack is empty, a variable is declared instead of being defined.

If we stop here, the non terminating example in call by value (item 1 p.6) is allowed again! That is why all computation over right part of application cannot be completely delayed. The rule sanity accomplishes this. It hides the control of v in a new variant of check fixpoint

App (Γ, σ) ⊢ f (Γ, σ, v) :: s | u # sanity (Γ, σ) ⊢ f s | u v # Def σ(y) = (Γ ′ , σ ′ , t) (Γ ′ , σ ′ ) ⊢ f s | t # (Γ, σ) ⊢ f s | y # Pop (Γ, σ) ⊢ f ∅ | c ◮ a (Γ, x ◮ a, σ, x → c) ⊢ f s | u # (Γ, σ) ⊢ f c :: s | fun x-→u # Lam (Γ, x ◮ ⊥, σ, x) ⊢ f ∅ | t # (Γ, σ) ⊢ f ∅ | fun x: T -→t # Abstract machine embedded in rule set drawn (Γ, σ) ⊢ f s | v ≈ where
• a new specification of subterm called Neutral and written ⋄ is added.

• Lam rule is modified to add to Γ a ⋄ instead of a ⊥ • Fix asks for recursive call to be < or ⋄.

Informally, it means to be "safely reducible in an empty context".

Moreover, the weak guard condition where every recursive call specification is strict subterm "<" implies the strong guard. This way, while checking sanity in App, we could implement the optimisation were a strictly guarded argument is declared and not defined. It is consequently checked only once even if it is used more than once.

StrongApp

(Γ, σ) ⊢ f ∅ | v # (Γ, σ) ⊢ f ␣ :: s | u # (Γ, σ) ⊢ f s | u v #
The end of our journey is now reached. By making the stack explicit, it can be given to the branches of a match and simulate commutative cuts.

Match

. . . (Γ, -----→ x ◮ a , σ, -→ x ) ⊢ f s | b i # . . . (Γ, σ) ⊢ f ∅ | t ◮ a (Γ, -------→ y ∈ p ◮ ⊥, z ◮ ⊥, σ, ---→ y ∈ p, z) ⊢ f ∅ | T # (Γ, σ) ⊢ f s | match t as z in I -→ p return T with . . . |C i -→ x ⇒ b i . . . end #

Typing

At last, termination checking is part of the type checking process. In order to get the general picture, we present its rules under the hypothesis that _ = βδιµ _ stands for being equals modulo evaluation and that (parallel) substitution deals correctly with α-conversion:

• For terms:

Def (∆; Γ) ⊢ a : ∆[a] Var (∆; Γ) ⊢ x : Γ(x) App (∆; Γ) ⊢ u : forall (x: I -→ t ), T (∆; Γ) ⊢ v : I -→ t (∆; Γ) ⊢ u v : T [v/x] Lam (∆; Γ, x: I -→ t ) ⊢ u : T (∆; Γ) ⊢ I -→ t ∈ ⋆ (∆; Γ) ⊢ (fun x: I -→ t -→u) : forall (x: I -→ t ), T Constr (∆; Γ) ⊢ C : ∆(C) Match ∆(I) = forall --→ w: S, ⋆ ∆ ⊢ -→ S ∋ -→ p ⊲ -→ L (∆; Γ) ⊢ forall -→ L , T ∈ ⋆ (∆; Γ) ⊢ t : I -→ a . . . ∆(C) = forall --→ x: U , I -→ b (∆; Γ, --→ x: U ) ⊢ u : T [ -→ b / -→ p ][C -→ x /z] . . . (∆; Γ) ⊢ match t as z in I -→ p return T with . . . |C -→ x ⇒ u . . . end : T [ -→ a / -→ p ][t/z] Fix (∆; Γ, f : T ) ⊢ fun . . . d . . . x-→t : T ( ---→ d ◮ ⊥, x ◮≤, ∆) ⊢ f ∅ | t # (∆; Γ) ⊢ (fix T f -→ d x-→t) : T
Two notations are not standard. First, in the fix case, types of d and x must be extracted from T but writing it explicitly would only obfuscate the rule.

More important is the pattern substitution in the match rule. If the pattern p is a variable, it is the common substitution. If the pattern is a constructor and the term begins by the same constructor, it is recursive calls. If the constructor of b is different, u if exists has to be well typed in an arbitrary type. This is the impossible branch case. If p starts with a constructor and b is not an applied constructor then type checking fails (see p.5).

• For types and kinds:

Ind ∆(I) = forall --→ x: T , ⋆ . . . (∆; Γ) ⊢ t i : T i [t j /x j ] 1...i . . . (∆; Γ) ⊢ I -→ t ∈ ⋆ Conv S = βδιµ T (∆; Γ) ⊢ S ∈ ⋆ (∆; Γ) ⊢ T ∈ ⋆ Prod (∆; Γ) ⊢ I -→ t ∈ ⋆ (∆; Γ, x: I -→ t ) ⊢ T ∈ ⋆ (

Conclusion

Ensuring termination raises a lot of technical issues. We have shown here how to take better advantage of one elementary criterion: the syntactic structural guard condition.

The main advantage of the presented work is to remove situations where the automatic part of proof term generation ends to functions refused by the Coq termination checker.

We have exhibited that enhancing the regular syntactic guard condition judgement with one ad-hoc reduction machine is the key to get a more powerful and stand alone rules set.

Formal correctness must be the next step. The two known techniques to do so are reducibility candidate and relative soundness by encoding. Nevertheless, these proofs are system specific. A result for our playground is just the beginning of the Coq case, and the CIC is very heavy to manipulate at once. An ideal proof that scales up would consequently say: suppose that a well typed and guarded term has no infinite β reduction chain then it has no β-ι-µ reduction chain.

Judgements have been defined in order to ensure that :

• ι naturally "consumes" a constructor and we do not deal with higher order in constructor's argument so no β-ι infinite chain is possible.

• A guarded term has no infinite ι-µ-reduction chain

• Guard and typing are stable by β-ι-µ reduction. Consequently, a well typed guarded term never evaluates to a term that has an infinite β-ι reduction chain or a ι-µ reduction chain.

A statement like "a β-ι-µ infinite chain implies an β-ι infinite chain or a ι-µ one" would complete syntactically our proof but is absolutely not straight forward.

More deeply, our algorithmic complexity is worse than typed base criteria and information is still lost when a fixpoint has more than one argument that decrease. Only one is taken into account and can be used in mutual fixpoints definition.

Bibliographie

Figure 1 :

 1 Figure 1: Examples of the language syntax

type

  Eq: Nat -→ Nat -→ ⋆ |eq_refl: forall (n: Nat), Eq n n If u has type I t, do match u as z in I x return x = t -→ [. . . ] with . . . |C -→ y ⇒ fun eq -→ [. . . ] . . . end (eq_refl t)

Figure 2 :

 2 Figure 2: A definition structurally guarded only unfolded

Figure 3 :

 3 Figure 3: ι-µ simulation without explicit reductions

Figure 4 :

 4 Figure 4: Commutative cuts in syntactic guard condition

  ∆; Γ) ⊢ forall (x: ∅) ⊢ t : T ∆; let a = t: T ⊣ Type ∆ ⊣ (∆; ∅) ⊢ K . . . T = forall _, I_(∆; type I: K; ∅) ⊢ T ∈ ⋆ . . . ∆; type I: K:= . . . C: T . . . ⊣ • And for patterns Nil ∆ ⊢ ∅ ∋ ∅ ⊲ ∅ ∋ x :: -→ p ⊲ (x: U ) ::