Valentine Wakelam
email: wakelam@obs.u-bordeaux1.fr

Jean-Christophe Loison

Eric Herbst

Dahbia Talbi

Dongui Quan

Françoise Caralp

J.-C Loison

A sensitivity study of the neutral-neutral reactions C + C3 and C + C5 in cold dense interstellar clouds

Keywords:

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The chemistry in astrochemical models is driven by large networks including thousands of reactions with poorly determined rate coefficients. For several years now, astrochemists have been working on the quantification of model uncertainties caused by uncertainties in rate coefficients. Using similar methods but different models and networks, Vasyunin et al. (2004Vasyunin et al. ( , 2008) ) and Wakelam et al. (2005Wakelam et al. ( , 2006a) ) have studied the error propagation of such uncertainties in various environments such as dense clouds, diffuse gas, hot cores, and protoplanetary disks. This approach to quantify the model error is useful quantitatively comparing calculated and observed molecular abundances. In addition to this important aspect, these authors have developed sensitivity methods for identifying those reactions in complete networks that might be worth studying theoretically or experimentally because model results are very sensitive to their rate coefficients and uncertainties. Identifying these reactions is critical because detailed experimental or theoretical studies of a single reaction, especially at low interstellar temperatures, can take years. Guiding chemists and physicist as to which reactions are the most important for them to study is an efficient method for reducing error in chemical models.

"Important" reactions can be defined in several ways. First, one can define important reactions for specific species; such reactions strongly affect the abundances of individual species through changes in their rate coefficients for formation or destruction processes. One must be precise with this definition, because even though some reactions dominate the formation or destruction of certain species, changes in their rate coefficients within certain ranges can have little effect. [START_REF] Quan | [END_REF], for instance, showed that although molecular oxygen is formed by the reaction O + OH → O 2 + H, the rate coefficient of this reaction can be changed by several orders of magnitude without affecting the O 2 abundance significantly. The reason is that the reaction is also the main route of OH destruction. When the rate coefficient is decreased, the OH abundance increases so that the rate of O 2 formation stays constant. As a counterexample, the reaction C + C 3 → C 4 + hν is very important to the abundance of CO, as will be discussed below. Secondly, "important" reactions can be defined through the number of molecular abundances they influence strongly. As an example, the cosmic-ray ionization of molecular hydrogen is important for almost all of the species in the chemical models of dense interstellar clouds (Wakelam et al. 2006b;Vasyunin et al. 2008).

In this paper, we present a complete approach to improving chemical models through identifying sensitive reactions followed by an increase in our knowledge of their rate coefficients via theoretical means, and using the newly revised rate coeffi-cients in model predictions. We direct our focus on two reactions: the radiative association reaction between C and C 3 and the neutral-neutral reaction C + C 5 . We start, in Section 2, with a discussion of the methods used for our sensitivity analyses and the determination of the important reactions in cold dense clouds. The theoretical study of the C + C 3 and C + C 5 rate coefficients is presented in Section 3 and the impact of new rate coefficients on the model predictions are studied in Section 4. Following our conclusion, an Appendix on other reactions of the C + C n class is presented.

Selection of important reactions

In order to identify important reactions of both classes, we use two different sensitivity methods and compare the results of the two. Each sensitivity method is based on linear correlations but in the first one, only one reaction is modified at a time whereas in the second method all reactions are modified at the same time. The first one, which we will call "individual perturbations", is simply based on the study of the linear effect of individual rate coefficient perturbations on molecular abundances. We have already used this method previously (Wakelam et al. 2005(Wakelam et al. , 2006a)). In the second method, we compute Pearson correlation coefficients.

Chemical model

To represent cold dark clouds, we use a pseudo-time-dependent gas-phase model, which computes abundances as a function of time for a temperature of 10 K, a total hydrogen density of 2×10 4 cm -3 and a visual extinction of 10. The model is known as nahoon (http : //www.obs.u-bordeaux1.fr/amor/VWakelam/). For comparison with previous studies, the elemental abundances are the O-rich low-metal elemental abundances (see table 1 in Wakelam & Herbst 2008). For this work, we used an older version of the osu database (osu.2003) since one goal of this work is to show how we corrected a mistake in this database. We focus on the specific time of 10 5 yr, since this so-called "early time" normally results in the best agreement between calculated abundances and observations (Smith et al. 2004).

Sensitivity Methods

The idea of the individual perturbation approach is to look at the individual effect of each reaction. With a network of N reactions, we run the model N times and modify only one rate coefficient each run. One then obtains the chemical evolution of the fractional abundance: X i j (t) for each species j and run i . Note that the index i can stand for the run or the reaction with varied rate coefficient. We then compare the abundance of each species X i j (t) with the standard abundance X re f j (t) obtained without changing the rate coefficients. In our previous uses of this approach to select important reactions for hot-core (Wakelam et al. 2005) and dense-cloud (Wakelam et al. 2006a) chemistry, we multiplied each rate coefficient by its uncertainty factor. This approach assumes that the real uncertainty in the rate coefficient is not much larger than the considered uncertainty factor, which may not be true. Indeed, as we will show later, this approach can miss important reactions if the real rate coefficient error is much larger than the uncertainty factor. For this reason, here we multiply each rate coefficient by the same factor of two. This factor is currently the default uncertainty used for most classes of reactions in current reaction networks (http://www.udfa.net/; http://www.physics.ohio-state.edu/˜eric/research.html).

To quantify the effect of these variations in the reaction rate coefficients on the abundances, we compute a parameter labeled R i j (t) for each species and each reaction, where

R i j (t) = (X i j (t) -X re f j (t)) X re f j (t)
.

(1)

As an example, a value of R i j (t) = 0.2 tells us that the multiplication of the reaction i by a factor of two increases the abundance of species j by 20%. We also did these calculations by multiplying the rate coefficients by a factor of 10 or dividing them by 2 but the list of important reactions is rather the same as for the case presented here.

The second method is based on linear correlations but is less time-consuming. Here we run about 2000 different models l, randomly varying all rate coefficients within an uncertainty range of a factor of two, with both increases and decreases considered. We then compute Pearson correlation coefficients for each species j and each reaction i using the following relation:

P i j (t) = l (X l j (t) -X j (t))(k l i -ki ) ( l (X l j (t) -X j (t)) 2 l (k l i -ki ) 2 , ( 2
)
where X j (t) and ki are the mean values of the abundance for species j and the rate coefficient i. Pearson correlation coefficients indicate the strength and direction of a linear relationship between two variables by dividing the covariance of the two variables by the products of their standard deviations (see for instance [START_REF] Press | Numerical Recipes[END_REF].

Results of sensitivity calculations

In this section, we show the results of both sensitivity methods to determine the most important reactions for the abundances of selected individual species and to determine the reactions that influence the abundances of the largest numbers of species.

In Table 1, we show the most important reactions for the species CO, O 2 , C 4 H and HC 3 N at an integrated time of 10 5 yr using the individual perturbation (R) and the correlation coefficient (P) methods. In tables 2 and 3, we list the reactions that influence the most species using R and P, respectively, as a criterion. For each reaction, we count the number of species for which R or P is either larger than 0.1 or smaller than -0.1.

A glance at Table 1 shows that the important reactions governing the abundances of individual species are generally similar for both methods. There are two main surprises, however. First, for the case of CO, the values of R are much smaller than those for P. Presumably, the explanation for this dichotomy is that most of the carbon goes into CO at that time. As a result, a change in the rate coefficients does not change the CO abundance, which is then controlled by the elemental abundance of C. This effect also explains the small uncertainty in the CO abundance found by Wakelam et al. (2006a). Secondly, the most unexpected reactions, because they seem so unrelated to the listed species, are those between C and C 3 and between C and C 5 . Note that the latter was assumed, erroneously, in osu.2003 to be a radiative association (see below). The importance of the C + C 3 association seems to be associated with the fact that C 3 acts as a catalyst to convert C and O into CO via the association reaction between C and C 3 followed by

O + C 4 -→ CO + C 3 , (3)
Table 1. Most important reactions for selected species at 10 5 yr.

Species Reaction

R P CO C + C 3 -→ C 4 + hν 0.009 0.5 H 2 + ζ -→ H + 2 + e - 0.004 0.3 C + C 5 -→ C 6 + hν 0.005 0.4 O 2 H 2 + ζ -→ H + 2 + e - 1.2 0.7 C + C 3 -→ C 4 + hν 0.3 0.2 H + 3 + CO -→ HCO + + H 2 -0.3 -0.2 C + C 5 -→ C 6 + hν 0.2 0.2 C + O 2 -→ CO + O -0.2 -0.2 C 4 H O + C 4 H -→ C 3 H + CO -0.7 -0.2 He + ζ -→ He + + e - 0.3 0.2 C + C 5 -→ C 6 -0.2 -0.07 C + C 3 -→ C 4 -0.2 -0.08 C 4 H + 2 + e --→ C 4 H + H 0.2 0.09 HC 3 N He + ζ -→ He + + e-- -0.5 -0.5 H 2 + ζ -→ H + 2 + e - 0.5 0.5 H 3 O + + e --→ OH + H + H -0.2 -0.1 H 3 O + + e --→ H 2 O + H 0.1 0.2 H + 3 + C -→ CH + + H 2 0.1 0.2 C + + H 2 -→ CH + 2 0.1 0.2 C + + HC 3 N -→ C 3 H + + CN -0.1 -0.1 CH + 3 + H 2 -→ CH + 5 0.1 0.1 C + C 3 -→ C 4 -0.1 -0.09
Table 2. Reactions influencing the most species at 10 5 yr using

R Reaction % of species H 2 + ζ -→ H + 2 + e - 53 H + 3 + C -→ CH + + H 2 31 He + ζ -→ He + + e - 31 C + + H 2 -→ CH + 2 29 H 3 O + + e --→ H 2 O + H 26 HCO + + C -→ CH + + CO 24 CH + 3 + H 2 -→ CH + 5 22 HCO + + C 3 -→ C 3 H + + CO 16 C + C 3 -→ C 4 15 H + 3 + CO -→ HCO + + H 2 14 C + 3 + e --→ C 2 + C 13 H 3 O + + e --→ OH + H + H 13 CH + 5 + CO -→ HCO + + CH 4 13
which regenerates the C 3 . A similar cycle happens with C 5 if it undergoes radiative association with C.

Considering the number of species affected, the most important reactions determined by both methods are quite similar although the order of importance can differ. As already noticed by several authors (Wakelam et al. 2006a;Vasyunin et al. 2004;Wakelam et al. 2006b;Vasyunin et al. 2008), the H 2 and He ionization rates by cosmic-rays appear to be important for many species since they are at the origin of formation and destruction pathways. Most of the other important reactions are ion-neutral normal and associative reactions and dissociative recombination reactions, such as those for H 3 O + with electrons. Among the important reactions,

C + + H 2 -→ CH + 2 , CH + 3 + H 2 -→ CH + 5 , H + 3 + C -→ CH + + H 2 , H + 3 + CO -→ HCO + + H 2 , H + 3 + O -→ OH + + H 2
have also been identified as important reactions for disk chemistry by Vasyunin et al. (2008). Most of these reactions are at the start of a chain of reactions that builds up hydrocarbons. It should be emphasized that our sensitivity methods need not tell us the details of the pathway of reaction cycles. If, for example, a destruction reaction leads to a loop of Table 3. Reactions influencing the most species at 10 5 yr using

P Reaction % of species H 2 + ζ -→ H + 2 + e - 86 He + ζ -→ He + + e - 82 H + 3 + O -→ OH + + H 2 54 H 3 O + + e --→ OH + H + H 48 H + 3 + CO -→ HCO + + H 2 43 C + C 5 -→ C 6 41 C + C 3 -→ C 4 41 C + + H 2 -→ CH + 2 41 H 3 O + + e --→ H 2 O + H 37 HCO + + e --→ CO + H 34 CH + 3 + H 2 -→ CH + 5 33 H + 3 + C -→ CH + + H 2 32 HCO + + C -→ CH + + CO 24
subsequent reactions that reforms the molecule being destroyed with some non-zero efficiency, the sensitivity method might just decide that the initial destruction reaction is less important, at least for the species being destroyed. The problem of enhanced molecular abundances due to artificial loops has been minimized whenever possible in the construction of the network by including a number of different product channels. For example, if the major destruction route of a neutral species leads to a protonated ion, and the major destruction route of the ion is dissociative recombination to form neutral molecules, the channel that loops back to the original neutral species plus a hydrogen atom will not be assumed to occur on more than 50% of the recombination reactions (unless, as is highly unusual, experimental results tell us the contrary). Let us look at the important reactions causing the destruction of HC 3 N in Table 1. One of them is the rather direct destruction via C + ions. The products of this reaction do not lead back to HC 3 N in any direct fashion. If, on the other hand, there were a charge exchange reaction to form C 3 HN + , and this ion were hydrogenated by reaction with H2 to form, C 3 H 2 N + + H, the hydrogenated ion could react with electrons to form HC 3 N + H. In the network, however, the probability of this neutral product channel is set to approximately 50% so that the loop is not particularly efficient.

The only neutral-neutral reactions that seem important for many species in Tables 2 and3 are the (presumed) radiative associative reactions C + C 3 and C + C 5 . The rate coefficients for these reactions used in osu.2003 are 10 -10 and 10 -11 cm 3 s -1 based on Smith et al. (2004), without temperature dependence. These reactions have been looked at again by Smith et al. (2006) and it was realized that the reaction between C and C 5 has the normal exothermic products C 3 + C 3 . Given the importance of these reactions, we decided to study them theoretically in some detail.

New calculations for C + C 3 and C + C 5 reactions

C + C 3

At low collision energies, the reaction of C( 3 P) atoms with linear C 3 in its ground electronic state (X 1 Σ + g ) leads only to adduct formation, C 4 , because the exit channel C 2 + C 2 is endothermic. The lowest energy pathway to produce C 4 is the linear one, and we focus on this pathway here. Under interstellar low-density conditions, the only way to stabilize the C 4 adduct is by emission of a photon. The formation of the linear C 4 adduct is strongly exothermic and spin-allowed to its triplet manifold of states, designated 3 C 4 :

C( 3 P) + 1 C 3 -→ 3 C 4 + hν. (4)
There are a variety of values for this exothermicity. A hightemperature experiment yields a value of (5.21 ±0.21) eV from the heats of formation of C 4 and C 3 (Gingerich et al. 1994), a PST calculation based on a photodissociation experiment yields a lower value of (4.84 ±0.15) eV (Choi et al. 2000), while highlevel ab initio theoretical values (including our own work) computed at the RCCSD and RCCSD(T) levels range from 4.94-4.98 eV without zero-point correction (Martin & Taylor 1995).

The high-temperature experimental value has been used in the RRKM calculations discussed below. The rhombic isomer of C 4 in its ground singlet state has been calculated to to be nearly isoenergetic with the linear isomer (Masso et al. 2006), but the pathway from C and linear C 3 to the first excited triplet state shows a high barrier at the CASSCF level of ab initio theory (see below).

In the C ∞,v symmetry, the three electronic states of C 4 correlating to the three spin-orbit states of C( 3 P 0,1,2 ) lead to two different potential energy surfaces corresponding to the fundamental state X 3 Σ - g and the first excited 3 Π g state. (Note that the ground electronic state of C is of g symmetry.) The energetic and structural parameters of these states of C 4 and the second excited 3 Π u state are listed in Table 4. These parameters and others such as the pathway to the rhombic isomer of C 4 have been calculated at the Restricted Hartree-Fock (RHF) and Complete Active Space Self Consistent Field (CASSCF) level with the double-zeta cc-pVDZ basis set of Dunning (1989), using MOLPRO 2000, a package of ab initio programs designed by H.-J. Werner, and P. J. Knowles (see http://www.molpro.net for more details). This level of theory was also used to determine if the three electronic curves are attractive along the linear reaction pathway. In these calculations, which underestimate the exothermicity of reaction (4), the C ∞v (linear) approach of C toward the C 3 axis, shown in Figure 1, yields no barrier for the ground C 4 ( 3 Σ - g ) electronic state but shows a high barrier of 1.5 eV for the first excited C 4 ( 3 Π g ) state. Using Ω and M J conservation, we obtain that only the C( 3 P 0 ) and C( 3 P 1 , M J = -1, +1) fine-structure substates are reactive; these three substates form vibrationally excited linear C 4 in its fundamental 3 Σ - g state, while the other six substates lead to the formation of the 3 Π g excited state (through a high barrier). Any others approach on the triplet surface, as the perpendicular one leading to the rhombic C 4 , shows high barriers at the CASSCF/cc-pVDZ level. As the C 4 is formed with a great excess of energy, the potential minima of several electronic states, not just the ground state, lie below the dissociation limit (the potential energy of ground-state reactants.). Stabilisation of C 4 adduct can then occur via purely vibrational transitions from the ground-state adduct, but also via electronic transitions from excited state adducts if they can be formed without barriers (Herbst & Bates 1988). Here, we must therefore consider three mechanisms for adduct stabilisation:

-vibrational radiative transitions from quasi-continuum vibrational levels in the ground state (X 3 Σ - g ) adduct to lower bound vibrational levels, -"inverse internal conversion" from the X 3 Σ - g adduct to an excited electronic state followed by electronic photon emission to bound vibrational levels of the ground state (case 1), -direct radiative emission from quasi-continuum vibrational levels in the ground X 3 Σ - g state to lower vibrationally bound levels in excited states (case 2). Other possibilities arise from the isomerisation of the triplet linear C 4 state toward the higher-energy singlet rombric C 4 state. However this isomerisation has to overcome a high barrier as well as intersystem crossing. We can reasonably neglect those possibilities.

(eV) th/exp R(C 1 -C 2 ) R(C 2 -C 3 ) R(C 3 -C4) θ1 θ2 3 Π u 0.
Of the three itemized mechanisms, the case 2 situation can be ignored. Both experiments and detailed calculations on our part show that the potential surfaces of all relevant low-lying excited states of linear C 4 lie almost always above the ground state at all relevant geometries so that emission transition from the ground state are impossible or very inefficient. Therefore, the only possibility for stabilization via electronic emission is case 1, with the dominant channel being potential curve crossing from X 3 Σ - g to 3 Π u at long C 2 -C 2 distances (see Masso et al. 2006, for example) followed by an allowed u→g electronic transition. The u-g potential curve crossing is not allowed when C 4 lies in the symmetric D ∞h linear configuration, but is allowed by vibrational excitation, which reduces the symmetry. Since the 3 Π u state has an electronically allowed transition not only with the fundamental state X 3 Σ - g but also with the first electronically excited 3 Π g state, we have to include these two transitions.

If we designate unstable adducts ("complexes") with an asterisk, the overall mechanism for association can now be written as:

C + C 3 k ass --→ (C 4 ( 3 Σ - g )) * k diss ---→ C + C 3 (5) (C 4 ( 3 Σ - g )) * k rad,v ---→ C 4 ( 3 Σ - g ) + hν (6)
(C 4 ( 3 Σ - g )) * k cc ---⇀ ↽ --- k -cc C 4 ( 3 Π u , 3 Π g ) * (7) C 4 ( 3 Π - u ) * k rad,el ----→ C 4 ( 3 Σ - g , 3 Π g ) + hν, (8)
where ass and diss designate association and dissociation, rad,v designates vibrational emission, cc designates curve crossing, rad,el designates electronic emission, and k designates a rate coefficient. Assuming that curve crossing is more rapid than the assorted emission processes, we obtain the following expression for the rate coefficient of the overall radiative association (k RA ):

k RA = k ass [k rad,v + k rad,el K cc ]/(k rad,v + k diss ) , (9)
where the equilibrium coefficient K cc is equal to k cc /k -cc and pertains to the 3 Π u only .

We first determine the microcanonical rate coefficient for dissociation, k diss , from the ground electronic state of linear C 4 as a function of internal energy E above the C + C 3 dissociation energy. We employ the so-called RRKM (Rice-Ramsperger, Kassel, & Marcus) unimolecular approach [START_REF] Holbrook | Unimolecular Reactions[END_REF]) using the FALLOFF system (Forst 1993). A so-called loose transition state is used with the canonical flexible transition state theory (CFTS) approach [START_REF] Holbrook | Unimolecular Reactions[END_REF]. The needed structural and thermochemical parameters of the studied system derive from quantum calculations. Thermal averaging of the microcanonical rate coefficient for dissociation of the C 4 adduct obtained from the RRKM calculation allows us to calculate the thermal dissociation rate coefficient. The RRKM thermally averaged lifetime of the C 4 adduct, τ = 1 k diss (T) , is presented in Fig. 2 as a function of T . From the equilibrium constant governing formation and dissociation of the adduct, the rate coefficient for formation, which differs from k ass in that fine-structure correlations are not yet taken into account, can be obtained.

The calculated capture rate constant obtained by this procedure at 298 K is equal to 2.0 × 10 -10 cm 3 s -1 with very little temperature dependence in the 10-300 K range, in good agreement with theoretical treatments for reactions between atomic carbon and assorted alkenes and alkynes (Clary et al. 1994) and with the experimental results of Chastaing et al. (2001) for such reactions. This thermal rate coefficient, however, does not take into account the fraction of fine-structure states leading to the attractive ground state C 4 surface. With this factor and the assumption that the fine-structure states are in thermal equilibrium, we obtain a refined association rate coefficient of f (T ) × 2 ×10 -10 cm 3 s -1 in the range 10-1000 K, where

f (T ) = (1 + 2e -16.4/T )/(1 + 3 × e -16
.4/T + 5 × e -43.4/T ). ( 10)

The method of estimating k rad,v equates this rate coefficient with the overall vibrational emission rate (Herbst 1982;Smith 1989):

A(E vib ) = i n i P (i) n i (E vib )A (i) n i →n i -1 (11)
where A (i) n i →n i -1 , the Einstein A coefficient for mode i spontaneously emitting from level n i to n i -1, is equal to n i × A (i) 1→0 ), P (i) n i (E vib ) is the probability of finding mode i in level n i , and the sums are over all modes i and all energetically accessible quanta n i . The vibrational frequencies and Einstein coefficients, calculated at the B3LYP/vtz level, are listed in Table 4, leading to k rad,v = 349 s -1 .

To estimate the rate coefficient k rad,el for stabilization by emission of electronic radiation, we use the results of ab initio calculations that the electronic potential curves of the C 4 ( 3 Π u ), C 4 ( 3 Σ - g ) and C 4 ( 3 Π g ) states have very similar shapes. Therefore, we can approximately ignore nondiagonal Franck-Condon factors. With the additional assumption that the diagonal factors are unity, we can write that < ν ′ |ν ′′ >= δ ν ′ ,ν ′′ , so that the spontaneous electronic emission rate coefficients are given by the expression (esu-cgs units):

k rad,el = (64π 4 e 2 a 2 0 /3h)ν 3 |µ el | 2 , ( 12
)
where e is the electronic charge, ν is the transition frequency, a 0 is the Bohr radius, and |µ el | is the electronic transition moment.

From the 3 Π u state, there are allowed transitions toward the 3 Σ - g and the 3 Π g state [START_REF] Larsson | [END_REF]. We obtain that k rad,el ≈ 6 × 10 4 s-1. Finally, we obtain the equilibrium coefficient K cc by assuming that the relative populations of the 3 Π u , 3 Π g , and 3 Σ - g states are equal to their relative densities of vibrational states at an internal C 4 energy of 5.21 eV, the experimental exothermicity of reaction (4). This assumption leads to an equilibrium coefficient K cc for the 3 Π u state only of 0.15, and an overall radiative stabilization rate k rad,v + k rad,el K cc of 9350 s -1 .

Once the partial rate coefficients are all calculated, we can obtain the total rate coefficient for radiative association, k RA as a function of temperature. The results are shown in Figure 3; the value at 15 K is 3 × 10 -12 cm 3 s -1 . The value at 15 K if only vibrational stabilization is allowed is a much lower 1 × 10 -13 cm 3 s -1 , which serves as a reasonable lower limit. The value obtained with the < ν ′ |ν ′′ >= δ ν ′ ,ν ′′ assumption is certainly an extreme upper limit, because the diagonal Franck-Condon overlaps are certainly lower than unity, the electronic transition moment, assumed to be independent of energy, may well decrease with increasing energy for certain states [START_REF] Boyé | [END_REF], and the internal conversion from the ground X 3 Σ - g of C 4 to excited electronic states may not reach equilibrium. Estimation of the size these factors have on the association rate coefficient is not facile, but a reasonable guess is that they contribute to produce a factor of ≈ 0.25, leading to a reduced value at 15 K of 8 × 10 -13 cm 3 s -1 . We adopt as an error limit an uncertainty of ± 75%, allthough this error does not quite cover the extreme maximum and minimum values discussed above. From the RRKM calculations, we obtain a temperature dependence for k RA of approximately T -1 , in excellent agreement with the approach of Bates & Herbst (1988) for a system with two rotational degrees of freedom. We obtain finally a temperature-dependent association rate coefficient k RA (T ) of (4.0 ± 3.0) × 10 -14 × (T/300) -1 cm 3 s -1 in the range 10-300 K. Compared with the radiative association rate coefficient of 1 × 10 -10 cm 3 s -1 in Smith et al. (2004) and osu.2003, our new value is lower by a factor of ≈ 100 at 10 K. This discrepancy between old and new values is larger than the formerly assumed uncertainty of an order of magnitude.

C + C 5

For the reaction between C in its ground 3 P state and linear C 5 in its ground 1 Σ + g state, the formation of the linear C 6 adduct in its 3 Σ - g ground state is strongly exothermic and spin-allowed. This case is then very similar to the C + C 3 one, and to determine if the electronic curves are attractive along the entrance channel reaction pathway, we performed similar ab initio calculations. Our results are also similar, with no barrier for the C 6 ( 3 Σ - g ) electronic state but high barriers for the C 6 ( 3 Π) electronic states. Unlike the case of the C 4 adduct, however, the C 6 adduct can fragment by an exothermic route; in particular

C( 3 P)+C 5 ( 1 Σ+ g ) -→ C 6 ( 3 Σ-g ) -→ C 6 ( 1 Σ) -→ C 3 ( 1 Σ+ g )+C 3 ( 1 Σ+ g ) , (13)
with an overall reaction enthalpy of ∆H = -1.36 eV. Although this reaction is formally spin-forbidden to the products in their singlet ground states, the adduct is likely to last long enough to allow intersystem crossing, as in the C + C 2 H 2 reaction (Mebel et al. 2007), and the barrier on the singlet exit channel is certainly much lower than the exothermicity (Nelson et al. 1982). The first excited triplet state of C 3 lies about 2 eV above the ground singlet state so is probably not accessible. Based on experiments, the assumption that the rate coefficient is independent of the number of hydrogen atoms on the C 5 reactant, and using the fine structure factor in eq. ( 10) , we estimate the rate coefficient to form the adduct and subsequent products to be 1.2±(0.8)×10 -10 cm 3 s -1 for 10-300 K. This value is somewhat less than that obtained from the capture methodology of Clary et al. (1994). Compared with the value in osu.2003 (k RA = 1.4 × 10 -10 cm 3 s -1 ), the rate coefficient for the reaction C + C 5 is approximately the same but the products are C 3 + C 3 instead of C 6 .

The rate coefficients for other C + C n reactions are discussed in the Appendix. These reactions are not among those the model results are very sensitive to.

Impact on predicted abundances

General impact

To quantify the overall impact of change in the rate coefficients/products computed in the previous section, we sum R i j (t), the fractional difference for species j and reaction i as defined in equation ( 1), over the species j and divide by the number of species n j to obtain the average fractional difference AFD(t) for reaction i:

AFD(t) = 1 n j j |R i j (t)|. (14)
Here, as in equation ( 1), we define the reference fractional abundance X re f j (t) for each species as that obtained with the old rate coefficient/products, but define the new values of X i j (t) as those obtained with the modified values for reactions i obtained here. An unimportant reaction at a specific time would give an AFD close to zero at that time. It should be noted that although we are using a method similar to section 2.2, the goal here is completely different. In the sensitivity analysis section (2.2), we multiply all reactions, one after another by a factor of 2 in order to compare the abundance sensitivity to individual reactions. Here, we change the rate coefficients for which new calculations have been done, for instance the C+C 3 reaction is changed by two orders of magnitude, and we look how much the new rate coefficients have changed the model predictions. If we redo the

C 3 (0) (2) C 5 C CO C 4 H 2 C 6 H (1)
(3) HC 7 N O Fig. 5. Abundances with respect to total hydrogen of several important species. Black dash-dotted lines (0) are calculated abundances when the standard network osu.2003 is used; grey dashed lines (1) when only C + C 3 is modified; grey dash-dotted lines (2) when only C + C 5 is modified, and black solid lines (3) when both C + C 3 and C + C 5 are modified. sensitivity analysis as in section 2.2 with the updated network, we may find different "important" reactions since the network has been changed.

For the dense cloud model discussed in Section 2, we consider three different cases for reactions i: (1), we change only the rate coefficient of the C+C 3 reaction, (2), we change only the products and the rate coefficient of the C+C 5 reaction and (3), we perform the changes for both reactions. For each of these cases, we compute the AFD parameter by (a) summing over all species (452), and by (b) summing only over those species with a fractional abundance greater than 10 -10 at 10 5 yr. For (b), the sum is made over 79, 80 and 77 species for cases (1), ( 2) and (3) respectively. Fig. 4 shows the results for the six different cases. It is clear from the results that the most important effect is obtained by the combined effect of changing both C+C 3 and C+C 5 reactions. For case (3), the sum over all species yields an AFD of 15 at slightly more than 10 5 yr, while the sum over the most abundant species only yields an AFD of 13 at 10 5 yr. If only one of the two reactions is changed, C+C 3 has the greater effect whereas C+C 5 affects the species at early times.

Impact on specific species

In Fig. 5, we show how the abundances of selected species are affected by the modifications of the C+C 3 and C+C 5 reactions at intermediate times; at other times there is little to no effect. For carbon monoxide, the reduction of the C + C 3 reaction rate coefficient results in the lowering of its abundance in the period 10 3 -10 5 yr by at most one order of magnitude. Changing the products of the C+C 5 reaction on the contrary slightly increases the CO abundance. For neutral atomic carbon, the gradual decrease in abundance with increasing time occurs much later when the rate coefficient of C +C 3 is reduced; at its maximum, there is a difference in abundance of about 3 orders of magnitude. The change in C + C 5 speeds up the destruction of C. In fact, the only species shown in Fig. 5 for which the modification of this reaction has a strong effect are C 5 and C 6 H.

As discussed in Section 2.3, with the use of the osu.2003 network, these two reactions are both involved in catalytic cycles to convert C and O into CO. By radiative association reactions with atomic carbon, C 3 and C 5 form C 4 and C 6 , which then react with atomic oxygen to give CO and regenerate C 3 and C 5 . In this work, we have shown that the C + C 3 reaction is less efficient than the value used in osu.2003 by two orders of magnitude at 10 K and the more likely products of the C + C 5 reaction are two C 3 molecules. Even after changing these reactions, this catalytic process remains the most efficient one to form CO at 10 4 yr. Changing only the C + C 5 reaction products makes this process more efficient by introducing more C 3 into the cycle. For this reason, CO is slightly increased whereas C is decreased. Obviously C 3 is more abundant because C + C 3 consumes less C 3 and C + C 5 produces it. Contrary to C 3 , the C 5 abundance decreases if the C + C 5 → C 6 -O + C 6 → C 5 + CO cycle is broken because C 5 is not locked in this loop anymore and is destroyed to give C 3 . The effect of these changes on C-rich molecules such as the ones shown in Fig. 5 is less evident to explain. From a general point of view, larger abundances of atomic oxygen and carbon between 10 4 and 10 5 yr destroy these species more efficiently than producing them. The radical C 6 H for instance is destroyed by C to give C 7 and C 7 in turn reacts with C to produce C 3 and C 5 (see Table A

Comparison with observations

To study the impact of these new rate coefficients on the agreement between models and observations, we used the method described in Wakelam et al. (2006a). We modeled the chemical evolution of two different clouds: L134N and TMC-1 (Cyanopolyyne Peak), using the Nahoon chemical model. The list of reactions is osu.2003 with the original C + C n rate coefficients and osu.2003 with the new values of the C + C n rate coefficients listed in Table A.1. For the uncertainties in the rate coefficients of these reactions, we assumed a flat distribution (because the mean values of the rate coefficients are not necessarily the favorite values) with the uncertainty ranges described in Table A.1. For the other reactions, we used log-normal distributions (see Wakelam et al. 2004). The physical conditions are taken to be homogeneous in the observed regions: a gas temperature of 10 K, an H 2 density of 10 4 cm -3 and a visual extinction of 10. The elemental abundances are the low-metal elemental abundances (see table 1 in Wakelam & Herbst 2008). For TMC-1, we decreased the oxygen abundance to have a C/O elemental ratio of 1.2 in order to better reproduce the observations (see Wakelam et al. 2006a, and references therein). The observed abundances are given in Tables 3 and4 of Garrod et al. (2007). In addition, we included the observational upper limits on the SiO abundances in these two clouds by Ziurys et al. (1989); the upper limits for this species are 2.6 × 10 -12 and 2.4 × 10 -12 for L134N and TMC-1 respectively. In total, we have observed abundances of 42 and 53 species for these two clouds to compare with our calculations.

The results of the comparisons are shown in Fig 6 in three panels, for each of which a different criterion is utilized. These criteria are based on the Monte Carlo approach to determination of the uncertainties in the computed abundances based on uncertainties in the rate coefficients, and the overlap of Gaussian distributions representing both the computed and observed abundances (Wakelam et al. 2006a). In the top panel, we use the fraction of reproduced molecules. In the middle panel, we use the so-called "distance of disagreement" D in which, for species not reproduced by the first criterion, we sum over the remaining species the distances between logarithms of the observed and model fractional abundances. Finally, in the bottom panel, we use the minimum distance of disagreement (over all times), divide by the distance of disagreement, and multiply by the fraction of reproduced molecules. See Wakelam et al. (2006a) for details on these parameters. The time of best agreement is roughly the same for all three parameters, although the sharpest agreement occurs for the bottom panel. It can be seen in all panels that the general agreement with the observations is slightly better using the new values of the C + C n rate coefficients. However, the more interesting effect is the shift in time of the best agreement. With the original model, the best agreement was obtained around 3 × 10 4 yr whereas now we calculate the best agreement to be between 10 5 and 3 × 10 5 yr. Note that to compare our results with the results of Wakelam et al. (2006a), we have only updated the C + C n rate coefficients whereas many other reactions have been updated in the latest version of the osu database (osu.3.2008).

Conclusion

This paper presents an approach to improve chemical models, which consists of first identifying important reactions, then obtaining improved rate coefficients for these reactions, and finally studying the impact of these new rate coefficients on the predictions of the model. In this example of the method, we found that under cold dense cloud conditions, the abundances of many species are sensitive to the rate coefficients of the C + C 3 and C + C 5 reactions. Using detailed ab initio and kinetic calculations, we have shown that the rate coefficient of the C + C 3 → C 4 previously used in the osu.2003 database is incorrect by two to three orders of magnitude at 10 K and has an inverse temperature dependence. We also found that the rate coefficient for the C + C 5 reaction was roughly correct in the osu.2003 database, but the products are most likely C 3 + C 3 instead of C 6 , as assumed earlier based on faulty thermodynamic information. Newly obtained rate coefficients for other reactions in the C + C n series are also reported, although the model shows little sensitivity to these. With the new rate coefficient for the association reaction between C and C 3 and the slightly changed rate coefficient and new products for the C + C 5 reaction, we found that the abundances of many carbon chain species are strongly modified at the so-called early time of 10 5 yr. The main reason for this effect is that the C + C 3 → C 4 / O + C 4 → CO + C 3 and C + C 5 → C 6 / O + C 6 → CO + C 5 reactions comprise a very efficient catalytic cycle to transform C and O into CO. Slowing down the first cycle and removing the second one, both decreases the abundance of CO and enhances the abundances of atomic C and O at early times. These changes in turn cause an alteration in the early-time abundances of many other species. The agreement with observed abundances in the two dense clouds L134N and TMC-1 (CP) is not significantly modified by these new rate coefficients/products but the best agreement is obtained at later times using the new values. The newly calculated rate coefficients and/or products will be included in the latest network from the Ohio State group (http://www.physics.ohio-state.edu/˜eric/research.html).

Fig. 1 .

 1 Fig. 1. Co-linear VDZ-CASSCF one-dimensional cuts of the lowest triplet electronic states of linear C 4 molecules along the C 3 -C stretch. The C 3 bonds are optimized. The labeling of the C 4 electronic states is based on D ∞h symmetry.

Fig. 2 .

 2 Fig. 2. RRKM lifetime (in s) of the C 4 adduct as a function of the internal energy (in K) above the C + C 3 dissociation limit.

Fig. 3 .

 3 Fig. 3. Radiative association rate coefficient for C 4 production as a function of temperature.

Fig. 4 .

 4 Fig. 4. Average fractional difference (AFD, see text) as a function of time. The dashed lines are for case (1), the dashed-dotted lines for case (2), and the solid lines for case (3). Black lines are for case (a) whereas grey curves are for case (b).

Fig. 6 .

 6 Fig. 6. Comparison between model and observations in two different clouds (black: L134N and grey: TMC-1). The solid line represents the comparison with the model using the original values of the C + C n rate coefficients whereas the dashed lines represents the comparisons with the updated model.

Table 4 .

 4 Vdz/CASSCF optimized structural parameters

	State T 0

  Distances R in Å, angles in degrees and total energies are with respect to the X 3 Σ - g state. The results presented in the table are from this work except the experimental data, which are fromLinnart et al. (2000) for 3 Π g andXu et al. (1997) for 3 Π u .

		89/0.93	1.27	1.33	1.27	180 180
	3 Π g	0.63/0.82	1.28	1.34	1.28	180 180
	3 Σ -g	0	1.32	1.30	1.32	180 180

Table 5 .

 5 Vibrational properties of the X 3 Σ - g state of the C 4 molecule.

		ν (cm -1 )	IR int	A 1,0 (s -1 )	n i A 1,0 (s -1 )
			(km.mole -1 )
	v1	172	27	0.01	0.34
	v2	172	27	0.01	0.34
	v3	352	0	0	0
	v4	352	0	0	0
	v5	908	0	0	0
	v6	1548	312	89	342
	v7	2032	0	0	0

  .1). Similarly C 4 H 2 is destroyed by the reaction C 4 H 2 + C → C 5 H + H and C 5 H is destroyed by O, producing CO and C 4 H. Large cyanopolyynes, such as HC 7 N, are reduced in abundance. On the other hand, large O-bearing molecules, such as CH 3 OH, are increased in abundance or not changed.

Acknowledgements. V. W. acknowledges the french national program PCMI for partial support to this work. E. H. thanks the National Science Foundation for its support of his research program in astrochemistry.

Appendix A: Other C + C n reactions

The calculated rate coefficients and products for C + C n are listed in Table A.1 for n = 2 -8 along with estimated uncertainties and the older values used in the osu.2003 network. The applicable temperature range is generally 10-300 K, although for radiative association reactions, the dependence can extend to higher temperatures. For the C( 3 P) + C 2 ( 1 Σ + g ) reaction, the spin-allowed pathway leads to a C 3 (a 3 Π u ) adduct, which is not the ground electronic state of C 3 but is highly thermodynamically accessible, lying 5.16 eV below the reactants. Preliminary ab intio calculations (CASCCF, vdz basis, full valence active space) give no barrier for the production of the a 3 Π u state. To determine the rate coefficient for radiative association, we considered only vibrational relaxation, Computing vibrational frequencies for C 3 at the B3LYP/vtz level, we obtained a relaxation rate of k rad,ν = 220 s -1 . We then estimated the association (capture) rate coefficient to be 2×10 -10 cm 3 s -1 based on experiments of analogous systems (e.g. C + C 2 H 2 ) and calculated the dissociation rate coefficient by the RRKM method. We obtained the radiative association rate coefficient, shown in Table A.1, to be (3 ± 2) × 10 -16 × (T/300) -1.0 cm 3 s -1 , a rather low value due to the rapid dissociation of the small C 3 adduct.

For the C( 3 P)

reactions, the formation of the C n+1 adducts is strongly exothermic and spinallowed. The possible potential energy surfaces in the entrance channels for all of these reactions are 1,3,5 Σ + and 1,3,5 Π. Preliminary ab intio calculations (CASCCF, vdz basis) show that the three 1,3,5 Σ + states have no barrier in the entrance channel, but that the three 1,3,5 Π states have high barriers along the reaction pathway. Exothermic fragment channels exist for all of these adducts. The rate coefficients for these reactions are once again estimated from experimental values of analogous systems, which in general are smaller than the capture values, derived from the formalism of Clary et al. (1994), and further reduced by a factor that allows for the multiplicity of the potential energy surfaces that correlate with the reagents and also by a factor for the multiplicity of the exit channels if relevant. Correlation involving the fine-structure states of atomic C is ignored. The

2) × 10 -10 0 1 Rate coefficients in units of cm 3 s -1 given by k = α × (T/300) β assigned rate coefficients and estimated uncertainties are shown in Table A.1.

The C( 3 P) + C 7 ( 1 Σ + g ) reaction leading to the formation of the C 8 adduct in the 3 Σ - g ground electronic state is strongly exothermic and spin-allowed. By comparison with C + C 5 we assume that there is no barrier in the entrance channel for the formation of the ground C 8 electronic state and, although this reaction is formally spin-forbidden to the products in their singlet ground states, the adduct is once again likely to last long enough to allow intersystem crossing. Once again, we use analogous experimental results rather than the formalism of Clary et al. (1994) to obtain the capture rate, and reduce this via eq. ( 10).


Andreas Herzig
email: herzig@irit.fr

Jérôme Lang
email: lang@irit.fr

Dominique Longin
email: longin@irit.fr

Thomas Polacsek
email: polacsek@irit.fr

A logic for planning under partial observability

We propose an integration of a fragment or propositional dynamic logic with an epistemic logic so as to represent logically the interactions between action and knowledge that are fundamental to planning order incomplete knowledge and partial observability. This logic, called EDL, enables us representing incomplete knowledge, nondeterministic actions, observations, sensing actions and conditional plans; it also enables a logical expression of several frequently made assumptions about the nature of the problem such as determinism, full observability, unobservability, or pure knowledge gathering. Plan verification corresponds to testing the validity of a given formula of this logic. The allowed plans are conditional, and a key point of our framework is that a plan is meaningful if the branching conditions bear on the knowledge of the agent only, and not on the real world (to which tha agent may not have access); this leads us considering "plans that reason" which may contain branching conditions referring to implicit knowledge to be evaluated at execution time.

Introduction

A large amount of work has been done recently about planning under incomplete information. By incomplete information, we mean (as usual) that the initial state of the world is not fully known and/or the actions are not deterministic. The gap between planning under complete and incomplete information relies on the role of knowledge in the latter and especially the interactions between knowledge and action (which are irrelevant for planning under complete knowledge). These interactions work in both ways:

• the choice of an action to perform is guided by the knowledge the agent has on the actual state of the world, and especially by the observations made after performing previous actions. As soon as performance of an action allows to gather knowledge by a susbsequent observation, the choice of the following action will be generally conditioned by this observation. This leads to the notion of conditional plan (for planning under complete information). • performing an action may bring some more knowledge (and help the agent acting in a better way, as explained just above) by means of consecutive observations; this has lead many researchers to focus and formualize a particular class of actions, viz. actions of observation, alias (pure) sensing actions, which do not change the state of the world but only the agent's beliefs.

On the other hand, the planning community has recently paid a lot of attention to the role of logic in representing and solving planning problems. This includes both (1) the satplan framework (as well as model checking) and its very recent extensions to planning under incomplete knowledge and (2) the action description languages and their recent application to planning. The former (1) lead to powerful resolution algorithms which benefit from the theoretical and experimental results on satisfiability. So far, not been too much extended to planning under incomplete information (up to a very small number of exceptions) nor to the sophisticated handling of change at work in approaches of type (2). The latter (2) gives birth to very expressive languages that enable reasoning with nondeterminism, minimal change, ramifications, concurrent actions, and more recently interactions between action and knowledge. The latter approaches did not lead yet to the development of planning algorithms based on automated proof procedures. This gap between (1) and ( 2) is nothing but the very classical duality between expressivity and efficiency and there is no reason why it should not be successfully filled in the next years. We believe that in order to pave the way towards this objective, a necessary step is the development of logics that explicitly handle all the facets of the aforementioned interactions between action and knowledge. This paper is a first step in this direction.

The question now consists of identifying the "simplest" logic containing the notions of incomplete knowledge, nondeterministic actions, observations, conditional plan and sensing actions. Two of these words evoque two well-known families of logics:

• dynamic logic aims at reasoning with complex combinations of actions (including sequential and conditional actions). It has been initially developed so as to reason about programs. Decidability and complexity results, as well as automated proof procedures for the standard propositional dynamic logic and its variants, extensions and restrictions are a familiar part of the logical landscape. But still, and surprisingly, dynamic logic has not been much considered for planning (further on we will make it clearer why this is not as surprising as it may appear).

• epistemic logics aim at reasoning with explicit knowledge of an agent. Some simple epistemic logics (such as S5) are computationally not harder than classical logic.

An immediate analysis of the needs (handling the intimate interactions between action and knowledge) call for a logic including both a suitable fragment of dynamic and epistemic logic. However, to our knowledge almost nothing has yet been done for such an integration of dynamic and epistemic logic in the scope of planning under incomplete knowledge (Segerberg ), [START_REF] Baltag | The logic of public announcements,common knowledge and private suspicions[END_REF] and [START_REF] Gerbrandy | Dynamic epistemic logic[END_REF].

We now go a bit deeper into the details. For the reader not familiar with dynamic logics nor with epistemic logic, the necessary background is given in Appendix. What is missing to propositional dynamic logic (PDL) so as to render it suitable for planning under incomplete information is (1) the possibility for actions to have epistemic effects and (2) the possibility to branch on epistemic conditions. ( 1) is clear and does not need further intuitive explanations. For (2), this is more subtle. Indeed, PDL enables expressing some kinds of conditional actions, namely, of the form if p then α else β. Are these conditional actions good candidates for expressing conditional plans? The answer is negative. While a program can be supposed to know at any instant the value of any variable, this is not the case (in general) for an agent acting in an incomplete environment, for whom some parts of the world are hidden. Clearly, this plan does mot solve our planning problem, because in general the agent does not know whether princess(i) holds or not, and therefore he is unable to branch on such a condition. The solution is to allow for epistemic conditions only. Suppose therefore that our language contains a modal operator K. A plan such as can then be formulated. However, except when d = 1, it misses the goals, because the agent may ignore whether princess(i) is true or not. Thus, agents branch on epistemic conditions only, because they are able to decide whether they know a given formula or not, whereas they are not always able to decide whether this formula is true or not in the actual world.

This brings us to the following specificity of our logic: it enables the expression of plans that explicitly involve a reasoning task. Let us consider the tiger and princess example with 4 doors and 2 tigers. Described in classical conditional planning formalisms, this problem would give for instance the following plan: It can be checked easily that π 3 achieves the goal with certainty. However, it explicits all branches and is thus space-consuming. If d and t vary then the size of a valid plan increases exponentially. Now, such plans have conjunctions of elementary observations as branching conditions (tiger(1) or ¬tiger( 1) is observed after listen( 1) is performed, etc.), which means that, at any step of its execution, (i) the agent decides in unit time what is the next action to follow and (ii) she is not asked to reason (only to obey, to follow a fully explicited plan).

Let us now consider the following plan π 4 for the same problem, where epistemic branching conditions are allowed. We use the following abbreviations:

KnowW hereP rincess = Kprincess(1) ∨ . . . ∨ Kprincess(d) KnowW hereT igers = (Ktiger(1) ∨ K¬tiger(1)) ∧ . . . ∧ (Ktiger(d) ∨ K¬tiger(d))
and we define the following procedures: It can be checked that π 4 reaches the goals. Interestingly, if d and t vary, there is a plan in the style of π 4 (using epistemic branching conditions) whose size is linear in d while any valid plan in the style of π 3 (with no epistemic branching conditions) has an exponential size. It is important to notice that this gain in size is counterbalanced by a loss of execution time: indeed, although π 1 -like plans have a size in O(2 d ), their execution time (assuming that actions are performed in unit time) takes only O(d). In contrast, for π 3 -like plans whose size is in O(d), their execution requires a linear number of calls to a NP-complete oracle. Therefore, a plan with epistemic branching conditions (EBC plan for short) is all the more interesting as the ratio between cost of space and cost of expensive on-line execution time is high.

An epistemic dynamic logic

Language of EDL

The language EDL is the fusion of an epistemic logic and a dynamic logic. Hintikka first proposed to analyse of knowledge and belief in terms of possible states [START_REF] Hintikka | Knowledge and belief[END_REF]. In this paper we are only interested in strong knowledge rather than in belief (since merely believing a fact would not ensure the truth of this fact and therefore would be in principle helpless so as to prove that a given plan certainly succeeeds).

The language of epistemic dynamic logic EDL is constructed from a set of atomic formulas VAR, a set of atomic actions ACT 0 , the classical logic operators →, ∧, ∨, ¬, the epistemic operator K, the dynamic operator [.], and the action operators λ and ;. The formula [α]q is read "after the execution of the action α, q is true". Note that we allow for nested epistemic and dynamic operators. λ is the action "do nothing". The complex action α; β is read "execute α and then β". α A is an abbreviation of ¬[α]¬A,

and [if A then α else β]C is an abbreviation of (A → [α]C) ∧ (¬A → [β]C).
An EDL formula is

• objective iff it does not contain any modality;

• static iff it does not contain any dynamic modality;

• an epistemic atom iff it is of the form KA, where A is any EDL formula;

• an epistemic formula iff it is formed from epistemic atoms and the usual connectives.

For instance, a∨(b∧c) is objective;

K(a∨¬K(a → [α]b)) is an epistemic atom; K(a ∨ ¬K(a → [α]b)) ∨ ¬K[β]c is an epistemic formula; a ∨ ¬K(b ∧ Kc) is static but not epistemic; Ka∨¬K(b ∧Kc
) is both static and epistemic.

Semantics of EDL

The semantics of EDL is in terms of possible states.

We interpret the knowledge of the agent at a possible world w by a set of worlds associated to w. Actions are interpreted as transition relations on worlds. We define a model for EDL as a quadruple

M = W, R K , {R α : α ∈ ACT 0 }, V where W is a set of pos- sible worlds, R K ⊆ W × W and every R α ⊆ W × W
is an accessibility relation1 , and V associates to each world an interpretation. We require

• R K to be an equivalence relation on W , • R λ {w} = {w}, • R α;β = R α • R β , • R α • R K ⊆ R K • R α .
The truth conditions are defined as usual, in particular:

• |= M,w KA if |= M,v A for every state v ∈ R K (w) • |= M,w [α]A if |= M,w A for every state w ∈ R α (w)

Axiomatization of EDL

Our axiomatisation of EDL contains that of classical logic together with modal logics S5 for knowledge and K for actions.

N(K)

A KA

N([α]) A [α]A K(K) ( KA ∧ K(A → C)) → KC T(K) KA → A 5(K) ¬KA → K¬KA Def(λ) [λ]A ↔ A Def(α; β) [α; β]A ↔ [α][β]A K([α]) ([α]A ∧ [α](A → C)) → [α]C Acq([α], K) K[α]C → K[α]KC

Action and information

Our language is sufficiently expressive to distinguish explicitly between the ontic and the epistemic effects of actions, where ontic (respectively epistemic) effects are meant to be effects on the physical world only (resp. on the epistemic state of the agent only). Two particular classes of actions are uninformative actions whose effects are purely ontic and purely informative actions whose effects are purely epistemic. As a consequence, our logic is a helpful language for expressing some specific conditions about observability, since observability is primarily a matter of interactions between ontic and epistemic effects. Intuitively, uninformative actions cannot any bring any new knowledge, which means that everything that is known after the action is performed could be predicted before it was performed. The other way round, purely informative actions do not change the world. In our example, the actions listen(i) are purely informative, while the actions open(i) are not.

A key hypothesis of our logic is that any action α can be decomposed into two actions, namely α = α e • α o , where α e is purely informative and

α o uninformative. open(i) can be written as open(i) e • open(i) o
, where its uninformative component open(i) o has the effect of making the agent married, eaten, or none of both, without him being aware, and its informative component open(i) e has the effect to make the agent learn whether he gets married, eaten or none of both.

Given that α = α e • α o , what is the relation between α o and α e ? Ideally, all changes brought about by α o are perceived through α e . We call actions of this kind (i.e., actions informing the agent about all changes they cause) fully informant. Formally, α is fully informant iff for any objective formula A, we have that A → [α](¬A → K¬A) holds. Purely informative actions α are fully informant because the ontic part is empty, i.e. α o = λ. In our example open(i) is fully informant because it makes the agent aware of the change of truth value of eaten or married when it occurs.

Noticeably, these properties (purely informative, uninformative, fully informant) are about individual actions. Nevertheless, global properties of environments can be captured from local properties of actions. An environment Σ consists in a nonlogical theory T describing the general laws of the world and what is known about the effects of actions, together with the description of what is known about the initial state Σ Init . An environment Σ is

• fully observable iff (i) each α ∈ ACT 0 is fully infor- mant, and (ii) Σ Init is complete 2 ; • unobservable iff each α ∈ ACT 0 is uninformative; • ontically static iff each α ∈ ACT 0 is purely informa- tive; • deterministic iff each α ∈ ACT 0 is deterministic.

Uninformative actions

We characterize uninformative actions by two axioms.

DetEpi(

[α], K) α KA → [α]KA Con([α], K) [α]KC → ([α]⊥ ∨ K[α]C)
The first expresses that uninformative actions are epistemically deterministic. The second says that the epistemic effects of α are known before hand. Semantically, the axioms correspond to the conditions

• If w , w ∈ R α (w) then R K (w ) = R K (w ) • If R α (w) = ∅ and w 1 R K • R α w 2 then w 1 R α • R K w 2
It can be proved that these two axioms together are equivalent to the more compact criterion of uninformativeness ¬K[α]A → [α]¬KA. It says that the agent cannot observe anything after α is performed: indeed, for any formula A, if he cannot predict before α is performed that A will hold after α is performed, then he will not know A after α is performed. Acq([α], K),

Con([α], K) gives us the equivalence [α]KC ≡ ([α]⊥ ∨ K[α]C).

Purely informative actions

Purely informative actions do not change the world but only the knowledge; they are characterized by the axiom

Pres([α])

A → [α]A if A is an objective formula.

Semantically, this corresponds to the condition

• if w 1 R α w 2 then V w1 = V w2
It follows by standard modal principles that purely informative actions do not diminish the knowledge of an agent. Proposition 1 Let A be an objective formula and α a purely informative action. Then Pres ([α]

, K) KA → [α]KA is provable from EDL .
If A is subjective then this does not necessarily hold, in particular if A expresses ignorance. For example K¬KA → [α]K¬KA cannot be accepted, given that K¬KA ↔ ¬KA is valid in our logic of knowledge S5.

A purely informative action α typically makes an agent evolve from ¬KA ∧ ¬K¬A to either KA or K¬A for some objective formula A. We might thus identify α with the action of testing whether A, denoted by A??. Note that the empty action, equivalent to testing whether , is a (degenerate) purely informative action.

In [START_REF] Herzig | Knowledge, actions, and tests[END_REF] we analysed such testing actions A?? as the nondeterministic composition of verifying that A (denoted by A?) and verifying that ¬A. Formally, A?? is an abbreviation of A? ∪ (¬A)?. Such an action A? of verifying that A is an extension of standard PDL testing actions to the epistemic context. We consider that verifying that A is inexecutable if A is false: ¬A → [A?]⊥.

Deterministic actions

In some domains actions are deterministic: every possible execution of an action will always lead to the same result.

Det ([α])

¬[α]C → [α]¬C
Semantically we have • R α (w) is a singleton or the empty set.

A solution to the Frame Problem

We must solve the Frame Problem in order to put to work our logic. Basically, we could integrate any solution into our framework, given that we have analysed the epistemic effects of an action in terms of its ontic effects on possible worlds. Scherl and Levesque e.g. used Reiter's solution to the Frame Problem, and applied regression as a reasoning method [START_REF] Scherl | The frame problem and knowledge-producing actions[END_REF]. We adopt the solution in [START_REF] Castilho | Formalizing action and change in modal logic I: the frame problem[END_REF]) based on dependence relations, which can be taken over without modifications and which we briefly recall here.

We associate to every atomic action α the set of atomic formulas it influences. Given a dependence relation DEP , |= DEP is the corresponding extension of the EDL consequence relation. As a particular case, purely informative actions verify DEP (α) = ∅. Thus, we have for instance the frame axioms t(1) → [listen(1)]t(1) and p(2) → [listen(1)]p(2). Combining all these atomic frame axioms by principles of classical logic, we obtain the following.

Proposition 2 Let A be objective. If DEP (α) = ∅ then |= DEP A → [α]A. If atm(A) is the set of atoms of A and atm(A) ∩ DEP (α) = ∅ then |= DEP KA → [α]KA.

Plan verification in EDL

The set of meaningful plans is the smallest set such that • α is a meaningful plan for every α ∈ ACT 0 ∪ {λ};

• if π and π are meaningful plans and A is an epistemic formula then π; π and if A then π else π are meaningful plans.

Intuitively, a meaningful plan is a plan whose branching conditions are "epistemically interpretable", which means that the agent can decide whether the branching condition holds or not (which would not necessarily be the case if the formula were not epistemic, cf. example).

A plan verification problem V is defined by a 5-tuple T, Σ Init , DEP, G, π where • T = S, E, X is an EDL theory composed of a set of state axioms S expressing static laws of the domain, laws about the effects of actions E, and executability laws X. Static laws are static formulas; effects laws are formulas of the form A → [α]C with A objective and C an epistemic formula; executability laws are formulas of the form A ↔ α with A objective. • Σ Init is an epistemic atom;

• DEP is a dependency function;

• G is a static formula (the goal);

• π is an meaningful plan.

Given a plan verification problem V, π is said to be

• executable for V iff T |= DEP Σ Init → π holds. • valid for V iff T |= DEP Σ Init → [π]G holds.
While the validity problems in EDL is PSPACE-hard (because EDL extends the logic K where validity is PSPACE-complete), the complexity of the much more specific plan verification problem in EDL is lower: Proposition 3 (complexity of plan verification) plan verification in EDL is Π p 2 -complete. Note that if branching conditions were restricted to elementary conjunctions of observations instead of any epistemic conditions then the problem would be "only" coNP-complete.

It is worth investigating what plan validation becomes when some specific assumptions are made about observability and determinism.

Unobservable environments When the environment is unobservable, we can show by induction that uninformativeness extends to any meaningful plan: for any meaningful plan π and any objective formula A, π KA → K[π]A holds, which leads to the following intuitive result: if there is a meaningful valid plan π for P = T, Σ Init , DEP, G then there is a nonbranching (i.e., without tests) meaningful valid plan for P.

Fully observable environments When the environment is fully observable, we can show by induction that for any meaningful plan π and any objective formula A, we have [π](KA ∨ K¬A) holds, and that the epistemic operator is needless, which is expressed intuitively by the following result: if there is a meaningful valid plan π for P then there is an epistemic-free (e.g., without any occurrence of K) meaningful valid plan for P. Thus, a fragment of PDL is sufficient for capturing plan verification in fully observable environments.

Fully epistemic environments When the environment is fully epistemic, all actions are commutative and knowledge preserving. This leads to the following result: if there is a meaningful valid plan π for P then α 1 ; α 2 ; ...; α n is a valid plan for P, where ACT 0 = {α 1 , ..., α n }.

We end up the section with some considerations on plan existence. Informally, the plan existence problem reads: given P = T, Σ Init , DEP, G , is there a plan π for P? Similar to verification problems, we check whether there is a proof of T, ¬G |= DEP ¬Σ Init . If this is the case, then we can associate a meaningful executable plan π to P. π can then be checked for validity (which will not always be the case, in particular when actions are nondeterministic). π is certainly only a first step towards a plan. We leave this issue to further research.

Example

How we can handle our running example in our logic? For the sake of readability, suppose d = 2 and t = 1. A meaningful valid plan is 3 We identify T with the conjunction of its elements.

Related work and conclusion

There is a significant amount of related work about the interactions between action and knowledge, both in the KR and the planning communities. Combining knowledge and action in a logical framework comes back to the work of [START_REF] Moore | A formal theory of knowledge and action[END_REF] who provided a theory of action including knowledge-producing actions. Building on this theory, [START_REF] Scherl | The frame problem and knowledge-producing actions[END_REF] represent knowledge-producing actions in the situation calculus by means of an explicit accessibility relation between situations, treated as an ordinary fluent, that corresponds to our epistemic accessibility relation. [START_REF] Levesque | What is planning in the presence of sensing?[END_REF] then uses this knowledge fluents to represent complex plans involving, like ours, nondeterminism, observations and branching (and also loops, that we did not consider). He points out that the executability of a plan requires that the agent needs to know how to execute it, which implies that branching conditions must involve knowledge and not objective facts whose truth may not be accessible to the agent. On the one hand, our logic, consisting of a fragment of propositional PDL extended with epistemic modalities to represent the effects of actions, is decidable, and furthermore the interactions between dynamic and epistemic modalities enable a simple representation of various observability assumptions; on the other hand, by using the situation calculus, Levesque handles more easily than us value tests returning the value of a variable (for instance, he is able to represent in a simple way a plan such as search Mary's phone number in the phonebook and then dial it whereas we cannot do it unless we write down a finite but unreasonable amount of propositional formulas). This approach was extended in [START_REF] Lakemeyer | AOL: a logic of acting, sensing, knowing, and only knowing[END_REF]) so as to introduce the only knowing modality. [START_REF] Bacchus | Modeling an agent's incomplete knowledge during planning and execution[END_REF] point out the practical impossibility to generate explicit conditional plans, because they get too large, and thus advocate for the need of reasoning about knowledge during plan execution, which is one of the key points of our logic. Their representation model makes use of an epistemic modality. Our approach could be thought of as being complementary to theirs, because we provide a simple way to represent various kinds of interactions between knowledge and action while they focus on the practical computation of the effects of a plan containing sensing actions and knowledge preconditions. [START_REF] Geffner | Modeling action, knowledge and control[END_REF] provide a general languuage enabling representing nondeterministic actions, sensing actions, observations and conditional plans. Their notion of executable policy is very similar to our notion of meaningful plan, though it is expressed the same way technically speaking: to avoid generating unreasonably large policies (which happens whenever all accessible belief states are explicitely considered), they express policies on states rather than on belief states; a policy is then said to be executable in a belief state Bel if, roughly speaking, it assigns equivalent actions to all states considered possible in Bel. We choose another way to escape repre-senting explicitly conditional plans, namely by calling for reasoning tasks during execution. [START_REF] Lobo | Adding knowledge to the action description language A[END_REF] extend Gelfond and Lifschitz' language A for reasoning about action so as to represent knowledge effects. An interesting notion in their approach is knowledge removing actions that may affect the knowledge the agent has on a fluent. These knowledge removing actions (such as toss) can be easily handled in EDL.

These approaches focus on representing actions and conditional plans involving knowledge preconditions and effects, and checking whether a given plan reaches the goal. Up to know, little has been done in order to generate plans having knowledge preconditions. [START_REF] Bonet | Planning and control in artificial intelligence: A unifying perspective[END_REF] have developed a general language which enables a high-level representation of Partially Observable Markov Decision Processes, which could probably be extended with reasoning tasks at run time. [START_REF] Rintanen | Constructing plans by a theorem prover[END_REF] extends the planning as satisfiability framework to planning under incomplete knowledge by means of Quantified Boolean Formulae. [START_REF] Boutilier | Computing optimal policies for partially observable decision processes using compact representations[END_REF] provide a propositional-like representation and resolution framework for POMDPs. None of these works makes use of epistemic nor dynamic modalities.

Lastly, a few authors developed logical systems integrating dynamic and epistemic modalities, but not from a planning perspective. [START_REF] Del Val | Qualitative reasoning about perception and belief[END_REF]) study from a logical perspective the relations between what the agent perceive and what they believe; this is much related to our logical expressions of observability assumptions in EDL. [START_REF] Fagin | Reasoning about knowledge[END_REF] have a language with temporal 'next' and 'always' operators instead of action operators. They have axioms of perfect recall similar to our Acq([α], K) (axioms KT1, KT2). They do not integrate a solution to the Frame Problem into their approach. Also slightly related to our work is [START_REF] Meyer | Test as epistemic updates[END_REF] who consider tests as epistemic updates.

Apart of the extension of EDL so as to deal with plan existence, further work includes the study of the complexity of validity for the full logic EDL (so far we only have a complexity result for plan verification in EDL) and next, the complexity of plan existence with epistemic preconditions, which would complete the panorama of complexity results for planning under incomplete knowledge [START_REF] Littman | Probabilistic planning: representation and complexity[END_REF] [START_REF] Baral | Computational complexity of planning and approximate planning in the presence of incompleteness[END_REF].

  Formally, we suppose given a dependency function DEP : ACT 0 -→ VAR. p ∈ DEP (α) means that α may change the truth value of the atom p. The other way round, if p ∈ DEP (α) then α does not change the truth value of p. In other words, DEP represents frame axioms in an economic way. This is expressed by the axiom P res DEP ([α]) if p ∈DEP (α) then p →[α]p and ¬p →[α]¬p Semantically, the axiom corresponds to the condition • For all w, w ∈ W and p ∈ VAR, if w ∈ R α (w) and p ∈ DEP (α) then |= M,w p iff |= M,w p.

π2, 1

 1 = listen(1); if Ktiger(1) then open(2) else open(1)Proving the validity of π 2,1 amounts to proving that the formula TΣ Init → [π 2,1 ](married ∧ alive) is a theorem, where the initial situation Σ Init is ΣInit = alive ∧ ((tiger(1) ∧ ¬tiger(2) ∧ princess(2))∨ (tiger(2) ∧ ¬tiger(1) ∧ princess(1)))and T is the nonlogical theory of the domain, consisting of the following set T of effect axioms 3 :T = { tiger(i) → [listen(i)]Ktiger(i), ¬tiger(i) → [listen(i)]K¬tiger(i), princess(i) → [open(i)]married, tiger(i) → [open(i)]¬alive, (¬princess(i) ∧ ¬married) → [open(i)]¬married, (¬tiger(i) ∧ alive) → [open(i)]alive, listen(i) , open(i) .(where we suppose i ∈ {1, 2}). Moreover, let DEP (listen(i)) = ∅ and DEP (open(i)) = {married, alive}. (The dependencebased solution to the Frame Problem requires the last two conditional frame axioms of T .) We establish that T ΣInit → [π2,1](married ∧ alive) by proving T (tiger(1) ∧ ¬tiger(2) ∧ princess(2) ∧ alive) → [π2,1](married ∧ alive) and T (tiger(2) ∧ ¬tiger(1) ∧ princess(1) ∧ alive) → [π2,1](married ∧ alive). Then the disjunction of the respective antecedens is nothing but Σ Init , and since (Ktiger(1) ∧[open(2)](alive ∧ married))∨ (K¬tiger(1) ∧ [open(1)](alive ∧ married)) is equivalent to [listen(1); if Ktiger(1) then open(2) else open(1)](alive ∧ married), putting things together we obtain what we wanted.

is a princess and no tiger. The agent has no prior knowledge about what is behind each of the doors (he only knows the values of d and t). The available actions are listening to what happens behind a given door, which results in hearing a tiger roaring iff there is one behind the door, and opening a given door, which results in marrying the princess or being eaten by the

	Example 1
	There are d doors. Behind exactly t of the doors, there
	is a tiger (t < d). Behind one (and only one) of the
	doors, there tiger or nothing, depending on what is behind the door.
	The goal of the agent is to stay alive and marry the
	princess.
	The propositional variables princess(i) and tiger(i)
	mean respectively that there is a princess (a tiger) be-
	hind door i. Consider the following plan
	π1: if princess(1)
	then open(1)
	else if princess(2)
	then open(2)
	else if princess(3)
	(...) else if princess(d) then open(d)

  All the axioms are standard, except Acq([α], K) which means that if the agent knows what will be true after an action then he does not loose this knowledge after the action. Note that Acq([α], K) could be replaced by K[α]C → [α]KC to which it is equivalent given the other axioms.

We shall sometimes identify RK and Rα with mappings RK : W -→

W and Rα : W -→ 2 W .

i.e. if ΣInit |= KA ∨ K¬A for all objective A

Acknowledgements Thanks to Philippe Balbiani for helpful discussions.