text:
# OUTFLOWS VS. CLOUDS IN AGN INTRINSIC ABSORBERS

## 1. Introduction

AGN outflows are evident by resonance line absorption troughs, which are blueshifted with respect to the systemic redshift of their emission counterparts. In Seyfert galaxies, velocities of several hundred km s<sup>-1</sup> (Crenshaw et al. 1999; Kriss et al. 2000) are observed in both UV resonance lines (e.g., C iv $`\lambda \lambda `$1548.20,1550.77, N v $`\lambda \lambda `$1238.82,1242.80, O vi $`\lambda \lambda `$1031.93,1037.62 and Ly$`\alpha `$), as well as in X-ray resonance lines (Kaastra et al. 2000; Kaspi et al. 2000). Similar outflows (often with significantly higher velocities) are seen in quasars (Weymann et al. 1991; Korista, Voit, Morris, & Weymann 1993; Arav et al. 2001a). Reliable measurement of the absorption column densities in the troughs are crucial for determining the ionization equilibrium and abundances of the outflows, and the relationship between the UV and the ionized X-ray absorbers.

In the last few years our group (Arav 1997; Arav et al. 1999a; Arav et al. 1999b; de Kool et al. 2001; Arav et al. 2001a) and others (Barlow 1997, Telfer et al. 1998, Churchill et al. 1999, Ganguly et al. 1999) have shown that in quasar outflows most lines are saturated even when not black. We have also shown that in many cases the shapes of the troughs are almost entirely due to changes in the line of sight covering as a function of velocity, rather than to differences in optical depth (Arav et al. 1999b; de Kool et al. 2001; Arav et al. 2001b). Gabel et al. (2003) show the same effect in the outflow troughs of NGC 3783. As a consequence, the column densities inferred from the depths of the troughs are only lower limits.

## 2. The importance of $`C(v)`$: O vi troughs in Mrk 279

Mrk 279 was observed by FUSE for a combined 92 ksec on December 1999 and January 2000. The source was in a high state, rivaling the highest UV flux state of any Seyfert outflow target. Several factors combined to make these data arguably the highest quality FUSE observation of an AGN outflow: Non-blending of the O vi trough, the length of exposure at a very high flux level, very low Galactic column along the sight-line, and insignificant narrow emission line. In figure 1 we show the O vi doublet data, covering fraction solution and three different extractions of the optical depth. We find that the shape of trough A is almost exclusively determined by $`C(v)`$. This feature manifests itself in the $`\tau (v)`$ solution. The column density extracted from the real solution is four times larger than the one we obtain from a simple inversion of the blue doublet-component data. Moreover the real column density is three times larger than the one we extract using a constant covering fraction for this outflow component. We also observe that the shape of $`\tau (v)`$ is very different if we assume a constant covering fraction instead of the actual $`\tau (v)`$. Underestimating ionic column densities by a factor of a few can translate to a much larger discrepancy in the solution for the ionization parameter ($`U`$) and total Hydrogen column density ($`N_H`$) of the outflow component. As shown in Arav (2001b) a five fold change in inferred ionic column density can result in a 10 times higher $`U`$ and a 100 times higher $`N_H`$.

## 3. Clouds vs. Dynamical Disk Outflows

The “cloud” picture of absorption features associated with AGN outflows was developed from the traditional ISM absorber model: A concentration of gas with thermal velocity distribution. Since the width of the outflow absorption troughs were found to be 10–1000 times the expected thermal width, a “turbulent” velocity broadening was invoked. We point out that this “turbulent” broadening is problematic since it suggests internal motions with large Mach numbers which should result in shocks and the destruction of the absorption ionic species. In addition, once it was realized that many of the troughs are saturated but not black, a partial geometrical covering of the emission source was invoked, as illustrated in the top part of figure 2. The main problem with this picture is its inability to explain the velocity dependence of the covering fraction. A cloud sitting in front of an emission source should have a velocity independent covering fraction. Furthermore, the cloud picture is hard pressed to explain the observed detached troughs where the absorption starts from non zero velocity.

We advocate the dynamical outflow scenario shown on the bottom of figure 2. As we show below, this model naturally explains the strong velocity dependence of the covering fraction, the detached trough phenomenon and the highly super-thermal width of the trough. All these attributes are connected to invoking the simplest reservoir for the outflowing material: The accretion disk around the black hole. This scenario fits well with the global AGN atmosphere model of Elvis (2000).

In figure 3 we illustrate how an accelerating outflow can produce an absorption trough whose shape is totally determined by $`C(v)`$. We make two plausible assumptions: 1) The flow is at a small angle to the line of sight (i.e. the flow is not purely radial). 2) The flow is accelerating as it crosses the cylinder of sight, which contains all the lines of sights from the continuum source to the observer. For simplicity we also assume a 2-D geometry where the velocity is constant perpendicular to the velocity vector. A covering fraction dominated absorption trough is produced for a fully opaque flow in a given resonance line (e.g., Ly$`\alpha `$). Prior to the flow reaching point a it does not intersect the cylinder of sight, therefore we do not see any absorption at $`v<v_a`$. This scenario gives a natural explanation to the widely observed phenomenon of detached troughs. As the flow continues to accelerate, it gradually covers a larger fraction of the cylinder of sight. For example, at point M the flow covers roughly one third of the cylinder of sight with material moving at $`v_M`$. Even if the resonance line opacity is very large at $`v_M`$ the absorption trough only dips to $`1/3`$ below the continuum flux. $`C(v)`$ gradually increases until $`v_b`$, at which point a maximum coverage has been reached. The maximum coverage can be smaller than one in cases where there is an additional extended emission source (e.g., the broad emission line region). At $`v_c`$ the flow reaches the last point of maximum coverage and thereafter the coverage decreases gradually. A fully opaque outflow produces an absorption trough purely from velocity dependent covering factor.

References

| Arav, N., 1997, ASP 128, p. 208 | Elvis, M., 2000, ApJ, 545, 63 |
| --- | --- |
| Arav, N., et al., 1999a, ApJ, 516, 27 | Gabel, J. R., et al.,2003, ApJ, 595, 120 |
| Arav, N., et al., 1999b, ApJ, 524, 566 | Ganguly, R., et al., 1999, AJ, 117, 2594 |
| Arav, N., et al., 2001a, ApJ, 546, 140 | Kaastra, J. S., et al., 2000, A&A, 354L, 83 |
| Arav, N., et al., 2001b, ApJ, 561, 118 | Kaspi, S., et al., 2000, ApJ, 535L, 17 |
| Barlow, T. A., 1997 ASP 128, p. 13 | Korista, T. K., et al., 1993, ApJS, 88, 357 |
| Churchill, C. W., et al., 1999, AJ, 117, 2573 | Kriss, G. A., et al., 2000, ApJL, 538, 17 |
| Crenshaw, D. M., et al., 1999 ApJ, 516, 750 | Telfer, R.C., et al., 1998, ApJ, 509, 132 |
| de Kool, M., et al., 2001, ApJ, 548, 609 | Weymann, R. J., et al., 1991, ApJ, 373, 23 |


format: text

text:
# Diffusion-reaction mechanisms of nitriding species in SiO2

## I Introduction

Nitrided silicon oxide or oxynitride is currently the near-term solution to substitute SiO2 as the gate insulator material for the ultrathin metal-oxide-semiconductors (MOS) technology. Recent studies have suggested that the performance of oxynitride-based MOS devices depends both on the depth concentration and on the distribution of nitrogen into the gate oxide.green  According to these studies, the best nitrogen profile for an ultrathin gate oxide would have: (i) a small nitrogen concentration near the SiO2/Si interface in order to reduce degradations by hot electrons,cartier  and (ii) a larger N concentration near the interface between the dielectric and the polycrystalline silicon (poly-Si) gate electrode, in order to minimize dopant diffusion.wrister

The growth of ultrathin oxynitride films depends strongly on the reactant agent (e.g., N2O, NO, NH3) and the technique used. Nitrogen can be incorporated into SiO2 using either thermal oxidation and annealing or chemical and physical deposition methods. Thermal nitridation of SiO2 in N2O generally results in a relatively low N concentration at near-interface (Si/SiO2) region. The nitriding species are originated in the decomposition of the N2O molecule occurring at typical oxidation temperature, these species being the NO and N2 molecules.ellis ; baumvol ; lu  On the other hand, nitrogen incorporation in SiO2 can also be performed via annealing in a NH3 atmosphere, resulting in a relatively high N concentrations into the films.baumvol  This method provides both near-interface and near-surface nitridation, which suggests different mechanisms for N incorporation or different nitriding species derived from NH3. The above thermal processing are performed at high temperatures ($`>`$ 800 C). Plasma nitridation is a promising method for making ultrathin oxynitride at lower temperatures ($``$ 300–400 C). Higher N concentrations and controlled distribution can be attained with this method,watanabe  typically using ions and radicals derived from N2 and NH3 as nitrogen sources.gusev  Additionally, nitridation by energetic particles (N ions) provides high N concentrations much closer to the near-surface region, with little or no nitrogen at the SiO2/Si interface.green  Although the nitridation mechanisms to make ultrathin SiO2 films are well known at the few layer level, less is known about the diffusing mechanism of the nitriding species and their reactions with the oxide at the atomic level.

In this work the energetics and diffusing properties of the SiO2 thermal nitridation are studied from first-principles total-energy calculations. We have considered the N2, NH and NO molecules as well as atomic N in different charge states as the nitriding species reacting and diffusing through the SiO2 network. The outline of the paper is as follows. Section II describes the theoretical procedure. Our results for the interaction of the nitriding species with the SiO2 network is presented in Sec. IIIA. The diffusivity of the nitriding species through SiO2 is presented in Sec. IIIB. In Sec. IIIC we discuss the spin-dependent diffusion reactions of NH and atomic N with the SiO2 network. Finally, in Sec. IV we show our conclusions.

## II theoretical method

Our calculations were performed in the framework of the density functional theory,dft  using a basis set of numerical atomic orbitals as implemented in the SIESTA code.siesta  We have used a split-valence double-$`\zeta `$ basis set plus the polarization functions as well as standard norm-conserving pseudopotentials.pseudo  For the exchange-correlation potential we adopt the generalized gradient approximation.pbe  We used a 72-atom $`\alpha `$-quartz supercell and the $`\mathrm{\Gamma }`$ point for the Brillouin zone sampling. The positions of all the atoms in the supercell were relaxed until all the force components were smaller than 0.05 eV/Å. We also consider neutral and singly charged species, where the neutrality of the cell is always maintained by introducing a compensating background charge. Spin-polarization effects are included throughout the calculation since they are important for the correct description of atomic and molecular reaction processes in SiO2.prl2-us  We initially study the energetics and structural properties of N2, NH, NO, and atomic N in the largest interstitial site of $`\alpha `$-quartz for three different charge states ($`+,0,`$). We explore possible reactions that these species may undergo with the network as well as their diffusivities in $`\alpha `$-quartz.

## III results and discussion

### III.1 Incorporation of nitriding species into the SiO2 network

Thermal processing of SiO2 in N2O and NO atmospheres shows that the NO molecule is the species which diffuses through the oxide, being incorporated at the Si/SiO2 interface.lu  In our calculations we find that neutral NO and NO+ do not react with the SiO2 network, remaining at the interstitial position and being, in this way, able to diffuse through the oxide as experimentally observed. However, NO- is trapped by the network forming a structure where the N atom of the molecule is bound to two fourfold coordinate Si atoms of SiO2, as shown in Fig. 1(a).

The binding energy of NO-, calculated as the difference in energy between the bound and the free-interstitial configurations for the same charge state, is found to be 1.3 eV. The Si-N and N-O bond lengths are 2.26 and 1.23 Å, respectively, whereas the Si-Si distance decreases by about 6% with respect to the equilibrium SiO2 structure. For interstitial NO and NO+ the N-O bond lengths are 1.17 and 1.13 Å, respectively.

The NH radical seems to be the most likely diffusing species after thermal dissociation of NH3 according to the dissociative reactions: NH3 $``$ NH2 \+ H $``$ 4.5 eV and NH2 $``$ NH + H $``$ 3.9 eV. Although NH2 may be another diffusing species for the interface nitridation, it is a relatively larger molecule and it may suffer additional dissociations at near-surface SiO2 during thermal processing. According to our results, neutral NH in the gas phase has a spin triplet ($`S`$ =1) ground state whereas the singlet ($`S`$ =0) states is 2.06 eV higher in energy. However, inside the largest interstitial site of $`\alpha `$-quartz, this difference in energy between both spin configurations decreases to 1.04 eV, due to the interaction with the crystal field. We find that triplet NH does not react with the SiO2 network remaining relatively inert at the interstitial sites. However, singlet NH reacts quickly with the oxide forming a structure where the N atom of NH binds to both Si and O atoms of the oxide. This incorporation reaction is highly exothermic with an energy gain of 2.04 eV. In Section III C we discuss the possibility that NH might be incorporated in the SiO2 network via a triplet-to-singlet spin exchange.

Singly charged NH molecules are highly reactive in the SiO2 network forming bound configurations as shown in Fig. 1(b) and Fig. 1(c). The binding energies for NH- and NH+ are 3.2 and 2.7 eV, respectively, which suggest that these configurations are very stable favoring a SiO2 near-surface nitridation. We observe that the NH- bound configuration is similar to that previously found for NO-. However, the relaxation of the SiO2 network is larger for the NH- bound configuration \[see Fig. 1(b)\]. Here, both Si-N bond lengths are about 2.1 Å, whereas the Si-Si distance decreases by about 14% with respect to the perfect SiO2 showing a strong lattice relaxation. The N-H bond length is found to be 1.04 Å. In the bound NH+ configuration \[Fig. 1(c)\], the N atom binds to an O atom of the oxide keeping its bond to the H atom. The O-N and N-H bond lengths are 1.43 and 1.05 Å, respectively, forming a O-N-H angle of 103.

The N2 molecule is a product of the N2O gas decomposition at typical oxidation temperatures, being introduced in this way into SiO2 in thermal processing.green  N2 (and atomic N) may also be introduced at lower temperatures by plasma assisted methods.watanabe  Our results for N2 in SiO2 show that this molecule does not react with the oxide being relatively inert for the three charge states considered. Therefore, it may diffuse easily through the oxide reacting with the silicon at the Si/SiO2 interface or escaping from the films.

The N atom in free space has a quartet ($`S`$ =3/2) ground state. The difference in energy with respect to the doublet ($`S`$ =1/2) state is calculated to be $``$ 3 eV. However, for a N atom in the largest interstitial site of $`\alpha `$-quartz, this energy difference decreases to 0.76 eV. We find that quartet N does not react with the SiO2 network suggesting that it would be a diffusing species. However, doublet N reacts with the oxide being incorporated into SiO2 network forming a Si-N-O bond. This reaction is exothermic with an energy gain of 0.76 eV. In Section III C, we discuss the possibility that atomic N might be incorporated in the SiO2 network via a quartet-to-doublet spin exchange.

Singly charged N atoms are highly reactive in SiO2. N- binds to a fourfold coordinate Si atom forming an additional Si-N bond of 1.85 Å, as shown in Fig. 1(d). The N atom has a binding energy of 2.2 eV. On the other hand, N+ binds to an oxygen forming a O-N bond, as shown in Fig. 1(e). We find a O-N bond length of 1.39 Å with a N binding energy of 1.1 eV.

As a general trend, we can say that because of the ionic character of SiO2, charged species are trapped by the network. The positively (negatively) charged NO, NH and N species attach to O (Si) atoms of the oxide, forming strong bonds, with binding energies ranging from 1 to 3 eV. This suggests a mechanism for the high-density bulk and near-surface nitridation. On the other hand, the neutral species in their ground-state spin configurations do not react with the SiO2 network. Therefore, they are able to diffuse through the oxide.

### III.2 Diffusion of nitriding species in SiO2

We calculate the diffusion coefficient for the neutral species hopping through the larger channel of $`\alpha `$-quartz, normal to the $`c`$-axis. To calculate the migration barriers, we have followed the same procedure as described in our previous calculation of the O2 diffusion in $`\alpha `$-quartz.prl1-us  We fix one atom of the molecules at several points along the pathway joining neighboring interstitial sites of $`\alpha `$-quartz where the distance between them is $``$ 5 Å. All other atoms of the systems are allowed to relax. Our results for the total energy variations along this diffusion path are shown in Fig. 2.

Here, the zero distance indicates approximately the center of the largest interstitial site and the arrow, the place of closest approach to the network. As a general trend, we find an anisotropic energy profile through the migration path which can be associated to the asymmetry of neighboring interstitial sites. Fig. 2(a) shows the calculated total-energy variations of diffusing NO and N2; we observe that these species show similar global minima and height barriers along the pathway. However, N2 exhibits two local minima not found in the NO pathway, showing that the interactions between the crystal field and the molecular orbitals of the diffusing species may affect the diffusion energy profile. Nevertheless, we must consider that uncertainties are introduced by fixing one atom of the molecules in order to map the diffusion energy profiles. For NH and atomic N we find lower-energy barriers and shorter distances between minima, as compared with NO and N2 (see Fig. 2), suggesting higher diffusivities for these species.

We estimate the thermal diffusion coefficient or diffusivity for the nitriding species using the Arrhenius law, given by

$$D(T)=D_0\mathrm{exp}(E_a/kT).$$
(1)
Here, the prefactor is defined by $`D_0`$ = $`l{}_{}{}^{2}\nu `$/6 for a three-dimensional migration path, where $`l`$ is the hopping distance between minima and $`\nu `$ is the attempt frequency, $`kT`$ the Boltzmann constant times the temperature, and $`E_a`$ is the highest energy barrier of the migration path. $`\nu `$ is calculated from the energy profile of each species at the interstitial site (approximately the zero distance in Fig. 2), using the harmonic approximation, whereas $`E_a`$ and $`l`$ are obtained directly from the same figure.

Tab. 1 lists the values of these quantities as well as our results for the prefactor of each nitriding species. It is worth pointing out that we have considered a very specific migration pathway through $`\alpha `$-quartz. Other pathways may result in different migration barriers and diffusivities. In fact, recent calculations have shown major differences in the diffusivity of atomic hydrogen in different crystalline structures of SiO2.bongiorno ; tuttle  However, we find that our approach is valid to obtain informations on the relative diffusivities of the species under consideration.

Figure 3 shows the diffusivities of the nitriding species in $`\alpha `$-quartz as calculated from Eq. 1, for a range of temperatures typically used in thermal and plasma assisted methods.

Here we observe that NH and atomic N have the higher diffusivities in $`\alpha `$-quartz with increasing temperatures as compared with NO and N2, which suggest that they would be the best thermally-activated diffusing species in SiO2 and the most efficient for Si/SiO2 interface nitridation, as compared with NO and N2. According to our results, the ratio between NH and NO diffusivities at 800C is estimated to be $`D_{\mathrm{NH}}/D_{\mathrm{NO}}90`$. Assuming that NH and NO are the main diffusing species, our results agree well with the experimental finding of higher N concentrations at the interface obtained by thermal nitridation of SiO2 in NH3 as compared with thermal nitridation in NO.baumvol

### III.3 Spin-dependent diffusion reactions of NH and N in SiO2

As mentioned above, NH in the triplet state does not react with the SiO2 network remaining inert at interstitial sites. However, singlet NH reacts easily with the oxide being incorporated into the network. Because of this spin-dependent reaction of NH with the SiO2 network, we study the possibility that a diffusing NH may suffer a triplet-to-singlet spin conversion while approaching the oxide, resulting in its incorporation into the network. For this, we compute the potential-energy surface (PES) along a pathway joining the equilibrium position of interstitial NH and a Si-O bond of the SiO2 network, for both triplet and singlet spin states, as shown in Fig.4. The triplet PES in the figure is depicted along a direction perpendicular to the diffusion pathway shown in Fig. 2, however, both pathways intercept at the interstitial equilibrium configuration of NH (zero distance in Fig. 4).

The probability that the system changes from the triplet to the singlet PES may be estimated by the Landau-Zener theory.zener  This theory has been recently used to describe spin effects in the adsorption of O2 in the Si(001) surfacekato  and the O2 incorporation reaction in the Si/SiO2 interface.prl2-us  Considering that the NH is initially in the triplet diffusion PES, and is evolving towards the crossing region with a velocity $`v`$, the probability for a conversion to the singlet PES ($`P_{ts}`$) may be approximated by

$$P_{ts}=2[\mathrm{\hspace{0.17em}1}\mathrm{exp}(V^2/hv|F_1F_2|)],$$
(2)
where $`V`$ is the triplet-to-singlet spin-orbit matrix element of NH ($`X^3\mathrm{\Sigma }^{}b^1\mathrm{\Sigma }^+`$) of 65.1 cm-1,yarkony  $`F_1`$ and $`F_2`$ are the slopes of the two PES at the crossing point and $`h`$ is the Planck’s constant. $`v`$ is estimated from the NH center-of-mass thermal velocity at 800 C, a typical annealing temperature. $`F_1`$ and $`F_2`$ are obtained from the triplet and singlet curves at the crossing region (see Fig. 2). Thus, the probability for a triplet-to-singlet conversion is found to be $`P_{ts}`$ = 9.3$`\times `$10-4. This means that triplet NH in a single passage through the crossing point has a small probability to change to the singlet PES. However, as the system is thermally activated, many passages of NH through the crossing point will be performed. In order to quantify the spin-conversion events for NH molecules approaching the SiO2 network at a given temperature, we estimate the ratio between the rate of NH following the triplet diffusion PES ($`\mathrm{\Gamma }_t`$) and the rate of NH changing from triplet to singlet PES at the crossing point ($`\mathrm{\Gamma }_{ts}`$). Assuming that the thermally-activated systems follow the Arrhenius law, the reaction rates can be written as

$$\mathrm{\Gamma }_t=\mathrm{\Gamma }_0\mathrm{exp}(\mathrm{\Delta }E_t/kT)$$
(3)
and

$$\mathrm{\Gamma }_{ts}=\mathrm{\Gamma }_0[\mathrm{exp}(\mathrm{\Delta }E_p/kT)]\times P_{ts}.$$
(4)
Here, $`\mathrm{\Gamma }_0`$ is the frequency prefactor; $`\mathrm{\Delta }E_t`$ is the energy barrier for the triplet diffusion PES obtained from Fig. 2(b) ($`\mathrm{\Delta }E_t`$ = 0.5 eV) and $`\mathrm{\Delta }E_p`$ is the energy difference between the lowest-energy equilibrium configuration of the triplet NH and the crossing point, obtained from Fig. 4 ($`\mathrm{\Delta }E_p`$ = 0.1 eV). For a temperature of 800 C, we obtain for our calculated $`P_{ts}`$ that $`\mathrm{\Gamma }_t/\mathrm{\Gamma }_{ts}14`$, which indicates that NH will proceed preferentially along the triplet diffusion PES.

As the incorporation of NH into the oxide due to the spin exchange is also likely to occur (an average of one in 14 events), we study three possible thermally-activated diffusion-reaction mechanisms for an incorporated singlet NH at 800 C: (i) NH diffuses along the SiO2 network by a hopping mechanism. The rate is estimated by Eq. 3, substituting $`\mathrm{\Delta }E_t`$ by a calculated hopping energy barrier ($`\mathrm{\Delta }E_h`$ = 2.2 eV). We find a hopping rate of $`\mathrm{\Gamma }_h`$ = $`\mathrm{\Gamma }_0`$(4.6$`\times `$10-11). (ii) NH is released from the network following the singlet PES. This reaction rate is estimated by

$$\mathrm{\Gamma }_s=\mathrm{\Gamma }_0[\mathrm{exp}(\mathrm{\Delta }E_s/kT)]\times (1P_{ts}),$$
(5)
where $`\mathrm{\Delta }E_s`$ is the singlet PES energy barrier obtained from Fig. 4 ($`\mathrm{\Delta }E_s`$ = 2.0 eV). We find that $`\mathrm{\Gamma }_s`$ = $`\mathrm{\Gamma }_0`$(4.0$`\times `$10-10). (iii) NH is released from the network changing from the singlet to the triplet PES at the crossing point. The reaction rate is estimated by Eq. 4, where $`\mathrm{\Delta }E_p`$ is now the difference between the energies at the singlet-triplet crossing point and at the incorporated NH equilibrium configuration, obtained from Fig. 4 ($`\mathrm{\Delta }E_p`$ = 1.05 eV). We find that $`\mathrm{\Gamma }_{st}`$ = $`\mathrm{\Gamma }_0`$(1.1$`\times `$10-8). According to these results, the most likely diffusion mechanism for an incorporated singlet NH in SiO2 would be mediated by the reaction (iii), i.e., NH leaves the network changing from the singlet to the triplet PES at the crossing point and then diffuses through SiO2 as a triplet NH. The two other mechanisms are less likely, as can be verified by the ratios $`\mathrm{\Gamma }_{st}/\mathrm{\Gamma }_h240`$ and $`\mathrm{\Gamma }_{st}/\mathrm{\Gamma }_s28`$.

Similarly to NH, we find a spin-dependent diffusion reaction for atomic N with the SiO2 network. According to our results, the N atom in the ground quartet state does not react with the network remaining at interstitial sites, whereas, in the doublet state, the N atom is incorporated between a Si-O bond forming a structure similar to the peroxyl bridge of oxygenshamann . Therefore, we examine the possibility that the N atom, initially in the quartet state, changes the spin configuration to the doublet one, resulting in its incorporation into the oxide. Following the same procedure described above for NH, we compute the quartet and doublet PES for the N atom approaching the SiO2 network. Our results are shown in Fig. 5.

From Eq. 2 we obtain the probability for the spin conversion using for $`V`$ the quartet-to-doublet spin-orbit matrix element of the N atom ($`{}_{}{}^{4}P^2P`$), obtained from spectroscopy data of 13.8 cm-1. Thus, we find a quartet-to-doublet conversion probability $`P_{qd}`$ = 1.6 $`\times `$ 10-5. This probability corresponds to a single passage of the N atom through the crossing point. To estimate the number of spin-conversion events of thermally activated N atoms approaching the SiO2 network, we calculate the ratio between the rate of N following the quartet diffusion PES ($`\mathrm{\Gamma }_q`$) and the rate of N changing from doublet to singlet PES at the crossing point ($`\mathrm{\Gamma }_{qd}`$). To calculate $`\mathrm{\Gamma }_q`$ we use Eqs. 3 substituting $`\mathrm{\Delta }E_t`$ by the energy barrier for the quartet diffusion PES obtained from Fig. 2(b) ($`\mathrm{\Delta }E_q`$ = 0.6 eV). $`\mathrm{\Gamma }_{qd}`$ was estimated by Eqs. 4 substituting $`P_{ts}`$ by $`P_{qd}`$ and using $`\mathrm{\Delta }E_p`$ = 0.6 eV, the difference between the energies at the interstitial site and at the quartet-doublet crossing point, obtained from Fig. 5. For a temperature of 800 C, we find that $`\mathrm{\Gamma }_q/\mathrm{\Gamma }_{qd}6\times 10^4`$. This results indicates that the N atom will most likely proceed along the quartet PES, i.e., it diffuses through the SiO2 essentially without reacting with the network.

Although very unlikely, the reaction of a doublet N with the oxide due to the spin exchange may also occur. Again, following the same procedure described for NH, we have three possibilities for the doublet N diffusion-reaction mechanism once it is incorporated into the oxide: (i) The incorporated N diffuses through the SiO2 network by a hopping mechanism. From Eq. 3, substituting $`\mathrm{\Delta }E_t`$ by the a calculated hopping energy barrier ($`\mathrm{\Delta }E_h`$ = 1.8 eV), we find a reaction rate of $`\mathrm{\Gamma }_h`$ = $`\mathrm{\Gamma }_0`$(3.5$`\times `$10-9). (ii) N is released from the network following the doublet PES. From Eq. 5, substituting $`\mathrm{\Delta }E_s`$ by the the doublet PES energy barrier, obtained from Fig. 5 ($`\mathrm{\Delta }E_d`$ = 0.9 eV), and $`P_{ts}`$ by $`P_{qd}`$, we find $`\mathrm{\Gamma }_d`$ = $`\mathrm{\Gamma }_0`$(5.9$`\times `$10-5). (iii) N is released from the network changing from the doublet to the quartet PES at the crossing point. From Eq. 4, substituting $`P_{ts}`$ by $`P_{qd}`$ and using $`\mathrm{\Delta }E_p`$ = 0.6 eV, the difference between the energies at the interstitial site and at the quartet-doublet crossing point, obtained from Fig. 5, we find $`\mathrm{\Gamma }_{dq}`$ = $`\mathrm{\Gamma }_0`$(2.4$`\times `$10-8). Therefore, if a N atom is incorporated into the oxide by a quartet-to-doublet spin exchange, a rare event, it will be released from the network following the singlet PES, according to the reaction (ii). However, as the incorporation reaction of the doublet N is exothermic, it will be reincorporated in the network if the timescale for relaxation back to the quartet ground state is long enough. Finally, we find that the other two possible reactions are very unlikely as can be verified by the ratios $`\mathrm{\Gamma }_d/\mathrm{\Gamma }_h1.7\times 10^4`$ and $`\mathrm{\Gamma }_d/\mathrm{\Gamma }_{dq}2.5\times 10^3`$.

## IV conclusions

We conclude that because of the ionic character of SiO2, charged species are trapped by the network, where positive (negative) species tend to attach to oxygen (silicon) atoms, forming strong bonds with binding energies as high as 3 eV. This suggests a mechanism for the N incorporation in bulk SiO2 observed in plasma assisted method, which would be associated to charged species surviving the first stages of the incorporation reactions occurring at the surface. Of course, these charged species may also transfer the charge to the network becoming neutral. According to our results, neutral species do not react with the network remaining at interstitial sites, therefore, they would be diffusing species in SiO2 able to reach the Si/SiO2 interface.

We estimate the diffusivities of neutral species through $`\alpha `$-quartz. Our results show that NH and atomic N have increasing diffusivities with temperature, and the highest one among the nitriding species, suggesting that they would be efficient for near interface nitridation. This result is in good agreement with the finding of high N concentration at the Si/SiO2 interface obtained by thermal processing in NH3. On the other hand, NO and N2 show relatively constant diffusivities in $`\alpha `$-quartz for the same range of temperatures. This result is also in good agreement with the finding of relatively low N concentration at the Si/SiO2 interface obtained by thermal processing in N2O, which is the main source of NO and N2 species.

We also study the incorporation reaction of NH and atomic N with the SiO2 network driven by a spin exchange mechanism. We find that, for a typical annealing temperature ($`T`$ = 800 C), a NH molecule diffusing through the triplet PES will have, on average, one in forteen possibilities to be incorporated into the network by a triplet-to-singlet conversion. The incorporated singlet NH will most likely return to the triplet PES after an inverse spin conversion. We also find that atomic N may be incorporated into the network by a quartet-to-doublet conversion while diffusing through the quartet PES, however, only an average of one in 6$`\times `$104 events will be successful. If this rare event occurs, the incorporated N will be released from the network following the doublet PES and, subsequently, reincorporated into the network due to the doublet exothermic process. However, this mechanism will be valid if the timescale for the relaxation to the quartet ground state is long enough.

###### Acknowledgements.

This work was supported by FAPESP and CNPq. We also would like to thank to CENAPAD-SP for computer time.


text:
# Untitled Document

SU-ITP-03/30 UCB-PTH-03/31 LBNL-54019 hep-th/0311053

Horizons and plane waves: A review

Veronika E. Hubenya and Mukund Rangamanib,c veronika@itp.stanford.edu, mukund@socrates.berkeley.edu

a Department of Physics, Stanford University, Stanford, CA 94305, USA

b Department of Physics, University of California, Berkeley, CA 94720, USA

c Theoretical Physics Group, LBNL, Berkeley, CA 94720, USA

Abstract

We review the attempts to construct black hole/string solutions in asymptotically plane wave spacetimes. First, we demonstrate that geometries admitting a covariantly constant null Killing vector cannot admit event horizons, which implies that pp-waves can’t describe black holes. However, relaxing the symmetry requirements allows us to generate solutions which do possess regular event horizons while retaining the requisite asymptotic properties. In particular, we present two solution generating techniques and use them to construct asymptotically plane wave black string/brane geometries.

November, 2003

1. Introduction

It is an incontrovertible fact that black holes provide an important window into quantum gravity. Knowledge of exact black hole solutions and their properties has greatly enhanced our understanding of gravitational physics and provided us with valuable intuition. Many of the puzzles and paradoxes associated with the unification of general relativity and quantum mechanics have their origins in the fascinating behaviour of black hole event horizons and hence, while we are aware of a rich set of solutions, it is always desirable to extend this list.

Black hole solutions in asymptotically “nice” (e.g.  maximally symmetric) spacetimes, such as Minkowski, de Sitter, and Anti de Sitter, have been known for decades, and have proved very fruitful in furthering our understanding. A good example is the Schwarzschild-AdS black hole, whose intricacies one may delve into using the well-known AdS/CFT correspondence . Indeed, much recent attention has been devoted to probing behind-the-horizon physics, and especially the singularity, via the CFT \[2,,3,,4,,5,,6,,7\]. Unfortunately, all of these efforts have been hampered by the fact that the AdS/CFT is a strong-weak coupling duality; in the regime where supergravity is valid, the gauge theory is strongly coupled, and therefore computationally intractable.

Plane waves, or more generally pp-waves, are another class of spacetimes with rather special properties. Since they admit a covariantly constant null Killing vector, all their curvature invariants vanish identically, rendering these spacetimes exact solutions to classical string theory (with vanishing $`\alpha ^{}`$ corrections). Nevertheless, they are causally quite nontrivial. For instance, remarkably enough, a large class of these has a one-dimensional null boundary \[8,,9,,10\].

It would be therefore very intriguing if these solutions could also admit event horizons, for this would yield exact black hole solutions in classical string theory with rather nontrivial asymptotics. Unfortunately, it turns out that this is not possible, as shown in  and reviewed below: pp-waves cannot admit event horizons. This however does not mean that there cannot exist black hole solutions with pp-wave asymptopia. After all, in all of the maximally symmetric spacetimes (flat, dS, and AdS), one also has to break some part of the symmetry in order to obtain black holes in these spacetimes. Indeed, below we will review two distinct methods for obtaining black string solutions which are asymptotically plane wave.

Apart from these solutions representing black holes with interesting asymptopia, they serve as important steps towards extending the recent BMN correspondence . The BMN correspondence may be viewed as a particular limit of the AdS/CFT correspondence, which on the gravity side generates a maximally supersymmetric plane wave, while on the gauge theory side limits to a large charge sector. This near-BPS regime allows one to do perturbative calculations on both sides of the correspondence, thus allowing greater computational control. It would be therefore very desirable to use this feature to probe the mysteries of quantum gravity, and as the first step, to study black holes in this set-up.

In particular, one may hope that a black hole with the particular plane wave asymptotics considered by  would correspond to some tractable modification on the gauge theory side, which we could then use to study such deep issues as singularity resolution, information paradox, etc. So far, such hope is founded mostly on analogy with similar extension of the original AdS/CFT correspondence: Putting a Schwarzschild black hole in AdS spacetime corresponds to thermalizing the gauge theory. Although the BMN regime contains conceptual puzzles of its own, studying black holes in this set-up would be an important endeavour. The requisite solutions have not yet been found; nevertheless, one may be optimistic, as the solutions discussed below already come quite close. In particular, metrically they have the desired asymptotics, though the matter support is different from that arising in the BMN correspondence.

This work does not contain any essentially new results; rather, it summarizes the main points of a series of papers , , and , all motivated by the above goal. We start in the next section by setting notation and establishing the concept of black holes in pp-waves. We then present a simplified proof that pp-waves cannot represent black holes1 We use the terminology black “holes” loosely, to denote all black objects, such as black strings/branes.  in Section 3. The following two sections discuss black strings in asymptotically plane wave spacetimes: extremal solutions with vacuum plane wave asymptotics in Section 4, and more robust, many-parameter family of black string solutions (including Schwarzschild-like one) with maximally symmetric plane wave asymptotics in Section 5. We end with a discussion in Section 6.

2. Definitions

To set the notation and re-emphasize terminology, we will first write down the pp-wave and plane wave metrics, and then discuss what we mean by a black hole with the corresponding asymptopia.

The pp-wave spacetimes are defined as spacetimes admitting a covariantly constant null Killing field. The metric in $`d`$ dimensions can be written as

$$ds^2=2dudvF(u,x^i)du^2+dx^idx^i,$$

where $`F`$ is an arbitrary function of $`u`$ and the transverse coordinates $`x^i`$ with $`i=1,\mathrm{},d2`$. The fact that $`\left(\frac{}{v}\right)^a`$ is a covariantly constant null Killing field ensures that all curvature invariants vanish in these spacetimes. Similarly, in the context of string theory, all the $`\alpha ^{}`$ corrections vanish.

Plane waves are a special subset of pp-waves, wherein the function $`F`$ is further restricted to be quadratic in the transverse coordinates, while still maintaining arbitrary $`u`$ dependence. In particular, plane waves can be written as

$$ds^2=2dudvf_{ij}(u)x^ix^jdu^2+dx^idx^i.$$

These solutions may be thought of as arising from a Penrose limit , which essentially zooms in on any null geodesic of any spacetime and reexpands the transverse coordinates. This induces an extra “planar” symmetry along the wavefronts. Further restricting $`f_{ij}(u)`$ can enhance this symmetry considerably; of greatest import will be the maximally symmetric plane waves, for which $`f_{ij}(u)=\mu ^2\delta _{ij}`$, and which have a large isometry group. A particular example of this type of solution is the BFHP plane wave in 10-dimensions .

We have discussed the metric, but to specify the full solution, one also needs to specify the matter content. Since the only nonvanishing component of the Ricci tensor is $`R_{uu}=\frac{1}{2}_T^2F(u,x^i)`$, we see that for vacuum spacetimes, $`F(u,x^i)`$ must be harmonic in the transverse coordinates. For plane waves, this translates into $`f_{ij}`$ being traceless, which in turn implies that nontrivial vacuum plane waves cannot be spherically symmetric; and conversely, the maximally symmetric plane waves must have some matter support2 Below, we will use the notation $`𝒱_d`$ to denote the vacuum plane waves, and $`𝒫_d`$ to denote the maximally symmetric plane waves, in $`d`$ dimensions..

Nevertheless, to ascertain the presence of black holes (i.e. to find whether or not a given spacetime admits an event horizon), it of course suffices to consider the properties of the metric alone, since that is what determines the causal properties of the solution. Accordingly, in the next section, we will consider general pp-wave metrics without requiring them to be solutions of any particular theory.

Before proceeding to prove the absence of black holes in pp-waves, we first need to specify what we mean by black holes. A black hole, by definition, is a region inside event horizon; but an event horizon is well defined only in asymptotically flat spacetime, namely as the boundary of the causal past of the future null infinity (scri ). In other words, a given asymptotically flat spacetime cannot admit an event horizon if the past of scri contains the full spacetime (i.e. from every point of the spacetime, there exists a causal curve which reaches scri). In more general spacetimes, lacking universally-defined asymptotics, we can try to follow the spirit of this definition by replacing “scri” with “arbitrarily far” in spatial directions. While this is generally somewhat murky definition, as we explained in , it may be adopted for the pp-waves (2.1) as the following working definition:

Def: A pp-wave spacetime does not admit an event horizon iff from any point in the spacetime, say $`(u_0,v_0,x_0^i)`$, there exists a future-directed causal curve to some point $`(u_1,v_{\mathrm{}},x_{\mathrm{}}^i)`$, where $`u_1>u_0`$ is arbitrary, while $`v_{\mathrm{}},x_{\mathrm{}}^i\mathrm{}`$.

The important aspect is that not just $`v`$, but also at least one of the transverse coordinates, $`x^i`$, gets arbitrarily big along a causal curve3 Since the fact that $`\left(\frac{}{v}\right)^a`$ is null and Killing implies that it describes orbits of null geodesics moving in the $`v`$ direction, the criterion that from any point in such a spacetime there is a causal curve attaining arbitrarily large $`v`$ is trivially satisfied. Furthermore, the crucial fact that the coordinate chart used in (2.1) covers the full spacetime makes this definition meaningful.. We will in fact use a stronger version of this criterion; namely, we will require $`u_1=u_0+\epsilon `$, for arbitrarily small $`\epsilon >0`$. This allows us to use the criterion in greater generality, in particular even in the cases where the spacetime terminates at some finite $`u`$, i.e., $`F(u,x^i)\mathrm{}`$ as $`uu_{\mathrm{}}<\mathrm{}`$.

3. No horizons in pp-waves

We will now use the above definition to demonstrate why pp-waves cannot admit horizons, and therefore cannot be black holes. This was motivated for plane waves and proved for general pp-waves in ; here we will present a simplified version of the proof, which applies for all spacetimes (2.1) with $`F(u,x^i)0`$, and refer the reader to  for the more general proof.

The lack of horizons in plane waves is very simple to understand intuitively: plane waves have a planar symmetry which precludes any special position at which the horizon could be4 This of course doesn’t mean that there can’t be observer-dependent horizons, such as in Rindler space or de Sitter; however, since Rindler horizons exist in any causally well-behaved spacetime, here we shall be concerned only with the black hole “event” horizons. . Alternately, one can argue that any plane wave is a Penrose limit of some spacetime, but event horizons cannot be retained under a Penrose limit, as the latter loses the global information about the spacetime. Hence, we will present a simplified version of the no-horizon proof for the more general pp-wave spacetimes; the fact that plane waves can’t have horizons then follows immediately as a corollary.

As indicated above, in order to demonstrate the absence of horizons, it suffices to show that from any  point $`p_0=(u_0,v_0,x_0^i)`$ of the spacetime, there exists a future-directed, causal curve $`\gamma `$ (i.e. one along which $`\dot{u}>0`$ and $`2\dot{u}\dot{v}F(u,x^i)\dot{u}^2+\dot{x}^i\dot{x}^i0`$) which reaches arbitrarily large values of $`r`$ and $`v`$ in arbitrarily small $`\mathrm{\Delta }u`$. One can construct such a curve $`\gamma `$ explicitly, as demonstrated in ; however, there is a more powerful and elegant technique which proceeds by introducing a fiducial metric, with smaller “light cones” than those of the physical spacetime we are interested in. Any curve which is causal in the fiducial metric will then also have to be causal in the physical one. The advantage of this observation is that by selecting appropriate fiducial metric, the construction of causal curves with the requisite properties is rendered much easier.

If $`F(u,x^i)`$ is non-negative everywhere, such a convenient fiducial metric is simply the flat spacetime, which corresponds to the pp-wave metric (2.1) with $`F(u,x^i)0`$. This translates into finding a curve $`\gamma (\lambda )`$ such that

$$\begin{array}{cc}& \gamma (0)=(u_0,v_0,x_0^i)\hfill \\ & \gamma (1)=(u_0+\epsilon ,v_{\mathrm{}},x_{\mathrm{}}^i)\hfill \\ \hfill \mathrm{and}& 2\dot{u}\dot{v}+\dot{x}^i\dot{x}^i0\hfill \end{array}$$

In flat spacetime, this is easily achieved by considering a “straight line” between the points $`p_0\gamma (0)`$ and $`p_{\mathrm{}}\gamma (1)`$, and the causal relation simply integrates to

$$2\mathrm{\Delta }u\mathrm{\Delta }v+\mathrm{\Delta }x^i\mathrm{\Delta }x^i0$$

The desired causal curve can then be obtained by the following series of steps:

$``$ Pick any point $`p_0=(u_0,v_0,x_0^i)`$ in the spacetime.

$``$ Choose arbitrarily large $`x_{\mathrm{}}^i`$ (or equivalently, arbitrarily large $`\mathrm{\Delta }x^i`$).

$``$ Choose $`\mathrm{\Delta }u=\epsilon `$ arbitrarily small (but positive, so that $`\gamma `$ is future-directed).

$``$ Since (3.1) implies that $`\gamma `$ will be causal if $`\mathrm{\Delta }v\frac{\mathrm{\Delta }x^i\mathrm{\Delta }x^i}{2\epsilon }`$, choose arbitrarily large $`v_{\mathrm{}}`$ such that

$$v_{\mathrm{}}\frac{\mathrm{\Delta }x^i\mathrm{\Delta }x^i}{2\epsilon }+v_0.$$

This construction then automatically gives the requisite causal curve in the physical spacetime (2.1) as well, thereby proving that pp-waves cannot admit event horizons. As mentioned earlier,  generalizes this proof to arbitrary $`F(u,x^i)`$.

The no-go theorem for horizons in pp-wave metrics is rather disappointing from the standpoint of finding black holes in string theory described by exact classical solutions which receive no $`\alpha ^{}`$ corrections. However, this does not necessarily imply that there are no such solutions, since the pp-waves are not the most general spacetimes with vanishing curvature invariants; cf. e.g. \[17,,18,,19\]. It would be interesting to repeat our analysis for these more general spacetimes.

4. Horizons in spacetimes with null isometry

Having shown that spacetimes with a covariantly constant null Killing field (pp-waves) do not admit event horizons, we can now ask whether relaxing the covariantly constant requirement enables us to construct spacetimes with horizons which nevertheless have a globally null Killing vector. Naively, one might expect that even null isometry is too restrictive to allow for horizons; but this is clearly not the case, as there are well-known examples of extremal asymptotically flat black branes with null isometry.

Although these solutions are asymptotically flat, it is not difficult to write down asymptotically vacuum plane wave black branes, as discussed in  and as we briefly review below. The “trick” is to use a solution generating technique, originally developed by \[20,,21\], called the Garfinkle-Vachaspati (GV) method. Given a solution to Einstein’s equations (in general, with some appropriate matter content), which admits a hypersurface-orthogonal null Killing field compatible with the matter content, one can deform the solution to a new one with the same matter fields. In particular, the curvature invariants of the deformed solution are identical to the parent solution. The idea is that given a solution with an appropriate set of symmetries, one can essentially “linearize” Einstein’s equations, which will then allow one to superpose solutions.

A trivial example of using the GV technique is to apply it to flat space to obtain a vacuum plane wave, or more generally, a vacuum pp-wave. In particular, starting with the metric (2.1) (with $`f=0`$ for flat space), the GV solution generating technique essentially amounts to adding a term $`F(u,x^i)du^2`$, where $`F`$ is harmonic, to the metric. This by definition corresponds to a pp-wave. To use the GV construction for the problem at hand, the strategy is to start with a solution with a regular horizon and add a term which preserves the integrity of the horizon, but changes the asymptotics in the required fashion. As mentioned above, the (asymptotically flat) extremal black branes in ten (IIA/IIB) or eleven dimensional supergravity satisfy the necessary criteria for the GV construction to be applicable; but not all have a regular horizon. Specifically, only the D3, M2, and M5 branes have a regular horizon, and of these, only the M2-brane solution is capable of producing a spacetime wherein the regular event horizon cloaks a singularity; so we will restrict our attention to this case (the other cases were briefly discussed in ).

To deform the M2-brane solution in eleven dimensional supergravity so that the asymptotic behaviour is $`𝒱_{10}\times 𝐑`$, whilst retaining the nature of the near-horizon geometry and the singularity intact, we proceed as follows. We start with the M2-brane solution to 11-dimensional supergravity, given by

$$\begin{array}{cc}\hfill ds^2& =H(r)^{\frac{2}{3}}\left(2dudv+dx^2\right)+H(r)^{\frac{1}{3}}\left(dr^2+r^2d\mathrm{\Omega }_7^2\right)\hfill \\ \hfill F_4& =\left(\frac{dH(r)^1}{dr}\right)dudvdxdr.\hfill \end{array}$$

where we have combined time with one of the spatial directions along the brane to write the metric in a more convenient form; to wit, both $`\left(\frac{}{v}\right)^a`$ and $`\left(\frac{}{u}\right)^a`$ are null Killing vectors and we can also verify that they are hypersurface-orthogonal. $`H(r)=1+\frac{Q^6}{r^6}`$ is a harmonic function in the transverse eight-dimensional space. The horizon is at $`r=0`$ in these coordinates. To see the location of the singularity, it is best to define a new coordinate $`\zeta =r^2`$. The singularity is located at the zero of $`H(\zeta )`$, i.e., $`\zeta =Q^2`$.

We can now apply the GV construction to write a new (“deformed”) metric as

$$ds^2=H(r)^{\frac{2}{3}}\left(2dudv+dx^2\mathrm{\Psi }(u,x,r,\mathrm{\Omega }_7)du^2\right)+H(r)^{\frac{1}{3}}\left(dr^2+r^2d\mathrm{\Omega }_7^2\right)$$

where the new term $`\mathrm{\Psi }`$ must be harmonic, $`^2\mathrm{\Psi }=0`$. Writing $`\mathrm{\Psi }(u,x,r,\mathrm{\Omega }_7)=\xi _{kL}(u)e^{ikx}\psi _k\mathrm{}(r)Y_L(\mathrm{\Omega }_7)`$ with arbitrary functions $`\xi _{kL}(u)`$, and $`Y_L(\mathrm{\Omega }_7)`$ denoting the spherical harmonics with $`L`$ being a label for the set of angular momenta on the seven sphere with principal angular momentum $`\mathrm{}`$, we find the radial equation

$$\frac{d^2\psi _k\mathrm{}(r)}{dr^2}+\frac{7}{r}\frac{d\psi _k\mathrm{}(r)}{dr}\left(\frac{\mathrm{}(\mathrm{}+6)}{r^2}+k^2H(r)\right)\psi _k\mathrm{}(r)=0$$

For the case of $`k=0`$, i.e., requiring $`\left(\frac{}{x}\right)^a`$ to be a Killing vector in the deformed geometry, the problem reduces to solving the Laplace equation in eight dimensional flat space. So we can pick the $`\mathrm{}=2`$ mode on the seven sphere to obtain a solution which is asymptotically plane wave. For example, parameterizing the seven sphere by the coordinates such that $`\theta `$ corresponds to the azimuthal angle, we can choose $`\mathrm{\Psi }(u,x,r,\mathrm{\Omega }_7)=r^2\left(8\mathrm{cos}^2\theta 1\right)`$. Then

$$\begin{array}{cc}\hfill ds^2& =H(r)^{\frac{2}{3}}\left[2dudv+dx^2r^2\left(8\mathrm{cos}^2\theta 1\right)du^2\right]\hfill \\ & +H(r)^{\frac{1}{3}}\left[dr^2+r^2\left(d\theta ^2+\mathrm{sin}^2\theta d\mathrm{\Omega }_6^2\right)\right]\hfill \\ \hfill F_4& =\left(\frac{dH(r)^1}{dr}\right)dudvdxdr,\hfill \end{array}$$

is a solution to eleven dimensional supergravity, with the same curvature invariants as the M2-brane solution. In particular, the solution still has a regular horizon5 This is to be contrasted with added pp-wave like terms $`\mathrm{\Psi }(u,r)\frac{1}{r}`$, or having plane waves along the longitudinal directions of the brane, wherein one does encounter singularities at the horizon cf., , ,  at $`r=0`$. Furthermore, its asymptotic behaviour is that of a ten dimensional vacuum plane wave times an extra real line parameterized by $`x`$.

In passing, we note that when $`k0`$, the nature of the asymptotics changes quite dramatically. The asymptotic behaviour of the equation (4.1) can be analyzed to show that the solutions are Bessel functions, which are incompatible with the necessary $`r^2`$ behaviour. So by looking for solutions wherein we have some momentum along the brane world-volume directions we do not obtain a solution that looks like a plane-wave. In order to obtain a plane wave solution, our only choice is then to use the solution presented in (4.1), wherein we have an additional isometry corresponding to translations along $`\left(\frac{}{x}\right)^a`$. We note that extensions of the GV technique were also considered in , , and .

Although the above solution (4.1), where we could compactify along the $`x`$ direction, is interesting in its own right, in the bigger scheme of attempting to extend the BMN correspondence to BFHP black hole spacetimes, it falls short in two important aspects: it corresponds to an extremal, rather than a neutral, black hole; and the asymptotic region corresponds to a vacuum, rather than the maximally symmetric BFHP, plane wave. In the next section we will rectify the first shortcoming completely and the second one at least partially; but before presenting that construction, we will make a few more remarks.

As a first step to correcting the above-mentioned deficiencies, one can try to look for a neutral black hole solution in asymptotically vacuum plane wave spacetime. One would expect that there be such a solution, since after all, one might achieve it physically by colliding two oppositely charged extremal black strings discussed above. Indeed, assuming the same symmetries as for the “seed” asymptotically flat extremal black string (namely globally null Killing vector and transverse spherical symmetry), all vacuum solutions can be found analytically. This was done in , where the new vacuum solutions were written down explicitly and their properties analysed. Interestingly, it turns out that (independently of their asymptotic behaviour) none of these solutions can admit horizons; they are in fact nakedly singular. This exemplifies the remarkable point that restricting ourselves to vacuum Einstein’s equations severely restricts the nature of the possible solutions, and in particular eliminates the causally nontrivial ones.

At the first sight, this result may seem paradoxical in light of the naive argument of constructing vacuum black strings by colliding oppositely-charged ones, but actually there is no contradiction: the collision process would spoil the null symmetry. In fact, this might be expected already from the explicit construction outlined above: only extremal black branes admit a null symmetry, so we can’t start with a non-extremal solution instead.

The second shortcoming, that the asymptotics correspond to vacuum, rather than the maximally symmetric plane wave (in the transverse directions), is in fact a necessary consequence of using the GV construction to generate the solution from asymptotically flat spacetime: the matter content is unchanged, so vacuum asymptotics can only lead to vacuum asymptotics. In the next section, this will be contrasted by a different solution generating technique, which in fact generates the maximally symmetric (nonvacuum) plane wave starting from the flat space.

5. Plane wave black strings

In the previous section we have seen that there exist asymptotically vacuum plane wave solutions with horizons and null isometry; however, the black branes were extremal and the asymptopia non-maximally symmetric. To do better, we should further relax the required symmetries of the solution; namely, we now drop the globally null isometry. As is often the case, the price we pay for breaking symmetries is manifested in the increased difficulty of finding the solutions. Solving the ansatz by brute-force is forbiddingly messy; but fortunately, one can once again resort to an elegant trick of using a particular solution generating technique, which we call the “Null Melvin Twist” .

Our method is based on the observation of  that certain class of plane wave geometries can be generated by applying a sequence of manipulations to Minkowski space. By applying the same sequence of manipulations starting from a black string solution, we are able to generate a large class of black string deformations of plane wave geometries with a regular horizon. These solutions are characterized by the mass density of the black string and the scale of the plane wave geometry in the rest frame of the black string. For dimensions greater than six, the deformation due to the presence of the black string decays at large distances in the direction transverse to the string. Hence in these cases, our solutions describe geometries with (radially) plane wave asymptotics. However, the solutions described will be plane-wave geometries which are supported by 3-form flux rather than 5-form flux as is desirable for the BMN correspondence.

The specific set of steps is quite simple, and requires only a starting 10 dimensional supergravity solution (in NS-NS sector) with a constant-norm isometry $`\left(\frac{}{y}\right)^a`$. One then performs the following sequence of steps:

$``$ Boost the space-time along $`y`$ by $`\gamma `$

$``$ T-dualize along the $`y`$ coordinate

$``$ Twist by making a change of coordinates6 Here we write the metric on the $`𝐒^7`$ in terms of polar coordinates $`d\mathrm{\Omega }_7^2=d\chi ^2+\frac{1}{4}\mathrm{cos}^2\chi d\mathrm{\Omega }_a^2+\frac{1}{4}\mathrm{sin}^2\chi d\mathrm{\Omega }_b^2`$ with $`d\mathrm{\Omega }_i^2d\theta _i^2+d\psi _i^2+d\varphi _i^2+2\mathrm{cos}\theta _id\psi _id\varphi _i`$, $`i=a,b`$, and introduce a symmetric 1-form $`\sigma \mathrm{cos}^2\chi (\mathrm{cos}\theta _1d\psi _1+d\varphi _1)+\mathrm{sin}^2\chi (\mathrm{cos}\theta _2d\psi _2+d\varphi _2)`$. $`\sigma \sigma +2\alpha dy`$

$``$ T-dualize back along $`y`$

$``$ Boost back along $`y`$ by $`\gamma `$

$``$ Finally, perform a double scaling limit, wherein the boost $`\gamma `$ is scaled to infinity and the twist $`\alpha `$ to zero keeping $`\beta \frac{1}{2}\alpha e^\gamma =`$ fixed.

As mentioned above, starting with the 10 dimensional Minkowski spacetime, $`ds_{str}^2=dt^2+dy^2+dr^2+r^2d\mathrm{\Omega }_7^2`$ with $`\mathrm{\Phi }=0,B=0`$, we obtain the plane wave

$$\begin{array}{cc}\hfill ds_{str}^2& =(1+\beta ^2r^2)dt^22\beta ^2r^2dtdr+(1\beta ^2r^2)dy^2+dr^2+r^2d\mathrm{\Omega }_7^2\hfill \\ \hfill \mathrm{\Phi }& =0,B=\frac{\beta r^2}{2}\left(dt+dy\right)\sigma \hfill \end{array}$$

where the usual form is obtained by letting $`u=t+y`$ and $`2v=ty`$.

Similarly, starting with the asymptotically flat Schwarzschild black string solution,

$$ds_{str}^2=f(r)dt^2+dy^2+\frac{1}{f(r)}dr^2+r^2d\mathrm{\Omega }_7^2$$

one obtains

$$\begin{array}{cc}\hfill ds_{str}^2& =\frac{f(r)\left(1+\beta ^2r^2\right)}{k(r)}dt^2\frac{2\beta ^2r^2f(r)}{k(r)}dtdy+\left(1\frac{\beta ^2r^2}{k(r)}\right)dy^2\hfill \\ & +\frac{dr^2}{f(r)}+r^2d\mathrm{\Omega }_7^2\frac{\beta ^2r^4(1f(r))}{4k(r)}\sigma ^2\hfill \\ \hfill e^\mathrm{\Phi }& =\frac{1}{\sqrt{k(r)}},B=\frac{\beta r^2}{2k(r)}\left(f(r)dt+dy\right)\sigma \hfill \end{array}$$

where $`f(r)1\frac{M}{r^6}`$ and $`k(r)1+\frac{\beta ^2M}{r^4}`$.

The solution (5.1) is very simple. By inspection, if we set $`M`$ to zero the solution reduces to the maximally symmetric plane wave $`𝒫_{10}`$. On the other hand, setting $`\beta =0`$ will reduce the solution to the black string solution (5.1). For all finite values of $`M`$, there is a curvature singularity at $`r=0`$, which can be easily checked to be spacelike. More importantly, there is a regular horizon at

$$r_H=M^{1/6}$$

which persists for finite values of $`\beta `$. One can therefore interpret (5.1) as the black string deformation of $`𝒫_{10}`$. Furthermore, since both $`f(r)`$ and $`k(r)`$ asymptote to 1 as $`r`$ is taken to be large, the effect of $`M`$ decays at large $`r`$. Unlike the six dimensional solution described in  which deformed the geometry by a finite amount at large $`r`$, (5.1) is a black string solution which genuinely asymptotes to $`𝒫_{10}`$ (in the transverse directions).

A rather remarkable property of this solution concerns its thermodynamics. As discussed in , the area of the horizon in Einstein frame metric is given by

$$𝒜_H=LM^{7/6}\mathrm{\Omega }_7,$$

while a natural definition7 As discussed in , there is a normalization ambiguity. of temperature would evaluate to

$$T_H=\frac{3}{2\pi }M^{1/6}.$$

The first law of thermodynamics would then naturally allow us to interpret the parameter $`M`$ as the mass density of the black string. The remarkable fact about these quantities is that they are independent of the parameter $`\beta `$, i.e. the plane wave black string thermodynamics is the same as the usual asymptotically flat black string thermodynamics.

As discussed in , the solution (5.1) can be generalized to include rotations, charge, or more general twists, giving rise to a 13-parameter family of solutions, all with regular horizons and maximally symmetric plane wave asymptotics. Furthermore, one can also repeat the construction starting with black D$`p`$-branes, which generates plane wave $`𝒫_{11p}`$ asymptotics transverse to the brane.

Although these are all intriguing generalizations with diverse and interesting properties, for the purposes of extending the BMN story, it would be far more useful to generate solutions with asymptotics which are not only metrically $`𝒫_{10}`$, but also have the requisite matter content, namely the RR 5-form field strength. In our construction, we explicitly exploited the usual duality between off-diagonal metric components and magnetic fields, which is why we obtained solutions supported by NS-NS flux. (In IIB it is trivial to S-dualise to generate solutions supported by a combination of NS-NS and RR 3-form fluxes). However, since there is no way to geometrically engineer RR 5-form fluxes, we will have to work harder to generate solutions supported by the same.

Nevertheless, it is tempting to conjecture that the final solutions will have similar thermodynamic properties as the solutions described above. This observation is simply based on the fact that the deformation of asymptotics from flat space to plane wave form seems to have no apparent effect on the thermal properties.

6. Discussion

We have summarized a particular development of ideas, to date still incomplete, to construct asymptotically BMN black hole spacetimes. Having shown that pp-wave (or more specifically, plane wave) metrics cannot represent black holes, we have reviewed the construction of asymptotically plane wave black holes. The first solution-generating method (the GV construction) we used relied heavily on null isometry and preserved the matter content of the seed solution. As such, it only allowed us to construct extremal black strings with vacuum plane wave asymptopia. While interesting in its own right, a far more fruitful technique proved to be the Null Melvin Twist, which allowed us to generate a wide class of black strings with the metric asymptoting to the desired maximally symmetric plane wave. However, even in the latter construction, we only managed to generate solutions that were supported by 3-form fluxes (in ten dimensional supergravity).

There are many open questions that remain to be discussed in this general story. One obvious extension is to obtain solutions that have 5-form flux support. Another would be to find explicit black hole solutions rather than the black string solutions mentioned above. These appear to be sufficiently complicated to be tackled by brute-force solution of Einstein equations and we are not aware of any appropriate solution generating technique. If such a solution generating technique were to be uncovered, its utility in constructing general warped flux compactifications would be enormous.

At the same time there are many interesting avenues that are amenable to further study taking off from the solutions presented here. For instance, it is very intriguing that the plane wave deformation of the black string geometries appears to be “irrelevant” and it would be worthwhile to investigate the generality of this result. One should also study the causal properties of black strings in plane wave geometries to figure out whether there are any remnants of the exotic features seen in the causal structures of plane waves. Furthermore, these solutions provide an excellent setting to understand the notions of ADM mass and other conserved charges in backgrounds which are asymptotically plane wave.

Acknowledgements

It is a great pleasure to thank Aki Hashimoto, Oleg Lunin and Eric Gimon for collaboration. We gratefully acknowledge the hospitality of the Aspen Center for Physics and the Kavli Institute for Theoretical Physics, where parts of this project were completed. VH is supported by NSF Grant PHY-9870115, while MR acknowledges support from the Berkeley Center for Theoretical Physics and also partial support from the DOE grant DE-AC03-76SF00098 and the NSF grant PHY-0098840.

References

relax O. Aharony, S.S. Gubser, J. Maldacena, H. Ooguri, Y. Oz, Large N Field Theories, String Theory and Gravity, Phys. Rept. 323 (2000) 183, \[arXiv:hep-th/9905111\]. relax V. Balasubramanian and S. F. Ross, Holographic particle detection, Phys. Rev. D 61, 044007 (2000) \[arXiv:hep-th/9906226\]. relax J. Louko, D. Marolf and S. F. Ross, On geodesic propagators and black hole holography, Phys. Rev. D 62, 044041 (2000) \[arXiv:hep-th/0002111\]. relax J. M. Maldacena, Eternal black holes in Anti-de-Sitter, JHEP 0304, 021 (2003) \[arXiv:hep-th/0106112\]. relax P. Kraus, H. Ooguri and S. Shenker, Inside the horizon with AdS/CFT, Phys. Rev. D 67, 124022 (2003) \[arXiv:hep-th/0212277\]. relax T. S. Levi and S. F. Ross, Holography beyond the horizon and cosmic censorship, Phys. Rev. D 68, 044005 (2003) \[arXiv:hep-th/0304150\]. relax L. Fidkowski, V. Hubeny, M. Kleban and S. Shenker, The black hole singularity in AdS/CFT, arXiv:hep-th/0306170. relax D. Berenstein and H. Nastase, On lightcone string field theory from super Yang-Mills and holography, \[arXiv:hep-th/0205048\]. relax D. Marolf and S. F. Ross, Plane waves: To infinity and beyond!, \[arXiv:hep-th/0208197\]. relax V. E. Hubeny and M. Rangamani, Causal structures of pp-waves, JHEP 0212, 043 (2002) \[arXiv:hep-th/0211195\]. relax V. E. Hubeny and M. Rangamani, No horizons in pp-waves, JHEP 0211, 021 (2002) \[arXiv:hep-th/0210234\]. relax D. Berenstein, J. M. Maldacena and H. Nastase, Strings in flat space and pp waves from N = 4 super Yang Mills, JHEP 0204, 013 (2002) \[arXiv:hep-th/0202021\]. relax V. E. Hubeny and M. Rangamani, Generating asymptotically plane wave spacetimes, JHEP 0301, 031 (2003) \[arXiv:hep-th/0211206\]. relax E. G. Gimon, A. Hashimoto, V. E. Hubeny, O. Lunin and M. Rangamani, Black strings in asymptotically plane wave geometries, JHEP 0308, 035 (2003) arXiv:hep-th/0306131. relax R. Penrose, Any spacetime has a planewave as a limit, in Differential geometry and relativity, pp 271-275, Reidel, Dordrecht, 1976. relax M. Blau, J. Figueroa-O’Farrill, C. Hull and G. Papadopoulos, A new maximally supersymmetric background of IIB superstring theory, JHEP 0201, 047 (2002) \[arXiv:hep-th/0110242\]. relax V. Pravda, A. Pravdova, A. Coley and R. Milson, All spacetimes with vanishing curvature invariants, Class. Quant. Grav. 19, 6213 (2002) \[arXiv:gr-qc/0209024\]. relax A. A. Coley, A class of exact classical solutions to string theory, Phys. Rev. Lett. 89, 281601 (2002) \[arXiv:hep-th/0211062\]. relax A. Coley, R. Milson, N. Pelavas, V. Pravda, A. Pravdova and R. Zalaletdinov, Generalized pp-wave spacetimes in higher dimensions, Phys. Rev. D 67, 104020 (2003) \[arXiv:gr-qc/0212063\]. relax D. Garfinkle and T. Vachaspati, Cosmic String Traveling Waves, Phys. Rev. D 42, 1960 (1990). relax D. Garfinkle, Black String Traveling Waves, Phys. Rev. D 46, 4286 (1992) \[arXiv:gr-qc/9209002\]. relax N. Kaloper, R. C. Myers and H. Roussel, Wavy strings: Black or bright?, Phys. Rev. D 55, 7625 (1997) \[arXiv:hep-th/9612248\]. relax G. T. Horowitz and H. S. Yang, Black strings and classical hair, Phys. Rev. D 55, 7618 (1997) \[arXiv:hep-th/9701077\]. relax D. Brecher, A. Chamblin and H. S. Reall, AdS/CFT in the infinite momentum frame, Nucl. Phys. B 607, 155 (2001) \[arXiv:hep-th/0012076\]. relax J. T. Liu, L. A. Pando Zayas and D. Vaman, On horizons and plane waves, \[arXiv:hep-th/0301187\]. relax N. Ohta, K. L. Panigrahi and Sanjay, Intersecting branes in pp-wave spacetime, \[arXiv:hep-th/0306186\]. relax D. Brecher, U. H. Danielsson, J. P. Gregory and M. E. Olsson, Rotating black holes in a Goedel universe, JHEP 0311, 033 (2003) \[arXiv:hep-th/0309058\]. relax M. Alishahiha and O. J. Ganor, Twisted backgrounds, pp-waves and nonlocal field theories, JHEP 0303, 006 (2003) \[arXiv:hep-th/0301080\]. relax E. G. Gimon and A. Hashimoto, Black holes in Goedel universes and pp-waves, Phys. Rev. Lett. 91, 021601 (2003) \[arXiv:hep-th/0304181\].


text:
# Unsupervised Grammar Induction in a Framework of Information Compression by Multiple Alignment, Unification and Search

## 1 Introduction

This paper describes a novel approach to unsupervised grammar induction that has been developed within a research programme whose overarching goal is the integration of diverse functions—learning, recognition, reasoning and others—within one relatively simple framework. This has had a substantial impact on the way in which the learning processes are organised.

The new framework called information compression by multiple alignment, unification and search (ICMAUS) originated in earlier research developing the SNPR model of grammar induction . Without supervision, the SNPR model successfully learns artificial context-free phrase-structure grammars (CF-PSGs) using a technique of ‘hierarchical chunking’ combined with a search for disjunctive (part of speech) categories and processes for generalising grammatical rules and correcting over-generalisations.

In the ICMAUS programme, the aim has been to match or exceed these capabilities within a system that has been generalised to model a range of other aspects of computing, AI, mathematics and logic. It became apparent at an early stage that this would mean a radical reorganisation of the SNPR model. In the ICMAUS framework a concept of multiple alignment—to be described—has replaced hierarchical chunking as the predominant mode of organisation. With this new orientation, the system provides an interpretation for concepts in computing, mathematics and logic and it has a range of AI capabilities described in  and earlier papers cited there. The present paper describes how the system has been developed for unsupervised learning of grammars.

A much fuller account of the research described here may be found in , available from http://www.cognitionresearch.org.uk/papers/ul/ul.htm.

### 1.1 Relationship with Other Research on Grammar Induction

This research extends the tradition of distributional linguistics pioneered by  and others.

At the heart of ICMAUS system are principles of Minimum Length Encoding (MLE) pioneered by  (see also ). In this framework, grammar induction is conceived as a process of optimisation rather than a process of identifying a target grammar ‘in the limit’ as postulated by . In the MLE framework, there is no target grammar, merely a process of searching for grammars that are ‘good’ in terms of MLE principles.

Recent studies that are, perhaps, most closely related to the present research include: . Not all of these studies have adopted MLE principles but they deal with issues and processes that relate to the present research. The idea of combining learning with parsing—to be described—has also been developed by Nakamura (see  and this workshop).

Compared with other work on unsupervised learning of grammar-like structures, the most distinctive features of the ICMAUS research are:

* The integration of learning with other areas of AI, computation, mathematics and logic.
* The multiple alignment concept as it has been developed in the ICMAUS framework, described below. There is, however, a clear affinity with ‘alignment-based learning’ .

## 2 The ICMAUS Framework

In the ICMAUS framework, all knowledge is stored as patterns: arrays of symbols in one or two dimensions.111In work to date, the focus has been on one-dimensional patterns. Despite the simplicity of this format, it is possible within the ICMAUS system to represent several different kinds of knowledge including context-free and context sensitive grammars, networks, trees, if-then rules and others.

Given the generality of this format for knowledge, the learning techniques described in this paper are relevant to the learning of any kind of knowledge, not just ‘grammars’, narrowly conceived.

The ICMAUS framework is intended as an abstract model of any kind of system for computing or cognition, either natural or artificial. In broad terms, the system works by receiving ‘New’ information from its environment and transferring it to a repository of ‘Old’ information. At the same time, it tries to compress the information as much as possible by finding patterns that match each other and merging or ‘unifying’ patterns that are the same. In these broad terms it is similar to a ZIP program but it differs in the thoroughness of the search for ‘good’ unifications of patterns and in the ‘multiple alignment’ concept, to be described.

### 2.1 Multiple Alignment

The concept of multiple alignment in the ICMAUS framework has been borrowed from the field of bio-informatics and adapted as described in .

An example of an ICMAUS multiple alignment is shown in Figure 1. Row 0 contains the New pattern ‘o n e o f t h e m d o e s’ and all the other rows contain Old patterns, one pattern per row. By convention, the New pattern is always shown in row 0 but otherwise the assignment of patterns to rows is entirely arbitrary.

Apart from the pattern in row 8, the patterns from Old in this example are like re-write rules in a CF-PSG with the re-write arrow omitted. If we ignore row 8, the alignment shown in Figure 1 is very much like a conventional parsing, marking the main components of the sentence: words and phrases and the sentence pattern itself (shown in row 5).

Row 8 shows how the ‘discontinuous’ dependency that exists between the singular noun in the subject of the sentence (‘Ns’) and the singular verb (‘Vs’) can be marked within the alignment in a relatively direct manner. Despite the simplicity of the format for representing knowledge, the formation of multiple alignments enables the system to express ‘context sensitive’ aspects of language and other kinds of knowledge.

In each Old pattern there are two kinds of symbols: ID-symbols like ‘$`<`$’, ‘N’, ‘Np’, ‘0’ and ‘$`>`$’ in ‘$`<`$ N Np 0 t h e m $`>`$’ serve to identify the pattern and the remaining symbols (‘t h e m’ in this example) are C-symbols that represent the contents or substance of the pattern.

Much more detail, with many more examples, may be found in .

## 3 SP70

All the main components of the ICMAUS framework outlined in Section 2 are now realised within the SP70 software model (version 9.2). The model is able to abstract plausible grammars from sets of simple sentences without prior knowledge of word segments or the classes to which they belong, and the computational complexity of the model appears to be acceptable (Section 4). However, in its current form, the model has at least two significant shortcomings and some other deficiencies, discussed briefly in Section 6.

### 3.1 Objectives

In the development of this model, the main problems that have been addressed are:

* How to identify significant segments in the ‘corpus’ of raw data when the boundary between one segment and the next is not marked explicitly.
* How to identify disjunctive classes of syntactically-equivalent segments (e.g., ‘nouns’, ‘verbs’ and ‘adjectives’).
* How to combine the learning of segmental structure with the learning of disjunctive classes.
* How to learn segments and disjunctive classes through two or more levels of abstraction.
* How to generalize grammatical rules beyond the data and how to correct over-generalizations without feedback from a ‘teacher’ or the provision of ‘negative’ samples or the grading of the data from ‘easy’ to ‘hard’ (cf. ).

Solutions to these problems were found in the SNPR model  but, as noted earlier, the organisation of this model is quite unsuited to the wider goals of the present research—integration of diverse functions within one framework. The SP70 model (v. 9.2) provides solutions to the first three problems and partial solutions to the fourth and fifth problems. Further development is planned as indicated in Section 6, below.

### 3.2 Overall Structure of the Model

Figure 2 shows the high-level organisation of the SP70 model.

The function create\_multiple\_alignments() referred to in Figure 2 creates zero or more multiple alignments, each one comprising the current pattern from New (CPFN) and one or more patterns from Old. This function is essentially the same as the main component of the SP61 model, described quite fully in . Readers are referred to this source for a more detailed description of how multiple alignments are formed in the ICMAUS framework.

### 3.3 Deriving Patterns from Alignments

In operation 3.5 in Figure 2, the derive\_patterns() function is applied to a selection of the best alignments formed and, in each case, it looks for sequences of unmatched symbols within the alignment and also sequences of matched symbols.

Consider the alignment shown in Figure 3. From an alignment like that, the function finds the unmatched sequences ‘g i r l’ and ‘b o y’ and, within row 1, it also finds the matched sequences ‘t h a t’ and ‘r u n s’. With respect to row 1, the focus of interest is the matched and unmatched sequences of C-symbols—ID-symbols are ignored.

A copy of each of the four sequences is made, ID-symbols are added to each copy and the copy is added to Old. In addition, another ‘abstract’ pattern is made that records the sequence of matched and unmatched patterns within the alignment. The result in this case is five patterns like those shown in Figure 4.

It should be clear that the set of patterns in Figure 4 is, in effect, a simple grammar for the two sentences in Figure 3, with patterns representing grammatical rules in much the same style as those shown in Figure 1. The abstract pattern ‘$`<`$ %10 220 $`<`$ %7 $`>`$ $`<`$ %9 $`>`$ $`<`$ %8 $`>`$ $`>`$’ describes the overall structure of this kind of sentence with slots that may receive individual words at appropriate points in the pattern.

Notice how the symbol ‘%9’ serves to mark ‘b o y’ and ‘g i r l’ as alternatives in the middle of the sentence. This is a grammatical class in the tradition of distributional or structural linguistics (see, for example, ).

### 3.4 Sifting and Sorting of Patterns

In the example just shown, all the patterns derived from the alignment are ‘correct’. But in many cases, patterns that are derived in this way and added to Old are ‘wrong’. The wrong patterns are weeded out in the sifting\_and\_sorting() stage of processing (operation 4 in Figure 2), where the system develops one or more alternative grammars for the patterns in New in accordance with MLE principles. Figure 5 shows the overall structure of the sifting\_and\_sorting() function.

#### 3.4.1 Compiling a Set of Alternative Grammars

A set of alternative grammars for the patterns in New that are good in terms of MLE principles are derived (in the compile\_alternative\_grammars() function) in operation 4 of Figure 5. Each grammar is a subset of the patterns that have been added to Old during operation 3 of Figure 2.

The process of compiling good grammars is essentially a hill-climbing search through the abstract space of alternative grammars, trying to minimise $`(G+E)`$ for each grammar, where $`G`$ is the size of the given grammar (in bits) and $`E`$ is the size of all the New patterns (in bits) after they have been encoded in terms of the grammar. Minimising $`(G+E)`$ is, of course, the central idea in grammar induction using MLE principles. In what follows, $`(G+E)`$ is abbreviated as $`T`$.

The grammars are built in stages, at first trying to minimise $`T`$ for the first New pattern alone, then trying to minimise $`T`$ for the first and second New pattern, followed by the first, second and third, and so on.

## 4 Computational Complexity

In a serial processing environment, the time complexity of SP70 is approximately O$`(N^2)`$ where $`N`$ is the number of patterns in New. In a parallel processing environment, the time complexity may approach O$`(N)`$, depending on how well the parallel processing is applied. In serial or parallel environments, the space complexity should be O$`(N)`$.

The time complexity of the program may be improved when it has been developed, as envisaged, so that the New patterns are processed in batches, with a purging of Old between each batch to remove all patterns except those in the best grammar. In this case, the time complexity should be O$`(N)`$.

## 5 Example

When New contains the eight sentences shown in Figure 6, the best grammar found by SP70 is the one shown in Figure 7.

### 5.1 Intermediate Results

As the first phase of learning proceeds (operation 3 of Figure 2), intermediate results are often much less tidy than the example shown in Section 3.3. For example, when Old contains only the first pattern shown in Figure 6, the only alignment it can create is:

0 t h a t b o y r u n s 0  | 1 \< %1 9 t h a t b o y r u n s \> 1

Notice that the Old pattern (in row 1) is, in effect, the same pattern as the New pattern (in row 0) so it is not permissible to match ‘o’ in the New pattern, for example, with ‘o’ in the Old pattern because that would mean matching a given symbol with itself!

From the alignment just shown, the program derives ‘bad’ patterns like ‘$`<`$ %3 14 t h a $`>`$’, ‘$`<`$ %4 18 b o y r u n s $`>`$’ and ‘$`<`$ %4 17 h a t b o y r u n s $`>`$’ and these are added to Old. However, as later patterns are processed, the repository of Old patterns begins to accumulate enough patterns that are good in MLE terms so that it is able to create quite respectable looking parsings like this:

0 t h a t g i r l w a l k s 0  | | | | | | | | | | | | | 1 | | | | | | | | \< %8 %36 926 w a l k s \> 1  | | | | | | | | | | | 2 \< %10 220 \< %7 | | | | \> \< %9 | | | | \> \< %8 \> \> 2  | | | | | | | | | | | | | | 3 | | | | | | | \< %9 %18 215 g i r l \> 3  | | | | | | | 4 \< %7 208 t h a t \> 4

In the sifting\_and\_sorting() phase, all the ‘bad’ patterns are discarded and the ‘good’ patterns are cleaned up by removing unnecessary ID-symbols and renaming the retained ID-symbols in a tidy manner.

### 5.2 Values for $`G`$, $`E`$, $`T`$ and Compression

Figure 1 shows changing values for $`G`$, $`E`$ and $`T`$ for the best grammar found (in terms of MLE principles) as successive patterns from New are processed in compile\_alternative\_grammars(). It is interesting to see that, as successive patterns are processed, progressively more compression is achieved, represented by the falling values for ($`T`$ / ‘original’), shown in the last column.

## 6 Discussion

### 6.1 Evaluation

In accordance with the ‘looks-good-to-me’ approach to the evaluation of grammar induction systems , the grammar shown in Figure 7 looks like an appropriate grammar for the patterns shown in Figure 6.222A possible improvement might be a grammar that isolates the ‘s’ in ‘r u n s’ and ‘w a l k s’ as a separate morpheme. This may seem like a sloppy method of evaluation but it should not be forgotten that the human brain is, by a wide margin, the best learning system on the planet. This provides a justification for using human judgement of what does or does not ‘look good’ as a means of evaluating the output of artificial learning systems. With any system that is sufficiently robust to be applied to realistic samples of natural language, then there is no alternative to (human) judgements about what is or is not a ‘correct’ grammar for a given language or (human) conventions about how language is segmented into words. Statistical tests may be applied to establish whether or not there is a significant level of agreement between structures established by human judgement and the results of artificial learning .

Notice that the use of a ‘target’ grammar as a criterion of success (as in Gold’s approach to learning ) does not overcome the problem that, for any given language sample, there are many alternative grammars that are compatible with the sample and some are ‘better’ than others.

### 6.2 Reorganisation Needed

The example in the previous section is good enough to show that the approach is sound but experiments with other examples have shown that the model suffers from two main weaknesses:

* Although the model in its current form can isolate basic segments and tie them together in an overall abstract structure, it is not good at finding intermediate levels of abstraction.
* In the development of the model to date, no attempt has been made to enable the system to detect discontinuous dependencies such as number dependency between the subject of a sentence and its main verb (as mentioned in Section 2.1). Although this kind of capability may seem like a refinement that we can afford to do without at this stage of development, a deficiency in this area seems to have an impact on the program’s performance at an elementary level.

A possible solution to both problems is a reorganisation of the model so that learning is integrated even more closely with parsing. Recent work has shown that operation 2.2 in the sifting\_and\_sorting() function (Figure 5) can be omitted—the multiple alignments from operation 3.2 in Figure 2 can be used instead. It is also envisaged that New patterns will be processed in batches and that, after each batch, sifting\_and\_sorting() will be applied and Old patterns that are not proving useful will be discarded.

## 7 Conclusion

SP70 is not yet an ‘industrial strength’ system for unsupervised learning but I believe the framework has considerable potential and provides a sound basis for further development.

A key attraction of this approach to learning is that the ICMAUS framework provides a unified view of a variety of issues in AI thus facilitating the integration of grammar induction with other aspects of intelligence. Given the generality of the framework, the learning techniques described here are relevant to the learning of any kind of knowledge, not just grammars.

## Acknowledgements

I am grateful to Pat Langley and Menno van Zaanen for constructive comments on the report on which this paper is based. The paper has also benefitted from comments and suggestions by an anonymous referee.