text:
# On the Radii of Close-in Giant Planets

## 1. Introduction

The recent indirect detections of extrasolar giant planets (EGPs) by Doppler spectroscopy have taught us that such planetary systems can be very much unlike our own. To date, nearly $``$30 EGPs have been discovered around stars with spectral types from M4 to F7 (e.g., Mayor & Queloz (1995); Marcy et al. 1999a ; Fischer et al.  (1999)). The planets themselves have minimum masses (Mp$`\mathrm{sin}(i)`$) between $``$0.42 M$`_\mathrm{J}`$and $``$10 M$`_\mathrm{J}`$, orbital semi-major axes from $``$0.042 A.U. to $``$3.8 A.U., and eccentricities as high as $``$0.71. Such variety vastly expands the parameter space within which both theorists and observers must operate in defining the physical character of extrasolar planetary systems.

The most interesting, unexpected, and problematic subclass of EGPs are those found within $``$0.1 A.U. of their primaries, 50–100 times closer than Jupiter is to our Sun. At such orbital distances, due to prodigious stellar irradiation alone, an EGP can have an effective temperature (T$`_{\mathrm{eff}}`$) greater than 600 K. Indeed, the EGPs HD187123b, HD209458b, $`\tau `$ Boo b, HD75289b, 51 Peg b, $`\upsilon `$ And b, and HD217107b likely all have Teffs above 1000 K. This is to be compared with Teffs for Jupiter and Saturn of 125 K and 95 K, respectively. The minimum masses of these close-in EGPs imply that they occupy the high-T$`_{\mathrm{eff}}`$/low-gravity corner of parameter space for which the compositions and composition profiles may be unique (Seager and Sasselov (1998); Goukenleuque et al.  (1999)).

However, high stellar fluxes on a close-in EGP can have profound structural consequences for the planet. In particular, stellar insolation can be responsible for maintaining the planet’s radius at a value 20% to 80% larger than that of Jupiter itself (Guillot et al.  (1996)). This prediction has recently been verified by the observation of the transit by HD209458b of its primary. The depth of the transit yields values for its radius that range from $``$1.27 R$`_\mathrm{J}`$(Charbonneau et al. 1999b ) to $``$1.7 R$`_\mathrm{J}`$(Henry et al.  (1999)), with a best value near $``$1.4 R$`_\mathrm{J}`$(Mazeh et al.  (2000)). Importantly, since HD209458b transits its primary, astronomers can derive $`\mathrm{sin}(i)`$, from which the planet’s mass can be directly determined. This is a major advance in the emerging study of extrasolar planets. In this paper, we focus on the HD209458 system and what broadly can be concluded theoretically from these new transit data. We do not provide detailed models from which one can extract bulk or atmospheric composition. Rather, we show that the large radius of HD209458b is a consequence of the retardation by stellar irradiation of the otherwise natural cooling of the convective core of the planet and that such a radius requires that the planet did not dwell for long, if at all, at large orbital distances after its formation. Hence, the large radius of a close-in EGP is not due to the thermal expansion of its atmosphere, but to the high residual entropy that remains throughout its bulk as a consequence of its early proximity to a luminous primary.

Recently, Cameron et al. (1999), using spectral deconvolution, claim to have seen $`\tau `$ Boo b in reflection. To investigate this exciting possibility, we calculate a range of theoretical radii for the $`\tau `$ Boötis planet. As we show, the Cameron et al. value of 1.6–1.8 R$`_\mathrm{J}`$for $`\tau `$ Boo b’s radius, if verified, is a challenge to the still embryonic theory of massive, close-in EGPs. Nevertheless, with the discovery of a transiting planet, HD209458b, with the maturation of the technique of spectral deconvolution, and with the anticipated development of adaptive optics and interferometry for the direct study of extrasolar planets (Angel (1994)), we are clearly entering a new phase in extrasolar planetary research.

## 2. A Summary of the Data

The transit of the F8V/G0V star HD209458 (at a distance of 47 parsecs) by HD209458b lasts $``$3 hours (out of a total period of 3.524 days) and has a depth of $``$1.5-2.0%. Its ingress and egress phases each last $``$25 minutes (Charbonneau et al. 1999b ; Henry et al.  (1999)). The properties of the planet, in particular its orbital distance and its radius, scale with the properties of the star and the most recent study of HD209458 was conducted in the context of these transits by Mazeh et al. (2000). They conclude from $`log\mathrm{g}`$/T$`_{\mathrm{eff}}`$spectral-line fits and $`M_V`$/$`(BV)`$ photometric fits that M= $`1.1\pm 0.1`$ M, R = $`1.2\pm 0.1`$ R, T$`_{\mathrm{eff}}`$$``$6000 K, \[Fe/H\]$``$0.0, $`t=5.5\pm 1.5`$ Gyr, and L$`{}_{}{}^{}2.0`$ L$`_{}`$. Mazeh et al. then derive for the planet: R$`_\mathrm{p}`$= 1.40$`\pm 0.17`$ R$`_\mathrm{J}`$, Mp= $`0.69\pm 0.05`$ M$`_\mathrm{J}`$($``$M$`{}_{}{}^{2/3}{}_{}{}^{}`$), $`i=86^{}.1\pm 1^{}.6`$, and $`a=0.047`$ A.U. ($``$M$`{}_{}{}^{1/3}{}_{}{}^{}`$). (All symbols have their standard meanings.)

Fuhrmann et al. (1998) provide parameters for the F7V star $`\tau `$ Boötis: M= $`1.42\pm 0.05`$ M, R = $`1.48\pm 0.05`$ R, T$`_{\mathrm{eff}}`$$``$6360 K, \[Fe/H\]$``$+0.27$`\pm `$0.08, $`t=1.0\pm 0.6`$ Gyr, and L$`{}_{}{}^{}3.2`$ L$`_{}`$. Its Hipparcos distance is $``$15.6 parsecs. With the Fuhrmann et al. mass for $`\tau `$ Boötis, Butler et al. (1997) would have obtained for its close-in EGP: Mp$`\mathrm{sin}(i)`$ = 4.33 M$`_\mathrm{J}`$, $`a0.049`$ A.U., and $`P=3.313`$ days. Charbonneau et al. (1999a) quote an upper limit at $``$4900Å of $`5\times 10^5`$ to the fraction of the star’s light reflected off the planet. Cameron et al. (1999) claim to have detected in the blue-green region of the spectrum a reflected fraction of $`1.9\pm 0.4\times 10^4`$. From the semi-amplitude ($``$74 km s-1) of the Doppler shift of this reflected fraction, they derive an orbital inclination ($`i`$) of 29, which would yield a mass for $`\tau `$ Boo b of $``$9 M$`_\mathrm{J}`$. From their reflected fraction, an orbital planetary phase function, and a geometric albedo ($`A_g`$) of 0.55 (similar to that of Jupiter in the visible), Cameron et al. obtain a radius for $`\tau `$ Boo b of 1.6–1.8 R$`_\mathrm{J}`$. If $`A_g`$ were smaller, the inferred radius of the planet would be larger ($`A_g^{1/2}`$).

## 3. The Radii of Close-in EGPs

By whatever processes giant planets are initially assembled, they must start out significantly larger than they end up. In isolation, they would cool inexorably due to radiation from their surfaces and shrink accordingly, just as does a protostar or a brown dwarf. Early on, due to the negative effective specific heat of an object in hydrostatic equilibrium supported by ideal gas pressure, energy loss results in an increase in its central temperature. However, the density increases more quickly and, as a consequence, the specific entropy ($`S`$) monotonically decreases. Since EGPs are almost fully convective (even if under significant stellar irradiation; Guillot et al.  (1996)), they are isentropes. This is an essential point. Given an EOS and a planetary mass, an EGP’s core entropy determines its radius (and its surface gravity). A large radius is a consequence of a large entropy.

As Zapolsky and Salpeter (1969) demonstrated for planets made of high-$`Z`$ material, any planet with a cold radius larger than $``$0.5 R$`_\mathrm{J}`$, must be made predominantly of hydrogen. Using the ANEOS equation of state tables (Thompson (1990)), we derive that an “olivine” (rock) or H2O (ice) planet with a mass of 0.69 M$`_\mathrm{J}`$has a radius of 0.31 R$`_\mathrm{J}`$or 0.45 R$`_\mathrm{J}`$, respectively. Importantly, these radii are 3–4 times smaller than observed for HD209458b and prove that HD209458b must be a hydrogen-rich gas giant; it cannot be a giant terrestrial planet or an ice giant such as Neptune or Uranus.

The rate with which an EGP shrinks is determined by the opacities in its outer radiative zone and the degree of stellar irradiation. If there were no radiative losses, the EGP would not shrink. In isolation, the energy loss rate and T$`_{\mathrm{eff}}`$are determined in the context of a self-consistent radiative/convective model and T$`_{\mathrm{eff}}`$is a function of only $`S`$ and Mp. (Note that, for a given metallicity, the surface gravity of the EGP is a function of $`S`$ and Mp alone.) The atmospheric flux in the outer skin determines the temperature profile at the boundary of the convective core and, hence, the rate of core entropy and radius decrease. According to theory (Saumon et al.  (1996); Burrows et al. 1995,1997), isolated EGPs shrink rapidly. A 1-M$`_\mathrm{J}`$EGP in isolation contracts below 2.0 R$`_\mathrm{J}`$in less than $`10^6`$ years. The theory depends upon the atmospheric opacities and metallicity and can reproduce the current Jupiter (Hubbard et al.  (1999)), but there still remain major uncertainties concerning grain and cloud formation (Lunine et al.  (1989)), rainout (Burrows and Sharp (1999)), gas-phase opacities (Burrows et al.  (1997)), and the depth of penetration of the stellar flux (Guillot et al.  (2000)). Hence, while the basic theory of EGP evolution is firm, the details are not and significant ambiguities in the variation of R$`_\mathrm{p}`$and T$`_{\mathrm{eff}}`$with age persist.

It is by altering the temperature/pressure profile of the atmosphere of an EGP that stellar irradiation can retard the evolution of the EGP’s core entropy and, hence, R$`_\mathrm{p}`$. Essentially, irradiation flattens the temperature profile at the top of the convective zone, while at the same time moving the radiative/convective boundary inward. The consequent growth of the radiative zone is a central feature of the large-radius phenomenon (Guillot et al.  (1996)). Since radiative fluxes are governed by the product of thermal diffusivities and temperature gradients and since the thermal diffusivity decreases with increasing pressure, the flux of energy out of the convective core and the rate of core entropy change are reduced. For close-in EGPs, T$`_{\mathrm{eff}}`$stabilizes early at large values, while the “effective” T$`_{\mathrm{eff}}`$of the core, where most of the heat and mass resides, is drastically lowered. The upshot is a retardation of the contraction of the planet. Large EGP radii are a consequence of such retardation, and not of the expansion of the outer envelope by stellar heating. This is easy to demonstrate by noting that the scale height of HD209458b’s atmosphere, under the assumption that T$`_{\mathrm{eff}}`$is between 1200 K and 1700 K, is only $``$1% of R$`_\mathrm{p}`$. Though the mapping between $`S`$ and R$`_\mathrm{p}`$is unaltered by irradiation, the mapping between $`S`$ and age can change significantly. Guillot et al. (1996) predicted this behavior for 51 Peg b, using a Bond albedo ($`A_B`$) of 0.35, obtaining R$`_\mathrm{p}`$’s of 1.1–1.3 R$`_\mathrm{J}`$after 8 Gyr. Scaling the results of that paper using the stellar flux on HD209458b and a mass of 0.69 M$`_\mathrm{J}`$, we obtain R$`_\mathrm{p}`$’s between 1.4 R$`_\mathrm{J}`$and 1.6 R$`_\mathrm{J}`$for ages between 10 and 3 Gyr, perfectly in line with the transit observations (§2). Figure 1 depicts two possible evolutionary trajectories for HD209458b, if born and fixed at 0.049 A.U. Also included on Figure 1 is a theoretical R$`_\mathrm{p}`$-$`t`$ trajectory for a 0.69-M$`_\mathrm{J}`$EGP in isolation. We have used for these calculations the formalisms of Guillot et al. (1995, 1996), Guillot and Morel (1995), and Burrows et al. (1997). Tidal and Roche effects have been ignored and are relevant only at very early ages ($`<`$$`10^4`$ yrs). Note, however, that despite its small orbital distance, HD209458b is beyond the Roche limit by a factor of $``$2.5 and is stable against loss both by thermal (Jeans) escape and non-thermal processes involving absorption of stellar UV flux (Trilling (1998)). A box of empirical ages and R$`_\mathrm{p}`$’s (Mazeh et al. 2000) is superposed.

As can be seen in Figure 1, there is a great difference between the theoretical radius of an isolated and an irradiated EGP. Importantly, since the scale-height effect is miniscule, the R$`_\mathrm{p}`$-$`t`$ trajectory of the isolated EGP (model I) immediately suggests that if HD209458b were allowed to dwell at large orbital distances ($``$0.5 A.U.) for more than a few $`\times 10^7`$ years, its observed radius could not be reproduced. As Figure 1 demonstrates, it is at such ages that the radius of an isolated 0.69-M$`_\mathrm{J}`$EGP falls below HD209458b’s observed radius. Note that for $``$0.5 A.U. the intrinsic luminosity of our isolated HD209458b model at such an age exceeds the amount of stellar light that would have been intercepted. Hence, stellar irradiation would have had little effect on this model. However, many orbital-distance/age histories can be contemplated and these will be the subject of a future work (Guillot et al.  (2000)). To reiterate, HD209458b could not have cooled off and achieved a radius or an entropy like that of Jupiter and then moved in. If it migrated, it had to have moved in early in its life. The radius of a close-in EGP depends upon its history (and the history of the star); large radii require early proximity to a central star. This fact provides an upper limit to the timescale of planetary migration, if migration did indeed occur (Trilling et al.  (1998)): conservatively, HD209458b dwelled less than a few$`\times 10^7`$ years at more than 0.5 A.U.

The actual evolution of a close-in EGP’s radius depends upon its Bond albedo (Marley et al.  (1999); Seager and Sasselov (1998); Sudarsky, Burrows, and Pinto (1999)), the level of any clouds formed and their optical depths, the gas-phase abundances and opacities, the helium and metallicity fractions, the H-He EOS (Saumon, Chabrier, & Van Horn (1995); Saumon et al.  (1999)), the depth of stellar flux penetration, and the primary star. In a later paper (Guillot et al.  (2000)), we explore these effects and conduct a detailed parameter study. A range of trajectories similar to those depicted in Figure 1 are still possible and when data on the HD209458b transit and primary star are further refined, theorists may well be able to sharply constrain the character of HD209458b’s atmosphere and composition.

### 3.1. Theoretical Radius for $`\tau `$ Boo b

We provide in Figure 1 two representative theoretical R$`_\mathrm{p}`$-$`t`$ trajectories for $`\tau `$ Boo b, along with an error box constructed using Cameron et al. (1999) and Fuhrmann et al. (1998). Depending upon L and its Bond albedo, which might vary from $``$0.0 to perhaps 0.6, $`\tau `$ Boo b’s T$`_{\mathrm{eff}}`$is between 1350 K and 1750 K. These Teffs are higher than those corresponding to HD209458b and reflect $`\tau `$ Boötis’ higher L. Due to uncertainties in the relative position of the silicate and iron cloud decks and the region of neutral alkali metals, there are still uncertainties in the atmospheric composition and albedos of such an EGP (Marley et al.  (1999); Sudarsky, Burrows, and Pinto (1999)). A high Bond albedo might be a consequence of the presence at altitude of reflecting clouds. Without these clouds, both the Bond albedo and the geometric albedo in the blue-green region of the planetary spectrum would be low, perhaps below 0.1. A low geometric albedo would put the measured radius of $`\tau `$ Boo b even higher than the range quoted by Cameron et al. . As the evolutionary models on Figure 1 suggest, though a lower Bond albedo results in a larger R$`_\mathrm{p}`$at a given age, the R$`_\mathrm{p}`$-$`t`$ error box for $`\tau `$ Boo b given in Figure 1 still seems out of reach. Note that a 9-M$`_\mathrm{J}`$$`\tau `$ Boo b model in isolation achieves a radius of 1.6 R$`_\mathrm{J}`$within a scant 5 Myr and that at 1 Gyr such a model has a radius of 1.1 R$`_\mathrm{J}`$.

The early radii of $`\tau `$ Boo b shown on Figure 1 are so much smaller than those of HD209458b because of the larger inferred mass of $`\tau `$ Boo b and the particular choice of opacity data used for these exploratory models. Other opacity databases would give quantitatively different radius-age trajectories early on, but would not alter the conclusion that the theoretical radius of a massive planet at late times ($`>`$ few$`\times 10^7`$ years) is significantly below the $`\tau `$ Boo b error box shown in Figure 1. Furthermore, under the assumptions that the Bond albedo is zero, that there is no outer radiative zone, and that the atmosphere and core of the planet have the same entropy, we can obtain a strong upper bound to the radius of a planet of a given age and mass (Guillot et al. 1996). For $`\tau `$ Boo b, this radius is 1.58 R$`_\mathrm{J}`$for 7 M$`_\mathrm{J}`$and 1.48 R$`_\mathrm{J}`$for 10 M$`_\mathrm{J}`$, both below the quoted radius range. Hence, we have difficulty fitting the Cameron et al. (1999) reflection data. In particular, despite significant irradiation, the large planetary mass measured by Cameron et al. (7-10 M$`_\mathrm{J}`$) results in rapid early contraction. If the Bond albedo is lower, the theoretical $`\tau `$ Boo b radius for an age near 1 Gyr would be larger, but the measured radius would also be larger.

## 4. The Effects of the Equation of State

Our cooling calculations use the hydrogen/helium EOS of Saumon, Chabrier, and Van Horn (1995, SCVH). Recent shock-compression experiments on deuterium (Holmes, Ross, and Nellis (1995); Da Silva et al.  (1997); Collins et al.  (1998)) show that this EOS underestimates the degree of molecular dissociation for pressures in the range $`0.1<P<2`$Mbar. However, by softening the repulsive part of the H2–H and H–H potentials, the EOS of SCVH can be made to reproduce all experimental results (Saumon et al.  (1999)). Since adiabats of hot Jupiters computed with the modified EOS are systematically cooler and denser than those of SCVH by up to 6% in $`T`$ and 10% in $`\rho `$, such changes in the EOS will reduce the theoretical radius of HD209458b by only a few percent, while modifying the corresponding quantity for $`\tau `$ Boo b by a negligible amount.

## 5. Atmospheric Transmission and Refraction

Details of the transit lightcurve depend upon the distribution of slant optical depth, as determined by molecular opacity and cloud layers, and, to a lesser extent, on refractive redistribution of the stellar surface brightness by the planetary atmosphere.

We use a theory to compute refractive effects that is essentially identical to that of the standard theory for occultations of stars by planetary atmospheres (Hubbard, Yelle, and Lunine (1990)) and have calculated the stellar brightness distribution for the transit of a planet with a radius equal to 1.4 RJ and a hot solar-composition atmosphere. The slant optical depth $`\tau `$ is computed for molecular opacity sources (with and without clouds) and at a variety of wavelengths. The effective radius of the planet, as determined by fitting the transit lightcurve, will depend upon the gas-phase opacity, the molecular composition, and the location of the optically-thick cloud layers (Seager and Sasselov (1999)). It will also be a diagnostic function of wavelength. Our preliminary calculations for cloud-free models indicate that $`|\mathrm{\Delta }R_\mathrm{p}/R_\mathrm{p}|`$ between 4500 Å and 6500 Å might be as much as 3%, smaller ($``$0.5%) if the alkali metals are important. Using a simple model for silicate cloud growth (Lunine et al.  (1989); Marley et al.  (1999)), we find a cloud base for HD209458b between $`10^2`$ and 0.4 bars and grain particle sizes between 1 and 100 microns. While for cloud models the wavelength dependence is muted, since the opacity varies strongly with particle size, there exists the possibility of remote sensing of cloud properties with high-precision measurements of upcoming transits (Hubbard et al.  (2000)).

## 6. Conclusions

Our theoretical calculations allow us to draw several specific conclusions:

1. HD209458b is a real object, made predominantly of hydrogen.
2. HD209458b’s radius is a consequence of the retardation of contraction by stellar irradiation and is not due to atmospheric expansion by stellar heating.
3. A large radius such as that of HD209458b requires early proximity to its central star.

Curiously, given L, $`a`$, and R$`_\mathrm{p}`$, HD209458b’s total luminosity is $`1.5\times 10^4`$ L$`_{}`$, about twice that of a star with $``$100 times the mass at the very bottom of the stellar main sequence. Given the large inferred mass of $`\tau `$ Boo b, its large radius is less easy to explain theoretically. However, the inherent difficulties of close-in EGP modeling may yet be responsible for theoretical surprises of a qualitative nature.

We thank Tim Brown, David Charbonneau, Geoff Marcy, Michel Mayor, Sara Seager, Richard Freedman and Jim Liebert for many useful discussions and for the use of data in advance of publication. This work was supported in part by NASA grants NAG5-7499, NAG5-7073, NAG5-4214, NAG5-7211, NAG2-6007, NAG5-4988, and NAG5-4987, as well as by an NSF CAREER grant (AST-9624878) to M.S.M.


format: text

text:
# On the Tractable Counting of Theory Models and its Application to Belief Revision and Truth Maintenance

## Introduction

Knowledge compilation has been emerging recently as a new direction of research for dealing with the computational intractability of general propositional reasoning (??). According to this approach, the reasoning process is split into two phases: an off-line compilation phase and an on-line query-answering phase. In the off-line phase, the propositional theory is compiled into some target language, which is typically a tractable one. In the on-line phase, the compiled target is used to efficiently answer a (potentially) exponential number of queries. The main motivation behind knowledge compilation is to push as much of the computational overhead as possible into the off-line phase, in order to amortize that overhead over all on-line queries.

One of the key aspects of any compilation approach is the target language into which the propositional theory is compiled. Previous compilation approaches have proposed Horn theories, prime implicates/implicants, and ordered binary decision diagrams (OBDDs) as targets for such compilation (?????). A more recent compilation target language is decomposable negation normal form (DNNF) (???). DNNF is universal; supports a rich set of polynomial-time operations; is more space–efficient than OBDDs (?); and is very simplistic as far as its structure and algorithms are concerned. Propositional theories in DNNF are highly tractable (?):

1. Deciding the satisfiability of a DNNF can be done in linear time.
2. Conjoining a DNNF with a set of literals can be done in linear time.
3. Projecting a DNNF on some atoms can be done in linear time. Intuitively, to project a theory on a set of atoms is to compute the strongest sentence entailed by the theory on these atoms.
4. Computing the minimum–cardinality of a DNNF can be done in linear time. The cardinality of a model is the number of atoms that are set to false in the model. The minimum–cardinality of a theory is the minimum–cardinality of any of its models.
5. Minimizing a DNNF can be done in quadratic time. To minimize a theory is to produce another theory which models are exactly the minimum-cardinality models of the original theory.
6. Enumerating the models of a DNNF can be done in time linear in its size and quadratic in the number of its models.

This paper rests on two key contributions. First, we show that DNNF representations scale as well as OBDD representations (?) by presenting a linear-time algorithm for converting an OBDD representation of a propositional theory into an equivalent DNNF representation. Second, we identify a subclass of DNNF, which we call deterministic DNNF, d-DNNF, and present a new linear-time operation for counting its models under the assertion, retraction and flipping of literals. In particular, we show how to traverse a d-DNNF only twice and yet compute: its number of models under the assertion, retraction and flipping of each literal. This allows us to test in linear time: the consistency of the d-DNNF under the assertion, retraction and flipping of each literal, therefore, allowing us to implement linear-time, complete truth maintenance and belief revision systems.

What is interesting though is that two of our key complexity results with respect to DNNF compilations continue to hold with respect to the subclass of d-DNNF. This includes a structure-based algorithm which can compile any CNF into an equivalent DNNF in linear time given that the treewidth of the CNF is bounded (?). It also includes the newly proposed algorithm for converting any OBDD into an equivalent DNNF in linear time.

This paper is structured as follows. We first review DNNF, introduce the class of deterministic DNNF and then discuss the new operation for model counting. We follow that by discussing the application of this counting operation to truth maintenance, belief revision, and model-based diagnosis systems. We finally close with some concluding remarks. Proofs of all results are available in the full paper (?).

## Deterministic DNNF

A propositional sentence is in negation normal form (NNF) if it is constructed from literals using only the conjoin and disjoin operators. Figure 1 shows a sentence in NNF depicted as a rooted, directed acyclic graph where the children of each node are shown below it in the graph. Each leaf node represents a literal and each non-leaf node represents a conjunction or a disjunction. We allow $`\mathrm{𝗍𝗋𝗎𝖾}`$ and $`\neg \mathrm{𝖿𝖺𝗅𝗌𝖾}`$ to appear as leaves in a DNNF to denote a conjunction with no conjuncts. Similarly, we allow $`\mathrm{𝖿𝖺𝗅𝗌𝖾}`$ and $`\neg \mathrm{𝗍𝗋𝗎𝖾}`$ as leaves to represent a disjunction with no disjuncts. The size of an NNF is measured by the number of edges in its graphical representation. Our concern here is mainly with a subclass of NNFs:

###### Definition 1

(?) A decomposable negation normal form (DNNF) is a negation normal form satisfying decomposability property: for any conjunction $`_i\alpha _i`$ appearing in the form, no atom is shared by any pair of conjuncts in $`_i\alpha _i`$.

The NNF $`(AB)(\neg AC)`$ is not decomposable since atom $`A`$ is shared by the two conjuncts. But the NNF in Figure 1 is decomposable. It has ten conjunctions and the conjuncts of each share no atoms. Decomposability is the property which makes DNNF tractable.

One of the key operations on DNNF is that of conditioning:

###### Definition 2

(?) Let $`\alpha `$ be a propositional sentence and let $`\gamma `$ be an instantiation.111An instantiation of a set of atoms is a conjunction of literals, one literal for each atom in the set. The conditioning of $`\alpha `$ on $`\gamma `$, written $`\alpha \gamma `$, is the sentence resulting from replacing each atom $`p`$ in $`\alpha `$ with $`\mathrm{𝗍𝗋𝗎𝖾}`$ if the +ve literal $`p`$ appears in $`\gamma `$ and with $`\mathrm{𝖿𝖺𝗅𝗌𝖾}`$ if the -ve literal $`\neg p`$ appears in $`\gamma `$.

For example, conditioning the DNNF $`(\neg A\neg B)(BC)`$ on instantiation $`BD`$ gives $`(\neg A\neg \mathrm{𝗍𝗋𝗎𝖾})(\mathrm{𝗍𝗋𝗎𝖾}C)`$ and conditioning it on $`\neg BD`$ gives $`(\neg A\neg \mathrm{𝖿𝖺𝗅𝗌𝖾})(\mathrm{𝖿𝖺𝗅𝗌𝖾}C)`$. Conditioning is a key operation because it allows us to conjoin a DNNF $`\mathrm{\Delta }`$ with some instantiation $`\alpha `$ (which may share atoms with $`\mathrm{\Delta }`$) while ensuring that the result is also a DNNF. Specifically, $`(\mathrm{\Delta }\alpha )\alpha `$ is a DNNF which is equivalent to $`\mathrm{\Delta }\alpha `$ and can be computed in time linear in the size of $`\mathrm{\Delta }`$.

We now introduce the class of deterministic DNNF:

###### Definition 3

A deterministic DNNF (d-DNNF) is a DNNF satisfying the following property: for any disjunction $`_i\alpha _i`$ appearing in the form, every pair of disjuncts in $`_i\alpha _i`$ are disjoint.

For example, $`(AB)C`$ is a DNNF but is not deterministic since the disjuncts $`AB`$ and $`C`$ are not disjoint. However, the DNNF $`(AB)(\neg AC)`$ is deterministic. Note that although every DNF is a DNNF, not every DNF is a d-DNNF.

The main value of d-DNNF is the ability to count its models in linear time and under the assertion, retraction and flipping of literals. Such operations will be discussed in the following section. In the remainder of this section we present two results that hold for DNNF, but continue to hold for d-DNNF. The first is a structure-based algorithm that we introduced in (?) for converting a CNF into a DNNF. The algorithm utilizes a decomposition tree, which is a binary tree the leaves of which correspond to the CNF clauses—see Figure 2. Each decomposition tree has a width and the complexity of the algorithm is exponential only in the width of used tree. The algorithm is given with a slight modification in Figure 3. The only difference between this version and the one in (?) is that we have $`\mathrm{cl2ddnnf}(\mathrm{𝑐𝑙𝑎𝑢𝑠𝑒}(N)\alpha )`$ instead of $`\mathrm{𝑐𝑙𝑎𝑢𝑠𝑒}(N)\alpha `$, therefore, converting a clause to a d-DNNF at the boundary condition.

###### Theorem 1

(?) Let $`N`$ be the root of decomposition tree $`T`$ used in Figure 3. Then $`\mathrm{cnf2ddnnf}(N,\alpha )`$ will return $`\mathrm{\Delta }\alpha `$ in DNNF, where $`\mathrm{\Delta }`$ contains the clauses attached to the leaves of $`T`$. Moreover, the time and space complexity of the algorithm is $`O(nw2^w)`$, where $`n`$ is the number of clauses in $`\mathrm{\Delta }`$ and $`w`$ is the width of decomposition tree $`T`$.

###### Theorem 2

The DNNF returned by the algorithm in Figure 3 is deterministic.

The class of CNF theories with bounded treewidth is defined in (?), where it is shown that, for this class of theories, one can construct in linear time a decomposition tree of bounded width. Therefore, one can compile a d-DNNF of linear size for this class of theories.

Binary decision diagrams (BDDs) are among the most successful representations of propositional theories (?). Two special classes of BDDs, OBDDs and FBDDs, are especially popular given (??):

the number of linear-time operations they support and

the number of real-world theories that admit efficient OBDD/FBDD representations.

We now present a linear-time algorithm for converting an FBDD into an equivalent d-DNNF, showing that d-DNNFs scale as well as FBDDs (which include OBDDs as a subclass). We start by the formal definitions of BDDs, OBDDs, and FBDDs.

###### Definition 4

A binary decision diagram (BDD) over a set of binary variables $`X=\{x_1,\mathrm{},x_n\}`$ is a directed acyclic graph with one root and at most two leaves labeled $`0`$ and $`1`$. Each non-leaf node $`m`$ is labeled by a variable $`\mathrm{𝑣𝑎𝑟}(m)X`$ and has two outgoing edges labeled $`0`$ and $`1`$, where $`\mathrm{𝑙𝑜𝑤}(m)`$ and $`\mathrm{ℎ𝑖𝑔ℎ}(m)`$ denote the nodes pointed to by these edges, respectively. The computation path for input $`(a_1,\mathrm{},a_n)`$, where $`a_i\{0,1\}`$, is defined as follows. One starts at the root. At inner node $`m`$, where $`\mathrm{𝑣𝑎𝑟}(m)=x_i`$, one moves to node $`\mathrm{𝑙𝑜𝑤}(m)`$ if $`a_i=0`$ and to node $`\mathrm{ℎ𝑖𝑔ℎ}(m)`$ otherwise. The BDD represents the Boolean function $`f`$ if the computation path for each input $`(a_1,\mathrm{},a_n)`$ leads to the leaf node labeled with $`f(a_1,\mathrm{},a_n)`$.

The size of a BDD is measured by the number of nodes it contains.

###### Definition 5

A binary decision diagram is called a free BDD (FBDD) if on each computation path each variable is tested at most once. A free BDD is called an ordered BDD (OBDD) if on each computation path the variables are tested in the same order.

OBDDs are a strict subclass of FBDDs (?) and have received much consideration in the verification literature, where they are used to test the equivalence between the specs of a Boolean function and its circuit implementation. OBDDs/FBDDs permit such a test to be performed in polynomial time. Their popularity stems from the existence of efficient OBDD/FBDD representations of many complex, real-world propositional theories. DNNF is more space-efficient than FBDDs (?), but this should not be surprising as FBDDs admit more linear-time operations than does DNNF. For example, the equivalence of two DNNFs cannot be decided in polynomial time while it can for FBDDs.

Figure 4 depicts a recursive algorithm for converting an FBDD into a DNNF, showing that DNNFs scale as well as FBDDs. The algorithm should be called on the root of given FBDD:

###### Theorem 3

(?) The algorithm of Figure 4 takes time linear in the size of given FBDD and returns a DNNF of the theory represented by the given FBDD.

###### Theorem 4

The DNNF returned by the algorithm of Figure 4 is deterministic.

This has major implications on our reported results regarding truth maintenance and belief revision systems, as it proves, constructively, that we can build efficient truth maintenance and belief revision systems for any propositional theory which has an efficient FBDD representation. Figure 5 depicts an FBDD and its corresponding d-DNNF as generated by the algorithm of Figure 4.

## Counting Models of d-DNNF

We now turn to an operation on d-DNNF which is of major significance to a number of AI applications, including belief revision, truth maintenance and diagnosis. Specifically, given a d-DNNF $`\mathrm{\Delta }`$ and a set of literals $`𝐒`$, we describe two traversal operations each taking linear time. By the end of the first traversal, we will be able to count the models of $`\mathrm{\Delta }𝐒`$. By the end of the second traversal, we will be able to count the models of:

1. $`\mathrm{\Delta }𝐒\{l\}`$ for every literal $`l𝐒`$;
2. $`\mathrm{\Delta }𝐒\{l\}`$ for every literal $`l𝐒`$;
3. $`\mathrm{\Delta }𝐒\{l\}\{\neg l\}`$ for every literal $`l𝐒`$.

That is, once we traverse the d-DNNF twice, we will be able to obtain each of these counts using constant-time, lookup operations. As we shall see in the following section, these counts are all we need to implement an interesting number of AI applications.

The traversal will not take place on the d-DNNF itself, but on a secondary structure that we call the counting graph. Without loss of generality, we will assume from here on that the d-DNNF is smooth:

###### Definition 6

A DNNF is smooth iff

1. every literal and its negation appear in the DNNF;
2. for any disjunction $`_i\alpha _i`$ in the DNNF, we have $`\mathrm{𝑎𝑡𝑜𝑚𝑠}(_i\alpha _i)=\mathrm{𝑎𝑡𝑜𝑚𝑠}(\alpha _i)`$ for every $`\alpha _i`$.

The d-DNNF in Figure 1 is smooth as it satisfies these two conditions. We can easily make a DNNF smooth using two operations:

1. If the negation of literal $`l`$ does not appear in the DNNF, replace the occurrence of $`l`$ with $`l(\neg l\mathrm{𝖿𝖺𝗅𝗌𝖾})`$;
2. For each disjunction $`_i\alpha _i`$, replace the disjunct $`\alpha _i`$ with $`\alpha _i_{A\mathrm{\Sigma }}(A\neg A)`$, where $`\mathrm{\Sigma }`$ are the atoms appearing in $`_i\alpha _i`$ but not in $`\alpha _i`$.

These operations preserve both the decomposability and determinism of a DNNF. They may increase the size of given DNNF but only by a factor of $`O(n)`$, where $`n`$ is the number of atoms in the DNNF. This increase is quite minimal in practice though. Note that the d-DNNFs generated by the algorithm of Figure 4 satisfy the first condition; and the d-DNNFs generated by the algorithm of Figure 3 satisfy the second condition as long as $`\mathrm{cl2ddnnf}(\mathrm{𝑐𝑙𝑎𝑢𝑠𝑒}(N)\alpha )`$ satisfies some simple conditions; see (?).

The counting graph of a d-DNNF is a function of many variables represented as a rooted DAG.

###### Definition 7

The counting graph of a smooth d-DNNF is a labeled, rooted DAG. It contains a node labeled with $`l`$ for each literal $`l`$, a node labeled with $`+`$ for each or-node, and a node labeled with $``$ for each and-node in the d-DNNF. There is an edge between two nodes in the counting graph iff there is an edge between their corresponding nodes in the d-DNNF.

Figure 6 depicts the counting graph of the d-DNNF in Figure 1. The size of a counting graph is therefore equal to the size of its corresponding d-DNNF. We will see now how such a graph can be used to perform the counting operations we are interested in.

###### Definition 8

The value of a node $`N`$ in a counting graph under a set of literals $`𝐒`$ is defined as follows:

* $`\mathrm{val}(N)=0`$ if $`N`$ is labeled with literal $`l`$ and $`\neg l𝐒`$;
* $`\mathrm{val}(N)=1`$ if $`N`$ is labeled with literal $`l`$ and $`\neg l𝐒`$;
* $`\mathrm{val}(N)=_i\mathrm{val}(N_i)`$ if $`N`$ is labeled with $``$, where $`N_i`$ are the children of $`N`$;
* $`\mathrm{val}(N)=_i\mathrm{val}(N_i)`$ if $`N`$ is labeled with $`+`$, where $`N_i`$ are the children of $`N`$.

The value of a counting graph $`G`$ under literals $`𝐒`$, written $`G(𝐒)`$, is the value of its root under $`𝐒`$.

Here’s our first counting result.

###### Theorem 5

Let $`\mathrm{\Delta }`$ be a smooth d-DNNF, $`𝐒`$ be a set of literals, and let $`G`$ be the counting graph of $`\mathrm{\Delta }`$. The value of $`G`$ under $`𝐒`$ is the number of models of $`\mathrm{\Delta }𝐒`$:

$$G(𝐒)=\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒).$$

Note that $`G(𝐒)>0`$ iff $`\mathrm{\Delta }𝐒`$ is consistent. Therefore, by traversing the counting graph once we can test the consistency of d-DNNF $`\mathrm{\Delta }`$ conjoined with any set of literals $`𝐒`$. Figure 6 depicts the counting graph of d-DNNF $`\mathrm{\Delta }`$ in Figure 1, evaluated under the literals $`𝐒=A,\neg B`$. This indicates that $`\mathrm{\Delta }\{A,\neg B\}`$ has two models.

We now present the central result in this paper. First, we note that when viewing a counting graph $`G`$ as a function of many variables, we will use $`V_l`$ to denote the variable (node) which corresponds to literal $`l`$. Second, we can talk about the partial derivative of $`G(𝐒)`$ with respect to any of its variables $`V_l`$, $`G(𝐒)/V_l`$. Due to the decomposability of d-DNNF, the function $`G(𝐒)`$ is linear in each of its variables. Therefore, the change to the count $`G(𝐒)`$ as a result of adding, removing or flipping a literal in $`𝐒`$ can be obtained from the partial derivatives, without having to re-evaluate the counting graph $`G`$. This leads to the following consequential result:

###### Theorem 6

Let $`\mathrm{\Delta }`$ be a smooth d-DNNF, $`𝐒`$ be a set of literals, and let $`G`$ be the counting graph of $`\mathrm{\Delta }`$. We have:

When $`l,\neg l𝐒`$:

$$\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{l\})=G(𝐒)/V_l.$$

When $`l𝐒`$:

$$\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{l\})=G(𝐒)/V_l+G(𝐒)/V_{\neg l}.$$

When $`l𝐒`$:

$`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{l\}\{\neg l\})`$
$`=`$ $`G(𝐒)G(𝐒)/V_l+G(𝐒)/V_{\neg l}.`$
Therefore, if we can compute the partial derivative of $`G(𝐒)`$ with respect to each of its variables, then we can count the models of $`\mathrm{\Delta }𝐒`$ under the assertion of new literals not in $`𝐒`$, and under the retraction or flipping of literals in $`𝐒`$. Figure 7 depicts the value of each of these partial derivatives for the d-DNNF in Figure 1. The counting graph is evaluated under literals $`𝐒=A,\neg B,C`$ and the partial derivatives are shown below each variable. According to these derivatives, we have:

$`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{D\})=1`$ and $`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{\neg D\})=0`$. This immediately tells us that $`\mathrm{\Delta }𝐒D`$.

$`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{A\})=1+1=2`$; $`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{\neg B\})=1+1=2`$; and $`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{C\})=1+1=2`$. Therefore, retracting any literal in $`𝐒`$ increases the number of models to $`2`$.

$`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{A\}\{\neg A\})=11+1=1`$; $`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{\neg B\}\{B\})=11+1=1`$; $`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{C\}\{\neg C\})=11+1=1`$. Therefore, flipping any literal in $`𝐒`$ will not change the number of models (although it does change the model itself).

There is one missing link now: How do we compute the partial derivatives of a counting graph with respect to each of its variables? This actually turns out to be easy due to results in (??) which show how to evaluate and simultaneously compute all partial derivatives of a function by simply traversing its computation graph in linear time. Although (?) casts such computation in terms of summing weights of paths in such a graph, we present a more direct implementation here. In particular, if we let $`\mathrm{pd}(N)`$ denote the partial derivative of $`G(𝐒)`$ with respect to a node $`N`$ in the counting graph, then $`\mathrm{pd}(N)`$ is the summation of contributions made by parents $`M`$ of $`N`$:

$`\mathrm{pd}(N)`$ $`=`$ $`\{\begin{array}{cc}1,\hfill & \text{N is the root node;}\hfill \\ {\displaystyle \underset{M}{}}\mathrm{cpd}(M,N),\hfill & \text{otherwise;}\hfill \end{array}`$
where the contribution of parent $`M`$ to its child $`N`$ is computed as follows:

$$\mathrm{cpd}(M,N)=\{\begin{array}{cc}\mathrm{pd}(M),\hfill & M\text{ is a }+\text{node;}\hfill \\ \mathrm{pd}(M)\underset{KN}{}\mathrm{val}(K),\hfill & M\text{ is a }\text{node;}\hfill \end{array}$$

where $`K`$ is a child of $`M`$. This computation can be performed by first traversing the counting graph once to evaluate it, assigning $`\mathrm{val}`$ to each node $`N`$, and then traversing it a second time, assigning $`\mathrm{pd}`$ for each node $`N`$. We are then mainly interested in $`\mathrm{val}(N)`$ where $`N`$ is the root node, and $`\mathrm{pd}(N)`$ where $`N`$ is a leaf node.

Therefore, both the value of a counting graph under some literals $`𝐒`$ and the values of each of its partial derivatives under $`𝐒`$ can be computed by traversing the graph twice. Once to compute the values, and another to compute the partial derivatives. Note that such traversal needs to be redone once the set of literals $`𝐒`$ changes.

We close this section by pointing out that partial differentiation turns out to play a key role in probabilistic reasoning as well. Specifically, we present a comprehensive framework for probabilistic reasoning in (?) based on compiling a Bayesian network into a polynomial and then reducing a large number of probabilistic queries into the computation of partial derivatives of the compiled polynomial.

## Complete, Linear-Time Truth Maintenance

We now turn to some applications of the results in the previous section. That is, what can we do once we are able to count models under the conditions stated above?

We first consider truth maintenance systems and show how our results allow us to implement complete truth maintenance systems which take linear time on two important classes of propositional theories: those with bounded treewidth, and those admitting a linear FBDD representation. For each class of such theories, we can compile a smooth d-DNNF $`\mathrm{\Delta }`$ in linear time and then use it for truth maintenance as follows.222We are assuming that smoothing a d-DNNF does not increase its size by more than a constant factor.

A truth maintenance system takes a set of clauses $`\mathrm{\Gamma }`$ and a set of literals $`𝐒`$ and tries to determine for each literal $`l`$ whether $`\mathrm{\Gamma }𝐒l`$. The most common truth maintenance system is the one based on closing $`\mathrm{\Gamma }𝐒`$ under unit resolution (?). Such a system takes linear time, but is incomplete. Given that the set of literals in $`𝐒`$ changes to $`𝐒^{}`$, the goal of a truth maintenance system is then to update the truth of each literal under the new “context” $`𝐒^{}`$. Sometimes, clauses in $`\mathrm{\Gamma }`$ are retracted and/or asserted. A truth maintenance system is expected to update the truth of literals under such clausal changes too.

Our model-counting results allow us to implement a complete truth maintenance system as follows. We compile the theory $`\mathrm{\Gamma }`$ into a smooth d-DNNF $`\mathrm{\Delta }`$ and construct the counting graph $`G`$ of $`\mathrm{\Delta }`$. Given any set of literal $`𝐒`$, we evaluate $`G`$ under $`𝐒`$ and compute its partial derivatives also under $`𝐒`$. This can be done in time linear in the size of $`\mathrm{\Delta }`$. We are now ready to answer all queries expected from a truth maintenance system by simple, constant-time, look-up operations:

Literal $`l`$ is entailed by $`\mathrm{\Delta }𝐒`$ iff $`\mathrm{\Delta }𝐒\{\neg l\}`$ has no models: $`G(𝐒)/V_{\neg l}=0`$.

Retracting literal $`l`$ from $`𝐒`$ will render $`\mathrm{\Delta }𝐒`$ consistent iff $`\mathrm{\Delta }𝐒\{l\}`$ has at least one model: $`G(𝐒)/V_l+G(𝐒)/V_{\neg l}>0`$.

Flipping literal $`l`$ in $`𝐒`$ will render $`\mathrm{\Delta }𝐒`$ consistent iff $`\mathrm{\Delta }𝐒\{l\}\{\neg l\}`$ has at least one model: $`G(𝐒)G(𝐒)/V_l+G(𝐒)/V_{\neg l}>0`$. 333Note that the flipping of literals is outside the scope of classical truth maintenance systems in the sense that they must retract $`l`$ and then assert $`\neg l`$, taking linear time, to perform the above operation.

If we want to reason about the assertion/retraction of clauses in theory $`\mathrm{\Gamma }`$, we can replace each clause $`\alpha `$ in $`\mathrm{\Gamma }`$ by $`C_\alpha \alpha `$, where $`C_\alpha `$ is a new atom that represents the truth of clause $`\alpha `$. We then compile the extended theory $`\mathrm{\Gamma }`$ into d-DNNF $`\mathrm{\Delta }`$. To assert all clauses initially, we have to include all atoms $`C_\alpha `$ in the set of literals $`𝐒`$. The assertion/retraction of clauses can then be emulated by the assertion/retraction of atoms $`C_\alpha `$. For example, in case of a contradiction, we can ask whether removing a clause $`\alpha `$ will resolve the contradiction by asking whether $`\mathrm{\Delta }𝐒\{C_\alpha \}`$ has more than one model:

$$G(𝐒)/V_{C_\alpha }+G(𝐒)/V_{\neg C_\alpha }>0.$$

.

## Complete, Linear-Time Belief Revision

We now turn to a second major application of model counting on d-DNNF: the implementation of a very common class of belief revision systems, which is adopted in model-based diagnosis and in certain forms of default reasoning. The problem here is as follows. We have a set of special atoms $`𝐃=\{d_1,\mathrm{},d_n\}`$ in the theory $`\mathrm{\Gamma }`$ which represent defaults. Typically, we assume that all of these defaults are true, allowing us to draw some default conclusions. We then receive some evidence $`𝐒`$ (a set of literals) which is inconsistent with $`\mathrm{\Gamma }𝐃`$. We therefore know that not all defaults are true and some must be retracted—that is, some $`d_i`$s will have to be replaced by $`\neg d_i`$ in $`𝐃`$. Our goal then is to identify a set of literals $`𝐃^{}`$ such that

1. $`d_i𝐃^{}`$ or $`\neg d_i𝐃^{}`$ for all $`i`$;
2. $`\mathrm{\Gamma }𝐃^{}𝐒`$ is consistent;
3. the number of negative literals in $`𝐃^{}`$ is minimized;

and then then report the truth of every literal under the new set of defaults $`𝐃^{}`$. Note that there may be more than one set of defaults $`𝐃^{}`$ that satisfies the above properties. In such a case, a literal holds after the revision process only if it holds under $`\mathrm{\Gamma }𝐃^{}𝐒`$ for every $`𝐃^{}`$.

How can we do this? As we shall see now, if $`\mathrm{\Gamma }`$ is a smooth d-DNNF, then all of this can be done in time linear in the size of $`\mathrm{\Gamma }`$!

This works exactly as in the previous section, except that we have to minimize the d-DNNF first, a process which eliminates some of the d-DNNF models (?). To define this minimization process more precisely, we need the following definition first:

###### Definition 9

If $`\mathrm{\Sigma }`$ is a set of atoms, then the $`\mathrm{\Sigma }`$-cardinality of a model is the number of atoms in $`\mathrm{\Sigma }`$ that the model sets to false.

To $`\mathrm{\Sigma }`$-minimize a theory $`\mathrm{\Gamma }`$ is to convert it into another theory whose models are exactly the models of $`\mathrm{\Gamma }`$ having a minimum $`\mathrm{\Sigma }`$-cardinality. Consider the d-DNNF $`\mathrm{\Gamma }`$ in Figure 1 for an example and suppose that $`\mathrm{\Sigma }=\{A,B,C,D\}`$; that is, we want to minimize the d-DNNF with respect to each of its atoms. This theory has eight models, each having an odd cardinality (one or three). If we $`\mathrm{\Sigma }`$-minimize this d-DNNF, we obtain another with four models, shown in Figure 9.

Given these definitions, we can re-phrase the problem of belief revision (stated above) as follows. Let $`\mathrm{\Sigma }`$ be a set of atoms representing defaults, and let $`\mathrm{\Gamma }`$ be a smooth d-DNNF. Given observation $`𝐒`$, $`\mathrm{\Sigma }`$-minimize the theory $`\mathrm{\Gamma }𝐒`$ to yield $`\mathrm{\Delta }`$ and then report on the truth of each literal under the minimized theory $`\mathrm{\Delta }`$.

As it turns out, one can minimize a smooth d-DNNF in linear time, to yield another smooth d-DNNF to which we can apply the techniques of the previous section. We now describe the process of minimizing a DNNF which is described in more details in (?). We do this in a two-step process:

1. We assign a cardinality to every node in the d-DNNF as follows:

1. each literal whose atom is not in $`\mathrm{\Sigma }`$ gets cardinality zero;
    2. each positive literal whose atom is in $`\mathrm{\Sigma }`$ gets cardinality zero;
    3. each negative literals whose atom is in $`\mathrm{\Sigma }`$ gets cardinality one;
    4. the cardinality of a disjunction is the min of its disjuncts’ cardinalities;
    5. the cardinality of a conjunction is the summation of its conjuncts’ cardinalities.
2. For each or-node $`N`$ and its child $`M`$, we delete the edge connecting $`N`$ and $`M`$ if the cardinality of $`N`$ is smaller than the cardinality of $`M`$.

Figure 8 depicts the result of assigning cardinalities to the d-DNNF of Figure 1, and Figure 9 depicts the result of deleting some of its edges. This is the minimized d-DNNF and it has four models:

$`\neg ABCD`$;

$`A\neg BCD`$;

$`AB\neg CD`$;

$`ABC\neg D`$.

Once we have minimized the d-DNNF, we can apply the results of the previous section to obtain the answers we want.

As an example, Figure 10 depicts the counting graph of the minimized d-DNNF $`\mathrm{\Delta }`$ in Figure 9, with its value and partial derivatives computed under the observation $`𝐒=\{\neg A\}`$. From these partial derivatives and Theorem 6, we immediately get:

$`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{\neg B\})=0`$; $`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{\neg C\})=0`$; $`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{\neg D\})=0`$. That is, $`B,C`$ and $`D`$ are all entailed by $`\mathrm{\Delta }𝐒`$.

$`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{\neg A\})=1+3=4`$. That is, we have four models if we retract $`\neg A`$.

$`\mathrm{𝑀𝑜𝑑𝑒𝑙𝑠}\mathrm{\#}(\mathrm{\Delta }𝐒\{\neg A\}\{A\})=11+3=3`$. That is, we have three models if we flip $`\neg A`$ to $`A`$.

## Predicting the Behavior of Broken Devices

The above results have direct application to model-based diagnosis, where $`\mathrm{\Delta }`$ is the device description, $`𝐒`$ is the device observation and $`𝐃`$ contains the health modes $`\mathrm{𝑜𝑘}_1,\mathrm{},\mathrm{𝑜𝑘}_n`$. Initially, we assume that all device components are working normally, but then find some observation $`𝐒`$ such that $`\mathrm{\Delta }𝐃=\{\mathrm{𝑜𝑘}_1,\mathrm{},\mathrm{𝑜𝑘}_n\}𝐒`$ is inconsistent.

To regain consistency we must postulate that some of the components are not healthy, therefore, flipping some of the $`\mathrm{𝑜𝑘}_i`$s into $`\neg \mathrm{𝑜𝑘}_i`$ in the set $`𝐃`$. Assuming a smallest number of faults, we want to minimize the number of unhealthy components needed to regain consistency. A set $`𝐃^{}`$ such that:

1. $`\mathrm{𝑜𝑘}_i𝐃^{}`$ or $`\neg \mathrm{𝑜𝑘}_i𝐃^{}`$ for all $`i`$;
2. $`\mathrm{\Delta }𝐃^{}𝐒`$ is consistent;
3. the number of negative literals in $`𝐃^{}`$ is minimized;

is called a minimum-cardinality diagnosis and one goal of model-based diagnosis to enumerate such diagnoses (??).

Another practical problem, however, which has received much less attention in model-based diagnosis is the following: Assuming a smallest number of faults, what is the truth value of every literal appearing in the device description $`\mathrm{\Delta }`$? That is, we do not want to know what the minimum-cardinality diagnoses are. Instead — and under the assumption that one of them has materialized — we want to predict the behavior of the given faulty device. But this is exactly the problem we have treated in the previous section.

Therefore, our results allow us to predict the value of each device port (literal $`l`$) in a broken device, assuming that the number of broken components is minimal, in time linear in the size of device description $`\mathrm{\Delta }`$, as long as $`\mathrm{\Delta }`$ is a smooth d-DNNF. We are unaware of any similar complexity result for model-based diagnosis.

## Conclusion

We have identified two classes of propositional theories, those which have a bounded treewidth, and those which have a linear-sized FBDD representation. We have shown that each of these classes of theories can be converted in linear time into a tractable form that we called deterministic DNNF, d-DNNF. We have also defined linear-time, model-counting operations on d-DNNF, allowing us to implement (a) linear-time, complete truth maintenance systems and (b) linear-time, complete belief revision systems for the two identified classes of propositional theories. Our results also have major implications on the practice of model-based diagnosis as they allow us to efficiently predict the behavior of a broken device, assuming a smallest number of broken components.


text:
# Single chargino production with R-parity lepton number violation in electron-electron and muon-muon collisions

## 1 Introduction

R-parity is a discrete symmetry defined by assigning to every field the number $`R=(1)^{3B+L+2S}`$ ($`B(L)`$ \- baryon (lepton) number, $`S`$ \- spin of the particle) . If it is conserved then baryon and lepton number violating transitions are forbidden. In that case, the theory guarantees both proton stability and lepton universality. However, in supersymmetric extensions of the Standard Model, gauge invariance and renormalizability, the two main principles of any gauge theory, do not assure R-parity conservation. At present, wide phenomenological investigations of R-parity violating processes have been undertaken (for reviews see e.g. ).

Here we will explore the possibility of discovering the lepton number violating process of single chargino production at future lepton-lepton colliders (see Fig.1(I) for an electron-electron collision). To our knowledge this process has not yet been discussed, though lepton number violating charginos pair production in electron-electron collisions (Fig.1(II)) has been considered .

Let us start with electron-electron collisions. The analysis of the muon option is analogous and will be shortly discussed whenever needed. As can be seen from Fig.1(I), the cross section for single chargino production is proportional to $`\lambda ^2g^2`$ where $`\lambda `$ and $`g`$ are couplings involved in the following Lagrangians ($`\lambda _{abc}=\lambda _{acb}`$, $`a,b,c`$ are family indices):

$``$ $`=`$ $`g\overline{\stackrel{~}{\chi }}_i^cV_{i1}(1\gamma _5)e\stackrel{~}{K}_{em}\stackrel{~}{\nu }_m^{}+h.c.,`$ (1)
$`_\mathit{}_p`$ $`=`$ $`\lambda _{abc}\{\stackrel{~}{\nu }_{aL}\overline{l}_{cR}l_{bL}(ab)\}+h.c.`$ (2)
These Lagrangians are written in physical basis. The matrix $`\stackrel{~}{K}_{em}`$ in Eq. (1) comes from the sneutrino mass matrix diagonalization. If R-parity is violated, we have to take into account the mixing between the sneutrinos $`\stackrel{~}{\nu }_e`$, $`\stackrel{~}{\nu }_\mu `$, $`\stackrel{~}{\nu }_\tau `$ and the neutral Higgs bosons $`H_1^0`$, $`H_2^0`$. We shall, however, assume that this mixing is negligible and does not affect the results, at least at the stage of chargino production. In what follows we shall also assume that the exchange of the lightest (electron) sneutrino dominates (which is equivalent to some hierarchy assumption in the sneutrino sector) and neglect the contribution of the heavier $`\stackrel{~}{\nu }`$’s. We therefore set ($`e`$ stands for electron) $`\stackrel{~}{K}_{em}=\delta _{em}`$ in Eq. (1). For more complicated cases where the interplay between sneutrino masses in propagators and appropriate elements of the $`\stackrel{~}{K}`$ matrix matters we refer to .

The second mixing matrix, namely $`V_{i1}`$ in Eq. (1) is connected with the chargino sector and describes the weights of the wino component of the chargino fields . Since this is the only component of the charginos that couples to the electron and the sneutrino (the charged higgsino coupling is neglected in the limit of zero electron mass) we set for simplicity $`V_{i1}=1`$. This is further justified by the analysis  (in the parameter region $`|\mu |100`$ GeV, $`M_2100`$ GeV for both small and large $`\mathrm{tan}\beta `$, with $`\mu ,M_2`$ being the higgsino and gaugino $`SU(2)`$ mass parameters, respectively, and $`\beta `$ a ratio of two vacuum expectation values involved in MSSM). In general the results should be multiplied by $`V_{i1}^2`$. Furthermore, with R-parity violation, additional couplings between leptons, gauginos and higgsinos $`(e,\mu ,\tau ,\stackrel{~}{W}^{},\stackrel{~}{H}^{})_L`$ exist, but are known to be smaller than the gauge ones .

## 2 Single chargino production and decays: results

In Fig. 2 we gather the cross sections for single chargino production at future electron-electron colliders with c.m. energies $`\sqrt{s}=500`$ GeV and $`\sqrt{s}=1`$ TeV as functions of the chargino mass for different sneutrino masses111Results (see Appendix) assume a $`P_{}^e=100\%`$ electron beam polarization. In reality we can expect that $`P_{}^e=90\%`$ can be achieved. Then the cross sections must be multiplied by a factor $`\frac{1}{4}(1P_{}^{e_1})(1P_{}^{e_2})0.9`$.. For the R-parity violating coupling, we have used the most conservative available upper limit $`\lambda _{112(3)}\lambda =0.05`$ , independently of the $`\stackrel{~}{\nu }_e`$ mass (in the case of muon-muon collisions the $`\lambda _{212(3)}`$ couplings would be involved). For sneutrino masses larger than 100 GeV this limit becomes weaker .

As can be deduced from Fig.2, with a planned annual luminosity of some 50 fb-1 yr-1  and with a discovery limit at a level of 10 events per year ($`\sigma =0.2`$ fb), the process is detectable for a wide range of sparticle masses.

With the R-parity violating production process (I) we are already definitely out of the SM physics. It is therefore interesting to investigate the possible detector signals. With R-parity non-conservation, the collider phenomenology is quite different from the MSSM case and depends especially on the nature of the LSP (Lightest Supersymmetric Particle). In the MSSM, the stable LSP must be charge and color neutral for cosmological reasons . With R-parity violation there are no hints about the unstable LSP. It can be among others a sneutrino, gluino or even a chargino .

Here we give an example of nonstandard phenomenology but restrict ourselves to a scenario in which charginos decay uniquely (via sneutrino exchange) to charged leptons. Final leptonic signals with lepton number violation and without missing energy could be detected, an interesting situation from the point of view of nonstandard physics, as there is no SM background (see further discussion). These two conditions (charged leptons without missing energy in the final state) require the chargino to be the second lightest supersymmetric particle (NLSP) with sneutrino the LSP. This situation is schematically summarized in Fig.3. If the chargino were the LSP its lifetime should be long enough so that it would be seen in the detector. In other cases (i.e. when the chargino is neither NLSP nor LSP) the chargino would also have cascade decays to final jet states . Then, the situation would be more complicated but at least we can expect that for kinematical reasons a decay to the R-parity lepton violating LSP sneutrino would still be important and the final signal with four charged leptons could be observed (work in progress).

Let us discuss the scenario with NLSP chargino. First, we should notice that, to get substantial chargino production (e.g. $`e^{}e^{}\mu ^{}\stackrel{~}{\chi }^{}`$ in Fig.2), we are interested in the situation where at least one, let us say $`\lambda _{112}`$ coupling is large. Then the decay of chargino to three charged leptons must be observed in the detector, as it can undergo uniquely through the same large $`\lambda _{112}`$ coupling (the only possible decay channel, see Fig.3).

In Fig.4, we show the final results for the angular distribution of the final positron (Fig.3) for two different energies ($`\sqrt{s}=500(1000)`$ GeV). We have taken $`m_{\stackrel{~}{\chi }}=205`$ GeV and $`m_{\stackrel{~}{\nu }}=200`$ GeV. Results have been obtained using the VEGAS procedure. Four particles in the final state give us an 8 dimensional integration. We have also applied the narrow width approximation where $`\mathrm{\Gamma }_{\stackrel{~}{\chi }}<<m_{\stackrel{~}{\chi }}`$ (see Appendix for details). The solid line describes results based on Eq. (A.21), when interferences between production and decay of charginos with $`\stackrel{~}{\lambda }=\pm 1/2`$ are taken into account. The dashed line describes results with factorization assumed , which means the following replacement in Eq. (A.21) is done

$$\underset{\stackrel{~}{\lambda }}{}|M(;,\stackrel{~}{\lambda })T\left(\stackrel{~}{\lambda }\right)|^2\frac{1}{2}\underset{\stackrel{~}{\lambda }}{}|M(;,\stackrel{~}{\lambda })|^2\underset{\stackrel{~}{\lambda }}{}|T\left(\stackrel{~}{\lambda }\right)|^2$$
(3)
We can see that spin correlations do not change the results substantially ($`2`$ % for considered c.m energies and the chargino mass). It is important that the positron angular distributions are not so strongly peaked in the beam directions, even for $`\sqrt{s}=1`$ TeV collider energy. With assumed cuts $`(|\mathrm{cos}\mathrm{\Theta }_+|0.95)`$ enough events will be detected to investigate the process.

The only SM process, which gives a four charged lepton signal without missing energy is  $`e^{}e^{}e^{}e^{}Z`$. With a possible Z boson decay to the lepton-antilepton pair, it does not coincide with the process under investigation ($`e^{}e^{}2\mu ^{}e^{}e^+`$). That means that we do not have to bother about the SM background contamination. However, this cross section is large enough ($`1`$ pb for $`0.5\sqrt{s}2`$ TeV energies) to cover some other scenarios. As an example let us assume that not only $`\lambda _{112}`$ but also $`\lambda _{121}`$ is not negligible and change the second coupling in the chargino decay channel (Fig.3) from $`\lambda _{112}`$ to $`\lambda _{121}`$. That means that we have now $`(e^{}e^{})e^{}e^{}\mu ^{}\mu ^+`$ in the final state, and this scenario will be dominated by the SM process given above with the Z decay to the muon antimuon pair. In this way we can find that $`\mu ^{}\mu ^{}e^{}e^+(\tau ^+),\mu ^{}\tau ^{}e^{}e^+(\mu ^+)`$ and $`\tau ^{}\tau ^{}e^{}e^+`$ charged lepton signals are testable (meaning sensitivity to the products $`\lambda _{112}\lambda _{112}(\lambda _{113})`$, $`\lambda _{112}\lambda _{113}(\lambda _{123})`$ and $`\lambda _{113}\lambda _{113}`$, respectively).

Finally, our results can be easily applied to the muon-muon collider where another set of R-parity lepton violating couplings can be tested, namely: $`\lambda _{221}\lambda _{212}`$ ($`e^{}e^{}\mu ^{}\mu ^+`$ in the final state), $`\lambda _{221}\lambda _{213}`$ ($`e^{}e^{}\mu ^{}\tau ^+`$) and $`\lambda _{221}\lambda _{231}`$ ($`e^{}\mu ^{}e^+\tau ^{}`$).

## 3 Conclusions

Present experimental limits on R-parity violating couplings do not exclude large and detectable lepton number violating signals in lepton-lepton collisions. We discuss such a possibility in conjunction with single chargino production and its subsequent leptonic decay. If at least one $`\lambda `$ value is large enough - in our discussion mainly $`\lambda _{112}`$ \- single chargino production in electron-electron collisions will be observable (Fig.2). If the chargino is NLSP and sneutrino the LSP, a unique lepton number violating signal of four charged leptons without missing energy could be observed.

## Acknowledgments

We would like to thank H. Fraas, C. Blöchinger, S. Hesselbach (Würzburg University) and G. Moortgat–Pick (DESY, Hamburg) for helpful discussions and valuable remarks. This work was supported by the Polish Committee for Scientific Research under Grant No. 2P03B05418. J.G. would like to thank the Alexander von Humboldt-Stiftung for fellowship.

## Appendix A Appendix

The helicity amplitude for single chargino production $`e^{}e^{}\mu ^{}(\tau ^{})\stackrel{~}{\chi }^{}`$ is given by:

$`M(\sigma _1,\sigma _2;\lambda ,\stackrel{~}{\lambda })`$ $`=`$ $`g\lambda _{112}[\overline{u}(p,\lambda )(1\gamma _5)u(k_1,\sigma _1){\displaystyle \frac{1}{tm_{\stackrel{~}{\nu }_e}^2}}\overline{u}(\stackrel{~}{p},\stackrel{~}{\lambda })(1\gamma _5)u(k_2,\sigma _2)`$ (4)
$``$ $`\overline{u}(\stackrel{~}{p},\stackrel{~}{\lambda })(1\gamma _5)u(k_1,\sigma _1){\displaystyle \frac{1}{um_{\stackrel{~}{\nu }_e}^2}}\overline{u}(p,\lambda )(1\gamma _5)u(k_2,\sigma _2)],`$
$`t(u)`$ $`=`$ $`m_{\stackrel{~}{\chi }}^2\sqrt{s}(\stackrel{~}{E}2\stackrel{~}{p}\mathrm{cos}\stackrel{~}{\mathrm{\Theta }})`$ (5)
where $`(\stackrel{~}{p},\stackrel{~}{\lambda })`$ denotes the momentum and helicity of the chargino, $`(k_{1(2)},\sigma _{1(2)})`$ are the corresponding quantities for the incoming electrons, $`p`$ and $`\lambda `$ denote momentum and helicity of the muon (tau) and $`(\stackrel{~}{\mathrm{\Theta }},\stackrel{~}{\varphi })`$ label the c.m. azimuthal and polar angles of a chargino with respect to the direction of the initial electron $`e_1^{}`$.

To work out the helicity amplitudes, we use the Weyl– van der Waarden spinor formalism  in which the 4–spinors can be written:

$`u(p,\lambda )`$ $`=`$ $`\left(\begin{array}{c}\sqrt{Ep\lambda }\chi (p,\lambda )\\ \sqrt{E+p\lambda }\chi (p,\lambda )\end{array}\right),v=\left(\begin{array}{c}\lambda \sqrt{E+p\lambda }\chi (p,\lambda )\\ \lambda \sqrt{Ep\lambda }\chi (p,\lambda )\end{array}\right),`$ (6)
and the Weyl spinors are given by:

$`\chi (p,+1/2)`$ $`=`$ $`\left(\begin{array}{c}e^{i\varphi /2}\mathrm{cos}\theta /2\\ e^{i\varphi /2}\mathrm{sin}\theta /2\end{array}\right),\chi (p,1/2)=\left(\begin{array}{c}e^{i\varphi /2}\mathrm{sin}\theta /2\\ e^{i\varphi /2}\mathrm{cos}\theta /2\end{array}\right),`$ (7)
where $`\mathrm{\Theta },\varphi `$ denote the azimuthal and the polar angle of a particle with respect to the $`\widehat{z}`$ axis.

In the limit of zero mass of all charged leptons we have only two non-vanishing helicity amplitudes ($`\sigma _{1,2},\lambda =1/2,\stackrel{~}{\lambda }=\pm 1/2`$), namely:

$`M(,,)`$ $`=`$ $`g\sqrt{2s}\sqrt{(\stackrel{~}{E}\stackrel{~}{p})(\stackrel{~}{E}\stackrel{~}{p})}\lambda _{112}\left[{\displaystyle \frac{\mathrm{cos}^2\frac{\stackrel{~}{\mathrm{\Theta }}}{2}}{tm_{\stackrel{~}{\nu }_e}^2}}+{\displaystyle \frac{\mathrm{sin}^2\frac{\stackrel{~}{\mathrm{\Theta }}}{2}}{um_{\stackrel{~}{\nu }_e}^2}}\right]`$ (8)
$`M(,,+)`$ $`=`$ $`g\sqrt{2s}\sqrt{(\stackrel{~}{E}+\stackrel{~}{p})(\stackrel{~}{E}\stackrel{~}{p})}\mathrm{cos}{\displaystyle \frac{\stackrel{~}{\mathrm{\Theta }}}{2}}\mathrm{sin}{\displaystyle \frac{\stackrel{~}{\mathrm{\Theta }}}{2}}\lambda _{112}\left[{\displaystyle \frac{1}{tm_{\stackrel{~}{\nu }_e}^2}}{\displaystyle \frac{1}{um_{\stackrel{~}{\nu }_e}^2}}\right].`$
The cross section is:

$$d\sigma =\frac{1}{2s}dLips(s,p,\stackrel{~}{p})\underset{\stackrel{~}{\lambda }}{}\left|M(,;,\stackrel{~}{\lambda }_j)\right|^2$$
(10)
where

$`dLips(s,p,\stackrel{~}{p})`$ $`=`$ $`{\displaystyle \frac{\stackrel{~}{p}}{16\pi ^2p}}d\mathrm{cos}\stackrel{~}{\mathrm{\Theta }}d\stackrel{~}{\varphi }.`$ (11)
In Fig. 3 we study the R-parity violating chargino decays via sneutrino exchange in the t-channel: $`\stackrel{~}{\chi }e^{}e^+\mu ^{}`$. Analogously to the production the amplitude is:

$`T(\stackrel{~}{\lambda }_i)`$ $`=`$ $`g\lambda _{112}\left[\overline{u}(p_1,\sigma _1)(1\gamma _5)u(\stackrel{~}{p},\stackrel{~}{\lambda }){\displaystyle \frac{1}{tm_{\stackrel{~}{\nu }_e}^2+i\mathrm{\Gamma }_{\stackrel{~}{\nu }}m_{\stackrel{~}{\nu }_e}}}\overline{u}(p_2,\sigma _2)(1\gamma _5)v(p_+,\sigma _+)\right],`$
where ($`(p_{1(2)}^i,\sigma _{1(2)}^i)`$ denote the momenta and helicities of the electron and muon, $`(p_+,\sigma _+)`$ are analogous quantities for the final positron.

Using Eqs. (6,7) we get

$`T(\stackrel{~}{\lambda }=+1/2)`$ $`=`$ $`\mathrm{\Omega }_t(+)\left[e^{i/2(\varphi _1\stackrel{~}{\varphi })}\mathrm{sin}{\displaystyle \frac{\mathrm{\Theta }_1}{2}}\mathrm{cos}{\displaystyle \frac{\stackrel{~}{\mathrm{\Theta }}}{2}}+e^{i/2(\varphi _1\stackrel{~}{\varphi })}\mathrm{cos}{\displaystyle \frac{\mathrm{\Theta }_1}{2}}\mathrm{sin}{\displaystyle \frac{\stackrel{~}{\mathrm{\Theta }}}{2}}\right]`$ (13)
$`\times `$ $`\left[e^{i/2(\varphi _2\varphi _+)}\mathrm{sin}{\displaystyle \frac{\mathrm{\Theta }_2}{2}}\mathrm{cos}{\displaystyle \frac{\mathrm{\Theta }_+}{2}}+e^{i/2(\varphi _2\varphi _+)}\mathrm{cos}{\displaystyle \frac{\mathrm{\Theta }_2}{2}}\mathrm{sin}{\displaystyle \frac{\mathrm{\Theta }_+}{2}}\right]`$
$`T(\stackrel{~}{\lambda }=1/2)`$ $`=`$ $`\mathrm{\Omega }_t()\left[e^{i/2(\varphi _1\stackrel{~}{\varphi })}\mathrm{sin}{\displaystyle \frac{\mathrm{\Theta }_1}{2}}\mathrm{sin}{\displaystyle \frac{\stackrel{~}{\mathrm{\Theta }}}{2}}+e^{i/2(\varphi _1\stackrel{~}{\varphi })}\mathrm{cos}{\displaystyle \frac{\mathrm{\Theta }_1}{2}}\mathrm{cos}{\displaystyle \frac{\stackrel{~}{\mathrm{\Theta }}}{2}}\right]`$ (14)
$`\times `$ $`\left[e^{i/2(\varphi _2\varphi _+)}\mathrm{sin}{\displaystyle \frac{\mathrm{\Theta }_2}{2}}\mathrm{cos}{\displaystyle \frac{\mathrm{\Theta }_+}{2}}+e^{i/2(\varphi _2\varphi _+)}\mathrm{cos}{\displaystyle \frac{\mathrm{\Theta }_2}{2}}\mathrm{sin}{\displaystyle \frac{\mathrm{\Theta }_+}{2}}\right]`$
where $`(\mathrm{\Theta }_{+(1,2)},\varphi _{+(1,2)})`$ denote azimuthal and polar angles of the final positron (electron (1), muon (2)) which are defined with respect to the direction of the initial electron beam $`e_1`$ and $`\mathrm{\Omega }_t(\pm )`$ is given by

$$\mathrm{\Omega }_t(\pm )=g\sqrt{8E_+E_1E_2}\sqrt{\stackrel{~}{E}\pm \stackrel{~}{p}\stackrel{~}{\lambda }}\underset{m_{\stackrel{~}{\nu }_n}}{}\lambda _{n12}\frac{1}{tm_{\stackrel{~}{\nu }_n}^2+i\mathrm{\Gamma }_{\stackrel{~}{\nu }}m_{\stackrel{~}{\nu }_n}}.$$
(15)
The decay width can be written as

$$d\mathrm{\Gamma }=\frac{1}{2m_{\stackrel{~}{\chi }}}dLips(\stackrel{~}{m},p_1,p_2,p_+)\underset{\stackrel{~}{\lambda }}{}|T(\stackrel{~}{\lambda })|^2$$
(16)
where

$`dLips(\stackrel{~}{m},p_1,p_2,p_+)`$ $`=`$ $`{\displaystyle \frac{1}{\left(2\pi \right)^58}}{\displaystyle 𝑑E_+d\mathrm{cos}\mathrm{\Theta }_+𝑑\varphi _+d\mathrm{cos}\mathrm{\Theta }_2𝑑\varphi _2}.`$ (17)
Formulae Eq. (A.13) describe the 3–body–decay of a chargino with energy $`\stackrel{~}{E}`$ and angles $`\stackrel{~}{\mathrm{\Theta }},\stackrel{~}{\varphi }`$. The angles of the chargino and of the particles produced by chargino decay are defined with respect to the direction of the initial electron beam $`e_1^{}`$. Angles of the decaying particles are also defined with respect to the initial CM system of colliding electrons. We have left quantities connected with $`e^+`$ as independent parameters to be integrated over. From the 12 quantities describing the chargino 3–body–decay, four are eliminated by momentum conservation. These are chosen to be the angles $`\mathrm{\Theta }_1,\varphi _1`$ and the energies $`E_{1,2}`$, namely:

$`E_2`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \frac{\stackrel{~}{m}_i2\stackrel{~}{E}E_++2\stackrel{~}{p}E_+\mathrm{cos}(\stackrel{~}{p},p_+)}{\stackrel{~}{E}E_+\stackrel{~}{p}\mathrm{cos}(\stackrel{~}{p},p_2)+2E_+\mathrm{cos}(p_2,p_+)}}`$ (18)
$`E_1`$ $`=`$ $`\stackrel{~}{E}E_2E_+`$ (19)
$`\mathrm{cos}\mathrm{\Theta }_1`$ $`=`$ $`{\displaystyle \frac{\stackrel{~}{p}\mathrm{cos}\stackrel{~}{\mathrm{\Theta }}E_2\mathrm{cos}\mathrm{\Theta }_2E_+\mathrm{cos}\mathrm{\Theta }_+}{E_1}}.`$ (20)
The angle $`\varphi _1`$ is fixed by two relations:

$`E_1\mathrm{sin}\mathrm{\Theta }_1\mathrm{cos}\varphi _1`$ $`=`$ $`\stackrel{~}{p}\mathrm{sin}\stackrel{~}{\mathrm{\Theta }}\mathrm{cos}\stackrel{~}{\varphi }E_2\mathrm{sin}\mathrm{\Theta }_2\mathrm{cos}\varphi _2E_+\mathrm{sin}\mathrm{\Theta }_+\mathrm{cos}\varphi _+,`$ (21)
$`E_1\mathrm{sin}\mathrm{\Theta }_1\mathrm{sin}\varphi _1`$ $`=`$ $`\stackrel{~}{p}\mathrm{sin}\stackrel{~}{\mathrm{\Theta }}\mathrm{sin}\stackrel{~}{\varphi }E_2\mathrm{sin}\mathrm{\Theta }_2\mathrm{sin}\varphi _2E_+\mathrm{sin}\mathrm{\Theta }_+\mathrm{sin}\varphi _+`$ (22)
We end up with the 8 parameters (these are given by Eq. (17) and $`\stackrel{~}{E},\stackrel{~}{\mathrm{\Theta }},\stackrel{~}{\varphi }`$).

For completeness, it is trivial to compute the sneutrino decay width. For $`m_{\stackrel{~}{\nu }}m_{\stackrel{~}{\chi }}`$ (the scenario discussed in the text, see Fig.4) only one decay channel to an $`e^{}\mu ^+`$ pair is open (for simplicity we assume that only one $`\lambda _{112}`$ dominates):

$$\mathrm{\Gamma }_{\stackrel{~}{\nu }}=\lambda _{112}^2m_{\stackrel{~}{\nu }_e}/8\pi .$$
(23)
Finally for the combined process of production and decay we obtain in the narrow width approximation:

$`d\sigma (e^{}e^{}2\mu ^{}e^{}e^+)`$ $`=`$ $`{\displaystyle \frac{1}{2s}}dLips(s,p,\stackrel{~}{p})dLips(\stackrel{~}{m},p_1,p_2,p_+){\displaystyle \frac{1}{2\pi }}`$ (24)
$`{\displaystyle \underset{\stackrel{~}{\lambda }}{}}|M(;,\stackrel{~}{\lambda })T\left(\stackrel{~}{\lambda }\right)|^2\left({\displaystyle \frac{\pi }{m\mathrm{\Gamma }}}\right).`$