text:
# Impurity-induced dephasing of Andreev states

## I Introduction

How much can flicker noise in the junction transparency affect coherent transport in Andreev states present in a superconducting quantum point contact (SQPC)? The assumption of coherent transport in Andreev states is widely used in theoretical work, see e. g. Refs.  and . However, in realistic systems interaction with a dynamical environment will always introduce some amount of dephasing, see Refs.  and  for a review.

In the so-called microwave-activated quantum interferometer  full coherency of Andreev states is assumed and a method for Andreev-level spectroscopy is presented. The Andreev levels are probed with a microwave field, resulting in an interference pattern in the current. If dephasing is present this interference pattern will begin to deteriorate. This connection between dephasing and current makes the microwave-activated quantum interferometer a suitable system to study the effect of flicker noise in the junction transparency on transport through Andreev states. It also provides an excellent opportunity to probe the coupling between a SQPC and its electromagnetic environment.

In the following we study the role of dephasing induced by flicker noise in the normal state junction transparency, $`D`$, of a SQPC in the transport through Andreev states. The concrete system which will be considered is the above presented interferometer.  Flicker noise can be caused by the presence of an impurity atom close to the junction which has two states of almost equal energy to choose from. When the atom tunnels between its two states the junction transparency will fluctuate. Another source of flicker noise is the tunneling of an electron between impurity atoms in a doped region. If there are two such neighboring defects with available states, a hybrid two-level state is formed and the electron can hop between the two. This hopping will then add a fluctuation to the junction transparency. The amplitude of these fluctuations depend on the distance between the defects and the junction. From now on we will refer to these dynamic defects as two-level elementary fluctuators (EFs).

The microwave-activated quantum interferometer (MAQI) is based on a short, weakly biased SQPC which is subject to microwave irradiation. Confined to the contact area there are current carrying Andreev states. The corresponding energy levels – Andreev levels – are found in pairs within the superconductor energy gap $`\mathrm{\Delta }`$, one below and one above the Fermi level. When a SQPC is short ($`L\xi _0`$ where $`L`$ is the length of the junction while $`\xi _0`$ is the superconductor coherence length), there is only one pair of Andreev levels and their positions depend on the order parameter phase difference, $`\varphi `$, across the contact as

$$E_\pm =\pm E(\varphi )=\pm \mathrm{\Delta }\sqrt{1D\mathrm{sin}^2(\varphi /2)}.$$
(1)
Within this pair, the two states carry current in opposite directions and in equilibrium only the lower state is populated. The applied bias, $`V`$, through the Josephson relation $`\dot{\varphi }=2eV/\mathrm{}`$, forces the Andreev levels to move adiabatically within the energy gap with a period of $`T_p=\mathrm{}\pi /eV`$, see Fig. 1.

The microwave field induces Landau-Zener (LZ) transitions between the Andreev levels (symbolized by wavy lines in Fig. 1). If the upper level is populated after the second transition a delocalized quasiparticle excitation will be created when this Andreev level merges with the continuum. The result will be a dc contribution to the current. Further, this current exhibits an interference pattern since there are two paths available to the upper level. It is this “interference effect” which is utilized in the MAQI for Andreev-level spectroscopy.

In order to estimate the influence of flicker noise on the interference pattern we continue with a quantitative presentation of the interferometer and the model used for the fluctuations.

## II Model and method

Consider a short single-mode SQPC which is subject to a high frequency microwave field ($`\mathrm{}\omega =2E(\varphi )2\mathrm{\Delta }`$). Let the contact, placed at $`x=0`$, be characterized by an energy-independent transparency $`D`$. A weak bias, $`eV\mathrm{\Delta }`$, is applied across the junction. We choose to describe the quasiparticles in the contact region with the following wave function,

$$\mathrm{\Psi }(x,t)=u_+(x,t)e^{ik_Fx}+u_{}(x,t)e^{ik_Fx},$$
(2)
where the envelope functions $`u_\pm (x,t)`$, left and right movers, are two-component vectors in electron-hole space. To simplify notation we introduce the four-component vector $`𝐮=[u_+,u_{}]`$. This vector satisfies the time-dependent Bogoliubov-de Gennes equation

$`i\mathrm{}𝐮/t`$ $`=`$ $`[_0+\sigma _zV_g(t)]𝐮,`$ (3)
$`_0`$ $`=`$ $`i\mathrm{}v_F\sigma _z\tau _z/x+\mathrm{\Delta }[\sigma _x\mathrm{cos}(\varphi (t)/2)`$ (5)
$`+\text{sgn}(x)\sigma _y\mathrm{sin}(\varphi (t)/2)],`$
where $`\sigma _i`$ and $`\tau _i`$ denote Pauli matrices in electron-hole space and in $`\pm `$ space, respectively, while $`V_g(t)=V_\omega \mathrm{cos}(\omega t)`$ is the time-dependent gate potential. We assume $`eV_\omega \mathrm{\Delta }`$.

The boundary condition at $`x=0`$ is

$$𝐮(+0)=D^{1/2}\left[1\tau _y(1D)^{1/2}\right]𝐮(0).$$

As a result of the applied high frequency field there will be resonant transitions between the Andreev levels. These transitions introduce a mixed state which can be described within the resonance approximation as

$$𝐮(x,t)=\underset{\pm }{}b^\pm (t)𝐮^\pm (x)e^{\omega t/2},$$

where $`𝐮^+(x)`$ and $`𝐮^{}(x)`$ are the envelope functions of the upper and lower Andreev states, while $`b^+`$ and $`b^{}`$ are the corresponding probability amplitudes. The final result is a dc current through the SQPC,

$`I_{\mathrm{dc}}`$ $`=`$ $`{\displaystyle \frac{e(2\mathrm{\Delta }\mathrm{}\omega )}{\mathrm{}\pi }}\left|b^+\left({\displaystyle \frac{\mathrm{}\pi }{eV}}\right)\right|^2=2I_0\mathrm{sin}^2(\mathrm{\Theta }+\mathrm{\Phi }),`$ (6)
$`I_0`$ $``$ $`(2e/\mathrm{}\pi )r^2(1r^2)\left(2\mathrm{\Delta }\mathrm{}\omega \right),`$ (7)
where $`r^2`$ is the LZ transition amplitude, which depends on the bias voltage and the amplitude of the perturbation ($`\mathrm{\Theta }`$ is the phase of the LZ transition, which can be considered constant). The phase $`\mathrm{\Phi }`$ which inhibits the interference is calculated through

$$\mathrm{\Phi }=\frac{1}{2eV}_{\varphi _A}^{\varphi _B}\left(E(\varphi )\frac{\mathrm{}\omega }{2}\right)d\varphi .$$
(8)
Flicker noise of the junction transparency, $`D`$, which is the subject to be discussed now, enters through $`E(\varphi )`$, Eq. (1), in this expression.

### A Flicker noise in the junction transparency

The main topic of this work is to study the effect of fluctuations in the junction transparency on the MAQI. For simplicity we choose to model the sources of these fluctuations, the EFs, with the so-called *random telegraph process*. This process is characterized by a random quantity $`\xi (t)`$ which has the value $`+1`$ or $`1`$ depending on whether the upper or lower EF state is occupied. We assume that the probability of each state is the same, namely $`1/2`$. This is acceptable since EFs with inter-level distances, $`E_i`$, smaller than $`k_\text{B}T`$, will be “frozen” — they behave as static impurities which do not affect the dynamic fluctuations of $`D`$. In this model the EF switches between its two states randomly in time. Physically, switching is a result of interactions between the EF and phonons or electrons in the contact area.

In the presence of EFs the junction transparency will be modulated. In other words, $`DD+D_f(t)`$, where $`D_f(t)`$ is assumed to be small. Generally

$$D_f(t)=\underset{i}{}A_i\xi _i(t),$$

with $`A_i`$ being the coupling strength of the $`i`$-th EF. We assume that the random processes in different EFs are not correlated. Consequently, after a change in variables from $`t`$ to $`\varphi `$ we can specify the random telegraph processes $`\xi _i(t)`$ through the correlation function,

$$\xi _i(\varphi _1)\xi _j(\varphi _2)=\delta _{ij}e^{2\gamma _i|\varphi _2\varphi _1|},$$
(9)
where $`\gamma _i`$ is the switching rate of $`i`$-th EF in units of the Josephson frequency $`\omega _J=2eV/\mathrm{}`$. It is related to the dimensional switching rate $`\mathrm{\Gamma }`$ as $`\gamma \mathrm{}\mathrm{\Gamma }/2eV`$.

Depending on the construction of the SQPC there can be any number of EFs which are “in range” to influence the transparency. In junctions which are very small it is probable that only one single EF will be in the vicinity of the contact. In this case, the coupling constant $`A`$ and the switching rate $`\mathrm{\Gamma }`$ can be directly evaluated from the measured telegraph noise intensity in the normal state,

$$S(\tau )I(t+\tau )I(t)_tI(t)_t^2.$$

Indeed, the current through a single mode QPC at low temperatures can be expressed according to the Landauer formula as $`I(t)=2e^2VD(t)/h`$. Consequently, the random telegraph noise intensity is equal to

$$S(\tau )=(2e^2VA/h)^2\mathrm{exp}(2\mathrm{\Gamma }\tau ),$$
(10)
and both $`A`$ and $`\mathrm{\Gamma }`$ can be extracted from measured $`S(\tau )`$. A possible approach for extracting these model parameters from noise measurements in the case of many fluctutators in the QPC area will be discussed later.

## III Single EF

In the case of a very small contact it is possible to consider only one EF and put $`i=1`$. We start by decomposing Eq. (1) as

$`E(\varphi )=E_+(\varphi )+E_{}(\varphi )\xi (\varphi ),`$ (11)
$`E_\pm {\displaystyle \frac{1}{2}}\left[E(\varphi |D_1)\pm E(\varphi |D_1)\right],`$ (12)
where $`D_{\pm 1}`$ are the two different values the transparency fluctuates between. Further, we assume that both $`\gamma `$ and $`g_{fs}E_{}/eV`$ are much smaller than the reduced inter-level distance $`(E_+\mathrm{\Delta })/eV`$. This means that all deviations in time are much longer than the Andreev level formation time, which is of the order $`\mathrm{}/2\mathrm{\Delta }`$.

Fortunately, the expression above, Eq. (12), is linear in $`\xi `$ and we can write the effect of the EF as an additive contribution to the accumulated phase, Eq. (8), without making any approximations. Namely, $`\mathrm{\Phi }\mathrm{\Phi }+\mathrm{\Phi }_f`$, with

$$\mathrm{\Phi }_f=\frac{1}{2}_{\varphi _A}^{\varphi _B}g_{fs}(\varphi )\xi (\varphi )d\varphi .$$
(13)
with $`g_{fs}(\varphi )=E_{}(\varphi )/eV`$. After averaging over the realizations of the random process $`\xi (t)`$, the expression (7) for the MAQI current is replaced by

$$I_{\mathrm{dc}}=I_0[1W\mathrm{cos}(2\mathrm{\Theta }+2\mathrm{\Phi })],$$
(14)
where $`We^{2i\mathrm{\Phi }_f}`$ contains the dephasing. Without dephasing $`W=1`$ and the effect of the phase $`\mathrm{\Phi }(\varphi _A,\varphi _B)`$ is a modulation of the dc current between 0 and $`2I_0`$, the modulation depth

$$(I_{\mathrm{max}}I_{\mathrm{min}})/(I_{\mathrm{max}}+I_{\mathrm{min}})=|W|.$$
(15)
being equal to one. This modulation of the current is the interference effect utilized in the MAQI. When dephasing enters, the quantity $`W(\varphi _A,\varphi _B)`$ will decrease and the modulation $`|W|`$ of the current envelope, i. e. the interference pattern, will in turn decrease.

To facilitate the calculation of the dephasing term, $`W`$, we define the auxiliary function,

$$\mathrm{\Psi }(\varphi )=\mathrm{exp}\left[i_{\varphi _A}^\varphi d\varphi ^{}g_{fs}(\varphi ^{})\xi (\varphi ^{})\right].$$
(16)
The quantity of interest, $`W`$, is related to $`\mathrm{\Psi }(\varphi )`$ as $`W\mathrm{\Psi }(\varphi _B)`$. Further, it can be shown, cf. with Ref. , that Eq. (16) satisfies the differential equation

$$\frac{\mathrm{d}^2\mathrm{\Psi }}{\mathrm{d}\varphi ^2}+\left[2\gamma \frac{\mathrm{d}\mathrm{ln}g_{fs}(\varphi )}{\mathrm{d}\varphi }\right]\frac{\mathrm{d}\mathrm{\Psi }}{\mathrm{d}\varphi }+g_{fs}^2(\varphi )\mathrm{\Psi }=0,$$
(17)
with the initial conditions

$$\mathrm{\Psi }(\varphi _A)=1,\mathrm{d}\mathrm{\Psi }/\mathrm{d}\varphi |_{\varphi =\varphi _A}=0.$$
(18)
Let us consider the following two cases in more detail: (i) the “slow EF”, $`\gamma g_{fs}`$, which corresponds to low temperatures, and (ii) the “fast EF”, $`\gamma g_{fs}`$, which corresponds to relatively high temperatures.

### A Slow switching EF

In the low-temperature limit the EF will slowly switch between its two states, and we can let $`\gamma 0`$ in Eq. (17). Further, by introducing the function,

$$\mathrm{\Xi }(\varphi )=_{\varphi _A}^\varphi d\varphi g_{fs}(\varphi )\mathrm{\Psi }(\varphi ),$$
(19)
and applying the initial conditions (18) we obtain the integral equation,

$$\mathrm{\Xi }^2+\mathrm{\Psi }^2=1.$$

The solution follows as $`\mathrm{\Psi }^{(0)}(\varphi )=\mathrm{cos}\mathrm{\Phi }(\varphi )`$ where $`\mathrm{\Phi }(\varphi )\left(_{\varphi _A}^\varphi d\varphi ^{}g_{fs}(\varphi ^{})\right)`$. Consequently, $`W^{(0)}=\mathrm{cos}\mathrm{\Phi }_\zeta `$ with

$$\mathrm{\Phi }_\zeta \mathrm{\Phi }(\varphi _B)=_{\varphi _A}^{\varphi _B}d\varphi g_{fs}(\varphi ).$$
(20)
A better approximation can be found by looking for the solution in the form $`\mathrm{\Psi }^{(1)}(\varphi )=u(\varphi )\mathrm{\Psi }^{(0)}(\varphi )`$ and assuming $`u(\varphi )`$ to be a slow function. Neglecting the second derivative of $`u(\varphi )`$ we obtain the differential equation

$$\mathrm{d}u/\mathrm{d}\varphi =\gamma \eta (\varphi )u$$
(21)
for $`u(\varphi )`$ with

$$\eta (\varphi )\left(1+\frac{1}{2g_{fs}^2\mathrm{tan}\mathrm{\Phi }(\varphi )}\frac{\mathrm{d}g_{fs}}{\mathrm{d}\varphi }\right)^1.$$
(22)
Defining

$$\upsilon _\zeta \frac{1}{2\zeta }_{\varphi _A}^{\varphi _B}\eta (\varphi )d\varphi $$
(23)
we arrive at the following expression for the oscillating part of the current,

$`W\mathrm{cos}(\mathrm{\Phi })=e^{2\gamma \upsilon _\zeta \zeta }\mathrm{cos}(\mathrm{\Phi }_\zeta )\mathrm{cos}(\mathrm{\Phi })`$ (24)
$`=e^{2\gamma \upsilon _\zeta \zeta }\left[\mathrm{cos}(\mathrm{\Phi }+\mathrm{\Phi }_\zeta )+\mathrm{cos}(\mathrm{\Phi }\mathrm{\Phi }_\zeta )\right]/2.`$ (25)
For a constant $`g_{fs}`$, $`\upsilon _\zeta =1`$ and $`\mathrm{\Phi }_\zeta =2g_{fs}\zeta `$, where $`\zeta =(\varphi _B\varphi _A)/2`$ is equal to half the distance between the resonance positions, see Fig. 1. In the general case these quantities are increasing functions of $`\zeta `$.

At $`\gamma =0`$, the current is split into two interference patterns of equal magnitude shifted by the phase $`\mathrm{\Phi }_\zeta `$. A plot of $`\mathrm{\Phi }_\zeta `$ as a function of $`\zeta `$ is presented in Fig. 2. The transparency $`D`$ and the strength of the fluctuator are shown in the inset. There is no dephasing, only a distortion of the interference pattern, the modulation being $`|W|=|\mathrm{cos}\mathrm{\Phi }_\zeta |`$.

This splitting into two patterns of equal magnitude follows from the assumption that the occupation probability is the same for the two EF states. The general case of arbitrary probabilities for the EF states can be solved numerically. At finite $`\gamma `$ dephasing takes place and the amplitude of the interference oscillations decreases by $`e^{2\gamma \upsilon _\zeta \zeta }`$. The physical reason of dephasing is the finite life time of an EF in a given state. We have calculated $`W`$ for $`\gamma =0.1`$, comparing the analytical approximation above against a numerical solution of Eq. (17), cf. with Fig. 3. (The plot for the analytical case when $`D=0.6,A=0.05`$ is missing because of numerical difficulties).

### B Fast switching EF

In the case of fast switching the differential equation (17) can be approximated as,

$$\frac{\mathrm{d}\mathrm{\Psi }}{\mathrm{d}\varphi }=\frac{g_{fs}^2(\varphi )}{2\gamma }\mathrm{\Psi }(\varphi ).$$
(26)
The solution in this case is easily obtained, as

$$W=\mathrm{\Psi }(\varphi _B)=\mathrm{exp}[K(\varphi _B,\varphi _A)],$$
(27)
with

$$K(\varphi _B,\varphi _A)=\frac{1}{2\gamma }_{\varphi _A}^{\varphi _B}d\varphi g_{fs}^2(\varphi ).$$
(28)
Here we find an exponential decay of the interference term. Expression (28) describes an effect which is similar to motional narrowing of spectral lines. When the EF fluctuates rapidly enough comparied to the “energy resolution” $`E_{}/\mathrm{}`$, influence from the difference between two EF states is smeared and dephasing will be of a diffusive character, with en effective, time-dependent, diffusion constant $`g_{fs}^2/2\gamma `$. A calculation of the factor $`K`$ for $`\gamma =3`$ is shown in Fig. 4 for three different sets of values of the junction transparency and the EF’s strength. The effect of dephasing from flicker noise will decrease for higher bias voltages, since a higher bias, through the Josephson relation, leads to a shorter time between the resonances.

To get an idea about the general case of arbitrary switching rates, it is instructive to consider a $`\varphi `$-independent $`g_{fs}`$. This approximation is only valid when $`|\mathrm{d}E(\varphi )/\mathrm{d}\varphi |`$ is small, but should provide the general behavior of $`W`$. In this limit Eq. (17) can be solved analytically, resulting in

$`W=e^{2\gamma \zeta }[\mathrm{cosh}\left(2\zeta \sqrt{\gamma ^2g_{fs}^2}\right)+`$ (29)
$`{\displaystyle \frac{\gamma }{\sqrt{\gamma ^2g_{fs}^2}}}\mathrm{sinh}\left(2\zeta \sqrt{\gamma ^2g_{fs}^2}\right)].`$ (30)
From this expression one can conclude that there will always enter an exponential decay of the interference current, except for the limit of $`\gamma 0`$. In this limit there should only be an additional oscillation added to the current as a function of $`\zeta `$ since for $`\gamma |g_{fs}|`$, the hyperbolic functions behave as trigonometric functions.

## IV Many EF’s

Let us consider a large number of EFs with varying switching rates distributed in the contact area. For simplicity, we shall assume that only the fluctuators with inter-level spacings $`U_ikT`$ are important, and that their distribution is uniform, $`𝒫_U(U)=P_0𝒱`$. Here $`𝒱`$ is the sample volume. Further, we assume that the switching rates $`\gamma _i`$ are the same for both transition directions (up och down) between the EF’s levels. This assumption is natural because the ratio between the corresponding transition rates is $`\mathrm{exp}(U_i/kT)`$. Within the assumptions discussed above, the final results are substantially simplified while preserving the essential depedence on temperature and the resonance position. These approximations agree with a general theory developed in Ref.  for the case of dephasing by two-level systems (TLS) in glasses.

The first step now is to linearize the SQPC’s transparency with respect to $`\xi _i`$ as $`DD+D_f(t)`$. This allows us to once again find an additive contribution to the accumulated phase, Eq. (8), which in this case will be,

$$\mathrm{\Phi }_f\underset{i}{}A_i_{\varphi _A}^{\varphi _B}\xi _i(\varphi )g_{fm}(\varphi )d\varphi .$$
(31)
Here we have defined $`g_{fm}(\varphi )=(1/2eV)\mathrm{d}E(\varphi )/\mathrm{d}D`$. In the same manner as in Sect. III, but this time averaging over $`A`$’s, $`\gamma `$’s and $`\xi ^{}s`$, we can express the modified MAQI current through expression (14) with

$$W=e^{i_iA_i_{\varphi _A}^{\varphi _B}g_{fm}(\varphi )\xi _i(\varphi )d\varphi }_{A,\gamma ,\xi }.$$
(32)
To approximate this average we use the Holtsmark method  which is valid in the limit of many fluctuators, $`N=P_0𝒱kT1`$. This allows us to rewrite Eq. (32) as the average over the contributions from single EFs,

$$W_s(A,\gamma )=\mathrm{exp}\left(iA_{\varphi _A}^{\varphi _B}g_{fm}(\varphi )\xi (\varphi )d\varphi \right)_\xi $$
(33)
as

$$W\mathrm{exp}\left(P_0𝒱kT1W_s(A,\gamma )_{A,\gamma }\right).$$
(34)
Since the number of EFs is assumed to be large, to keep dephasing at a reasonable level it is important to keep $`1W_s`$ small.

With the solutions for $`W_s`$ found in Sect. III the average $`1W_s`$ remains to be calculated. To calculate this average one has to specify the distributions of the parameters $`A`$ and $`\gamma `$. The simplest and most natural assumption is that these two quantities are not correlated. Consequently, the distribution $`𝒫(A,\gamma )`$ can be decoupled as $`𝒫_A(A)𝒫_\gamma (\gamma )`$. To specify the distribution $`𝒫_A`$ let us assume that the EFs are uniformly distributed in space. An EF behaves like a dipole, either electric or elastic, this allows us to specify it‘s interaction strength as $`A(r)=A_0/r^3`$, where $`r`$ is the distance between the contact and a given EF,  while $`A_0`$ is a coupling constant dependent on a specific interaction mechanism. Note that the quantity $`A_0`$ has dimension of volume. Within this model we arrive at the normalized distribution function $`𝒫_A(A)=4\pi A_0/3𝒱A^2`$ (see Appendix B for details). The distribution $`𝒫_\gamma (\gamma )`$ is specified in a manner which is commonly used in glasses. Namely, the logarithm of $`\gamma `$ is assumed to be uniformly distributed. Hence, $`𝒫_\gamma (\gamma )\gamma ^1`$, see Appendix B. To normalize it let us take into account that for a given energy spacing $`U`$ there is a maximal switching rate. Since we are interested in the fluctuators with $`U_ikT`$, we can specify the maximal switching rate as $`\gamma _T`$, which is a function of the temperature. The actual temperature dependence is determined by the specific interaction mechanism between the EF and its environment. If the transitions between the EF states are caused by interaction with phonons, then $`\gamma _TT^3`$ while if the transitions are caused by the electrons excitations, then $`\gamma _TT`$ Therefore , the normalized distribution can be specified as $`𝒫_\gamma (\gamma )=(\gamma )^1`$, where $`=\mathrm{ln}(\gamma _T/\gamma _{\mathrm{min}})1`$. Here we have introduced the minimal switching rate, $`\gamma _{\mathrm{min}}`$. To express the decay in a more clear form let us introduce the dimensionless frequency $`\nu _d`$ corresponding to the interaction strength for an EF separated from the contact by an average distance to the active fluctuators, $`\overline{r}(4\pi P_0kT/3)^{1/3}`$, divided by the Josephson energy $`2eV`$. We can specify $`\nu _d`$ as

$$\nu _d=4\pi P_0kTA_0/3=A_0/\overline{r}^3.$$
(35)
The decay rate $`𝒦=\mathrm{ln}W`$ is then given by the expression

$$𝒦=\frac{\nu _d}{}_0^{\mathrm{}}\frac{\mathrm{d}A}{A^2}_{\gamma _{\mathrm{min}}}^{\gamma _T}\frac{\mathrm{d}\gamma }{\gamma }\left[1W_s(A,\gamma )\right].$$
(36)
Note that $`g_{fs}`$ has to be replaced with $`Ag_{fm}`$ in the expressions for $`W_s`$ in the many EF case, because of differences in notation.

To estimate the amount of dephasing let us take into account that the asymptotic expressions for $`W_s`$, found in (25) and (27) for slow and fast switching respectively, match at

$$\gamma \stackrel{~}{\upsilon }_\zeta (A\overline{g}_\zeta )^2\eta _\zeta /2\gamma ,$$
(37)
where $`\stackrel{~}{\upsilon }_\zeta `$ differs from $`\upsilon _\zeta `$ defined in Eq. (23) by the replacement $`g_{fs}Ag_{fm}`$ in the differential equation (21), while

$$\overline{g}_\zeta =\frac{1}{2\zeta }_{\varphi _A}^{\varphi _B}g_{fm}(\varphi ),\eta _\zeta \frac{1}{2\zeta \overline{g}_\zeta ^2}_{\varphi _A}^{\varphi _B}g_{fm}^2(\varphi )d\varphi .$$
(38)
Note that $`\stackrel{~}{\upsilon }_\zeta `$ is a function of $`A`$, $`\stackrel{~}{\upsilon }_\zeta (A)`$. Consequently, Eq. (37) should be treated as an *equation* to determine the characteristic value of the coupling $`A`$. Defining the solution of Eq. (37) as $`A_\zeta `$ and splitting the integration over $`A`$ in Eq. (36) as

$$_{\gamma _{\mathrm{min}}}^{\gamma _T}\frac{\mathrm{d}\gamma }{\gamma }\left(_0^{A_\zeta }+_{A_\zeta }^{\mathrm{}}\right)\frac{\mathrm{d}A}{A^2}\left[1W_s(A,\gamma )\right]$$
(39)
we can use the expression (27) in the first interval and the expression (25) in the second one. Since both integrals are determined by $`A_\zeta `$ we arrive at the estimate

$$\mathrm{ln}W3\nu _d\zeta f_\zeta ,$$
(40)
where $`f_\zeta \overline{g}_\zeta \sqrt{\eta _\zeta \stackrel{~}{\upsilon }_\zeta (A_\zeta )}`$ is some function of $`\zeta `$, rather smooth if $`D`$ is not close to 1. We see that the interference pattern decays exponentially with an increasing distance, $`2\zeta `$, between the resonances. Generally the $`\zeta `$-dependence of $`f_\zeta `$ can be calculated numerically for a given transparency $`D`$ using the analytical expressions (23) and (37). For a constant $`g_{fm}`$, $`f_\zeta =g_{fm}`$. We do not analyze here the function $`f_\zeta `$ in detail.

### A Non-optimal EFs

In the previous sections it has been assumed that the system size is infinite. A consequence of this assumption is that, independent of temperature, the EFs which have the strongest effect on the junction transparency will always be included in the estimates. From the method used to obtain the general estimate for many EFs, Eq. (40), one can conclude that the EFs which have the most effective coupling fulfill $`AA_\zeta `$, this corresponds to a spatial distance $`r_\gamma =(A_0/A_\zeta )^{1/3}(A_0\overline{g}_\zeta /\gamma )^{1/3}`$. A further point is that the rate $`\gamma `$ is confined to the interval between $`\gamma _{\mathrm{min}}`$ and $`\gamma _T`$. Thus we have actually assumed that the size of the region where EFs reside has a size greater than $`r_{\mathrm{max}}(A_0\overline{g}_\zeta /\gamma _{\mathrm{min}})^{1/3}`$, and that there is no “excluded region” without EFs near the contact with the size less that $`r_{\mathrm{min}}(A_0\overline{g}_\zeta /\gamma _T)^{1/3}`$.

What happens if this “optimum” EF is out of the range? This can occur if the system is limited in size, or if there is a specifically pure region around the contact.

#### 1 Role of finite size of the sample

Let us first discuss the role of a finite size, $`R`$ , of the region containing EFs. If $`Rr_{min}=(A_0/A_\zeta )^{1/3}`$ then all EFs will act as “slow” ones. To estimate $`\mathrm{ln}W`$ in this case one can use the expression $`W_s=\mathrm{cos}\mathrm{\Phi }_\zeta `$ for the whole integration region over $`A`$ in Eq. (36), arriving at

$$\mathrm{ln}W=2\nu _d\overline{g}_\zeta \zeta F(2A_0\overline{g}_\zeta \zeta /R^3).$$
(41)
Here

$$F(z)=_z^{\mathrm{}}\frac{1\mathrm{cos}x}{x^2}dx,$$
(42)
which is a decreasing function of its argument. This expression (41) is valid if its right-hand side is less the right-hand side of Eq. (40).

At intermediate values of $`R`$,

$$(A_0\overline{g}_\zeta /\gamma _{min})^{1/3}R(A_0\overline{g}_\zeta /\gamma _T)^{1/3},$$

as in the previous case, only the second integral in the expression (39) does exist, lowest limit should also be replaced by $`A_0\overline{g}_\zeta /R^3`$. However, the approximation $`W_s=\mathrm{cos}\mathrm{\Phi }_\zeta `$ is not valid any more. Using the approximation (25) one can obtain

$$W=\mathrm{exp}\left[\nu _d\zeta f_\zeta \frac{\mathrm{ln}(\gamma _TR^3/A_0\overline{g}_\zeta )}{\mathrm{ln}(\gamma _T/\gamma _{\mathrm{min}})}\right].$$
(43)
This means that when the size of system is limited the amount of dephasing can be less than estimated for an infinite system.

#### 2 Role of the spacer

Let us now discuss the role of a “pure” region (spacer) near the SQPC where there are no EFs. If a typical diameter $`r_0`$ of such region is large enough, such that $`r_0r_{\mathrm{max}}=(A_0\overline{g}_\zeta /\gamma _{\mathrm{min}})^{1/3}`$, then all EFs act as “fast” ones.

The single EF solution, $`W_s`$, in this limit is given by Eq. (27) in Sect. III B. After calculating the average in Eq. (34) we arrive at

$$\mathrm{ln}W(\nu _d\overline{g}_\zeta /)\sqrt{4\pi \zeta \eta _\zeta /\gamma _{\mathrm{min}}}.$$
(44)
It is difficult to estimate the actual amount of dephasing. We have to restrict our conclusions to interpreting how the amount of dephasing will change depending on the parameters $`\gamma _T`$, $`\gamma _{\mathrm{min}}`$, $`\zeta `$ and $`T`$. We already know that dephasing will increase with temperature. Generally one can also say that dephasing will increase with $`\zeta `$. However, at large enough temperatures when $`\gamma _{\mathrm{min}}`$ appears large enough, the dephasing will decrease. The free parameter of the theory, $`A_0`$, can be estimated only roughly through comparison with the noise measurements in the normal state. To map the parameter $`A_0`$ to the noise let us employ the theory of flicker noise in a QPC to the case of a single mode contact. According to that theory, results for the noise intensity $`S(\tau )`$ are substantially dependent on the relationship between the maximal and minimal distances between the EFs and the QPC. The simplest case, which is quite realistic, is when these distances are of the same order of magnitude. When $`\mathrm{\Gamma }_T^1|\tau |\mathrm{\Gamma }_{\mathrm{min}}^1`$ the noise intensity can be expressed as, cf. with Ref. ,

$$S(\tau )\left(\frac{2e^2V}{h}\right)^2\left(\frac{4\pi P_0kTA_0}{3}\right)^2\frac{\mathrm{ln}(1/\mathrm{\Gamma }_{\mathrm{min}}|\tau |)}{\mathrm{ln}(\mathrm{\Gamma }_T/\mathrm{\Gamma }_{\mathrm{min}})}.$$
(45)
By obtaining estimates for $`\mathrm{\Gamma }_{T/\mathrm{min}}`$ from noise spectra in the normal state one can, in principle, estimate the coupling parameter $`A_0`$. A key point is to make measurements of both the MAQI interference pattern and the normal-state noise spectra in a rather large frequency range. This combination does not look too simple.

## V Conclusions

We have presented a method for investigating the influence of flicker noise in the junction transparency of a SQPC on coherent Andreev states. This is done by estimating the effect of these fluctuations on the so-called microwave-activated quantum interferometer (MAQI) .

For a small contact when only a single EF is in range to affect the junction transparency there can be either a distortion or a decay of the MAQI interference pattern. A distortion appears for very slow switching rates of the EF and a weak decay (dephasing) for fast rates. It is possible to confirm our model in the fast switching limit experimentally. The only unknown parameter is the switching rate $`\gamma `$ which can be found by measuring the telegraph noise of the contact in the normal state. This is best done by driving the system into the normal state with a magnetic field, since $`\gamma `$ is temperature dependent. When $`\gamma `$ is known it is then possible to calculate the amount of dephasing and compare with experimental results.

In the limit when the influence of many EFs has to be considered we have arrived at more general results. It is not possible to make any exact predictions since the distribution and coupling strength of the EFs are sample dependent. However, our calculations show that in the presence of many EFs there will always be an exponential decay of the MAQI interference pattern. The strength of this dephasing should be about the same for all switching rates. One exception is when there is an impurity-free region near the SQPC, in this case dephasing will decrease for higher rates.

Finally, we note that this paper together with work in Ref.  presents a framework which can be used to investigate the coupling of a SQPC to its electromagnetic environment.

## Acknowledgements

We are grateful to M. Jonson for fruitful discussions. Support from the SSF program “Quantum Devices and Nanostructures” and CAS, the Centre for Advanced Study in Oslo, Norway is acknowledged.

## A Derivation of equation for $`W`$

In this appendix the differential equation, Eq. 17, for $`W`$ is derived. The following is valid for the random telegraph process $`\xi (t)`$,

$$\xi (\varphi _1)\xi (\varphi _2)\mathrm{}\xi (\varphi _n)=e^{2\gamma |\varphi _2\varphi _1|}\xi (\varphi _3)\xi (\varphi _4)\mathrm{}\xi (\varphi _n),$$
(A1)
when $`\varphi _1\varphi _2\mathrm{}\varphi _n`$. Further, all averages with an odd number of $`\xi `$:s are equal to zero. This follows from the assumption of equal probability for both EF states.

To facilitate the calculation of $`W`$, the auxiliary function

$$\mathrm{\Psi }(\varphi )=\mathrm{exp}\left[i_{\varphi _A}^\varphi d\varphi ^{}g_{fs}(\varphi ^{})\xi (\varphi ^{})\right]$$
(A2)
is defined. By expanding the auxiliary function in a Taylor series and utilizing the relation in Eq. A1 above, it is possible to rewrite the auxiliary function as

$`\mathrm{\Psi }(\varphi )=`$ (A3)
$`1+i^2{\displaystyle _{\varphi _A}^\varphi }d\varphi _1{\displaystyle _{\varphi _A}^{\varphi _1}}d\varphi _2g_{fs}(\varphi _1)g_{fs}(\varphi _2)e^{2\gamma |\varphi _2\varphi _1|}\mathrm{\Psi }(\varphi _2).`$ (A4)
A derivation with respect to $`\varphi `$ leads to the following integro-differential equation

$$\frac{\mathrm{d}\mathrm{\Psi }}{\mathrm{d}\varphi }=g_{fs}(\varphi )_{\varphi _A}^\varphi d\varphi ^{}g_{fs}(\varphi ^{})e^{2\gamma |\varphi ^{}\varphi |}\mathrm{\Psi }(\varphi ^{}),$$
(A5)
and a second derivation provides the following differential equation

$$\frac{\mathrm{d}^2\mathrm{\Psi }}{\mathrm{d}\varphi ^2}+\left[2\gamma \frac{\mathrm{d}\mathrm{ln}g_{fs}(\varphi )}{\mathrm{d}\varphi }\right]\frac{\mathrm{d}\mathrm{\Psi }}{\mathrm{d}\varphi }+g_{fs}^2(\varphi )\mathrm{\Psi }=0,$$
(A6)
with the initial conditions

$$\mathrm{\Psi }(\varphi _A)=1,\mathrm{d}\mathrm{\Psi }/\mathrm{d}\varphi |_{\varphi =\varphi _A}=0.$$
(A7)
This equation makes it possible to find approximate analytical solutions for $`W`$ in the single EF case.

## B Distributions, $`𝒫_\gamma (\gamma )`$ and $`𝒫_A(A)`$

Here we outline the derivation for the distribution functions $`𝒫(\gamma )`$ and $`𝒫(A)`$ which are necessary when averaging in the many EF case. Let us begin with $`𝒫(A)`$, where $`A`$ is the coupling strength between an EF and the contact. By assuming that an EF can be modeled with a dipole field, we can state that $`AA_0/r^3`$ where $`r`$ is the distance from the EF. The normalized distribution is then found through the following integral, $`𝒫(A)=𝒱^1d𝐫\delta (AA_0/r^3)`$ as

$$P(A)=(4\pi /3𝒱)(A_0/A^2).$$
(B1)
To find the distribution of $`\gamma `$ a closer look at the structure of the two level system (TLS) which is assumed for the EFs is necessary. The Hamiltonian for a TLS can be $`H=\mathrm{\Delta }\sigma _z\mathrm{\Lambda }\sigma _x`$, where $`\mathrm{\Delta }`$ is the energy difference between the minima of the two states and $`\mathrm{\Lambda }`$ is the tunneling coupling between the two states. After diagonalization the excitation energy is found to be $`U=\sqrt{\mathrm{\Delta }^2+\mathrm{\Lambda }^2}`$. By assuming that the tunneling coupling decays exponentially we have that $`𝒫(\mathrm{\Lambda })1/\mathrm{\Lambda }`$. Further, the hopping rate $`\gamma `$ depends on $`(\mathrm{\Lambda }/U)^2`$ and a term $`U^3/\mathrm{}E_c^2`$ where the latter term comes from assuming that hopping is phonon mediated ($`E_c`$ is the parameter characterizing the coupling energy between the phonons and the EFs). Within these assumptions $`𝒫(\gamma )`$ is given by,

$`𝒫_\gamma (\gamma )`$ $`=`$ $`{\displaystyle d\mathrm{\Delta }d\mathrm{\Lambda }P(\mathrm{\Lambda })\delta (U^2\mathrm{\Delta }^2\mathrm{\Lambda }^2)}`$ (B3)
$`\times \delta (\gamma {\displaystyle \frac{\mathrm{\Lambda }^2}{U^2}}{\displaystyle \frac{U^3}{\mathrm{}E_c^2}}){\displaystyle \frac{1}{\gamma }}.`$
After normalization we have,

$$P(\gamma )=\frac{1}{\gamma },$$
(B4)
where $`=\mathrm{ln}(\gamma _T/\gamma _{\mathrm{min}})`$ with $`\gamma _{T,\mathrm{min}}`$ being limiting values for the EF switching rate $`\gamma `$.

In the general case $`𝒫=𝒫(U,\gamma ,A)`$ and the number of EFs will be given by $`N=dUd\gamma dA𝒫(U,\gamma ,A)`$. By assuming a constant distribution for $`U`$, which we label $`𝒫_0`$, we arrive at the number of EFs as $`N=P_0𝒱kT`$.

The final distribution function for $`A`$ and $`\gamma `$ is then

$$𝒫(A,\gamma )=\frac{4\pi P_0kT}{3}\frac{A_0}{A^2}\frac{1}{\gamma }.$$
(B5)


format: text

text:
# Consistency Management of Normal Logic Program by Top-down Abductive Proof Procedure

## Introduction

Knowledge base is always subject to change since an environment around the knowledge base is not guaranteed to be stable forever and even some error might be included at the initial stage. Therefore, study of revision of knowledge base is very important(???????). (?) and (?) consider a revision of monotonic theories and there are a lot of researches in this direction (see (?) for a survey). (?) and (?) consider an update of nonmonotonic theories to derive a given goal or a given observation. (?) and (?) consider a revision of nonmonotonic theories which is more related to a revision of monotonic theories studies (??); they consider a revision when inconsistency arises at addition of rules 111(?) relate the latter approach with the former approach by introducing “anti-explanation of contradiction.” In this paper, we follow the latter approach.

Revision of nonmonotonic theories is especially important for AI, since it is very rare that commonsense reasoning can be represented as a monotonic theory. However, revision of nonmonotonic theories is more complicated than revision of monotonic theory. In monotonic theory, if some addition of knowledge or observation leads to inconsistency, then we can avoid inconsistency by deleting a part of knowledge base. On the other hand, we might add a piece of assumptions since deletion leads to inconsistency.

Consider the following program.

$`runs(X)car(X),broken(X).`$

$`car(c_1).`$

$`car(c_2).`$

$``$ means “negation as failure”. The first rule says that if $`X`$ is a car and $`X`$ is not known to be broken, $`X`$ should run. Since there is no information about $`broken(c_1)`$ and $`broken(c_2)`$ in the current program, $`runs(c_1)`$ and $`runs(c_2)`$ are derived. Suppose, however, that we add a rule “$`runs(c_1)`$” meaning that car $`a`$ does not run 222$``$ means contradiction.. Then, we have no stable model, that is, we are in an inconsistent situation. To fix this inconsistency, we have (at least) two possible ways.

1. We simply discard the default rule of car $`a`$:

$$runs(c_1)car(c_1),broken(c_1).$$
2. We derive $`broken(c_1)`$ since if we assumed $`broken(c_1)`$, then contradiction would occur and thus, we have a reason to assume $`broken(c_1)`$.

The first revision is contraction widely used in belief revision of monotonic theories (?) but the second is special for nonmonotonic theories such as normal logic programs. In monotonic theories, addition of formula can not help to restore consistency, but in nonmonotonic theories addition can help. This phenomena were firstly observed in Doyle’s justification TMS and he introduced dependency-directed backtracking. Moreover, in monotonic theories, contraction or deletion of formula can not produce any inconsistency, whereas in nonmonotonic theories, deletion can cause inconsistency.

Therefore, we need more functions for revision in nonmonotonic theories than monotonic ones. In this paper, we propose a top-down procedure using abduction to compute revision for a normal logic program when there exists no stable model.

Our idea of using abduction for revision is as follows. We introduce two kinds of abducibles one of which represents a deletion of each retractable rule and the other of which represents an addition of each addable rule. For a retractable rule, we add negation of a corresponding abducible in the body of the rule so that if an instance of abducible is assumed then an instance of rule corresponding with the instance of abducible is no longer applicable. For an addable rule, we add a corresponding abducible in the body of the rule so that if an instance of abducible is assumed then an instance of rule corresponding with the instance of abducible becomes applicable.

Then, in order to compute such abducibles to specify revision, we show that we can use a modification of Satoh and Iwayama’s query evaluation procedure on stable models (?) which is a combination of integrity constraint checking (?) and abductive procedure (?). In stead of starting with a subprocedure which show a derivation of positive literals, we start with a subprocedure for rule consistency checking to derive abducibles to specify revision. This procedure traverses rules of a program which is related with addition or deletion of a rule and we guarantee that a minimal revision can be found by selecting a minimal set of abducibles among all the sets of abducibles computed by the rule consistency checking procedure.

## Revision of Normal Logic Program

Firstly, we define a revision framework as follows. In this paper, we consider a function-free normal logic program. We use domain closure axiom and unique name axiom so that constants in the language for a program are finite and denote distinct objects. We can easily extend our results to function-free extended logic programs by translating an extended logic program into a normal logic program proposed by (?).

###### Definition 1

A rule $`R`$ is of the form:

$$HP_1,\mathrm{},P_j,N_1,\mathrm{},N_h$$

where $`H`$, $`P_1,\mathrm{},P_j,N_1,\mathrm{},N_h`$ are atoms.

We call $`H`$ the head of the rule $`R`$ denoted as $`head(R)`$ and $`P_1,\mathrm{},P_j,N_1,\mathrm{},N_h`$ the body of the rule denoted as $`body(R)`$. If $`H=`$, we sometimes call the rule an integrity constraint.

Let $`T`$ and $`T_{bck}`$ be sets of rules. A revision framework $``$ is a pair, $`T,T_{bck}`$ where $`T`$ can be divided into two sets of rules $`T_{pst}`$ and $`T_{tmp}`$. We call $`T_{pst}`$ a persistent part of $``$ and $`T_{tmp}`$ a temporal part of $``$ and $`T_{bck}`$ a backup part of $``$.

$`T`$ expresses the current logic program which consists of $`T_{pst}`$ and $`T_{tmp}`$. $`T_{pst}`$ is an unchanged part which should always be satisfied such as integrity constraints whereas any part of $`T_{tmp}`$ can be retracted and any part of $`T_{bck}`$ can be added to restore consistency. Usage of $`T_{bck}`$ is inspired by back-up semantics proposed by (?).

We use stable model semantics for the above program.

###### Definition 2

Let $`P`$ be sets of rules. We denote a set of ground rules obtained by replacing all the variables in every rule of $`P`$ by every element in the language as $`\mathrm{\Pi }_P`$.

###### Definition 3

Let $`M`$ be a set of ground atoms and $`\mathrm{\Pi }_P^M`$ be the following program. $`\mathrm{\Pi }_P^M=`$ $`\{HB_1,\mathrm{},B_l|`$

$`\mathrm{`}\mathrm{`}HB_1,\mathrm{},B_l,A_1,\mathrm{},A_h.^{\prime \prime }\mathrm{\Pi }_P`$ and $`A_iM`$ for each $`i=1,\mathrm{},h.\}`$ Let $`min(\mathrm{\Pi }_P^M)`$ be the least model of $`\mathrm{\Pi }_P^M`$. A stable model for a logic program $`P`$ is $`M`$ iff $`M=min(\mathrm{\Pi }_P^M)`$ and $`M`$.

We say that $`P`$ is consistent if $`P`$ has a stable model.

Now, we define a revised program in a revision framework.

###### Definition 4

Let $``$ be a revision framework, $`(T_{pst}T_{tmp}),T_{bck}`$. Let $`R_{new}`$ be a rule. Then, a revised program w.r.t. $``$ and $`R_{new}`$ is $`(T_{pst}\{R_{new}\})(\mathrm{\Pi }_{T_{tmp}}O)I`$ such that

* $`O\mathrm{\Pi }_{T_{tmp}}`$
* $`I\mathrm{\Pi }_{T_{bck}}`$
* $`(T_{pst}\{R_{new}\})(\mathrm{\Pi }_{T_{tmp}}O)I`$ is consistent.

We say for such $`O`$ and $`I`$ that a pair $`O,I`$ accomplishes revision of $`R_{new}`$ to $``$.

A minimally revised program w.r.t. $``$ and $`R_{new}`$ is $`(T_{pst}\{R_{new}\})(\mathrm{\Pi }_{T_{tmp}}O)I`$ such that there is no revised program $`(T_{pst}\{R_{new}\})(\mathrm{\Pi }_{T_{tmp}}O^{})I^{}`$ such that $`I^{}I`$ and $`O^{}O`$ where $``$ is a strict inclusion.

###### Example 1

Let
$`T_{pst}`$ be $`\{c(c_1).c(c_2).\}`$ and
$`T_{tmp}`$ be $`\{r(X)c(X),b(X).\}`$ and
$`T_{bck}`$ be $`\{b(X)c(X),r(X).\}`$ and
$`R_{new}`$ be “$`r(c_1)`$”.
Then, $`\mathrm{\Pi }_{T_{tmp},(T_{pst}\{R_{new}\})T_{tmp}T_{bck}}=`$ $`\{r(c_1)c(c_1),b(c_1).r(c_2)c(c_2),b(c_2)\}`$,
and $`\mathrm{\Pi }_{T_{bck},(T_{pst}\{R_{new}\})T_{tmp}T_{bck}}=`$ $`\{b(c_1)c(c_1),r(c_1).b(c_2)c(c_2),r(c_2)\}`$.

For the above revision, we have the following two minimally revised programs:

1. a program accomplished by $`(O_1,I_1)`$ where $`O_1=\{r(c_1)c(c_1),b(c_1).\}`$ and $`I_1=\{\}`$:

$`(T_{pst}\{R_{new}\})`$ and $`r(c_2)c(c_2),b(c_2).`$
2. a program accomplished by $`(O_2,I_2)`$ where $`O_2=\{\}`$ and $`I_2=\{b(c_1)c(c_1),r(c_1).\}:`$

$`(T_{pst}\{R_{new}\})`$ and $`T_{tmp}`$ and $`b(c_1)c(c_1),r(c_1).`$

There are other non-minimally revised programs, for example, one accomplished by $`O_1,I_2`$ or by $`O_1\{r(c_2)c(c_2),b(c_2).\},I_2\{b(c_2)c(c_2),r(c_2).\}`$.

In the above example, we follow Giordano’s approach (?) where contrapositives of default rules are in the back-up part, but we can actually assume any rules which we think are appropriate for back-up rules when inconsistency occurs.

To compute a revised program, we use a translation from a specification to an abductive logic program and compute a consistent generalized stable model for the translated program which denotes deletion and addition of rules.

###### Definition 5

(?). An abductive framework is a pair $`P,A`$ where $`A`$ is a set of predicate symbols, called abducible predicates and $`P`$ is a set of rules each of whose head is not in $`A`$. We call a ground atom for a predicate in $`A`$ an abducible.

The semantics of abductive framework is based on a generalized stable model (?).

The following is a definition of a generalized stable model which can manipulate abducibles in abductive logic programming.

###### Definition 6

Let $`P,A`$ be an abductive framework and $`\mathrm{\Theta }`$ be a set of abducibles. A generalized stable model $`M(\mathrm{\Theta })`$ is a stable model of $`P\{H|H\mathrm{\Theta }\}`$.

We say that a model $`M(\mathrm{\Theta })`$ is a generalized stable model with a minimal set of abducibles $`\mathrm{\Theta }`$ if there is no generalized stable model $`M(\mathrm{\Theta }^{})`$ such that $`\mathrm{\Theta }^{}`$ is a proper subset of $`\mathrm{\Theta }`$.

Now, we define a translation of a revision framework into an abductive framework as follows.

###### Definition 7

Let $``$ be a revision framework $`(T_{pst}T_{tmp}),T_{bck}`$. We firstly give a name to every rule in $`T_{tmp}`$ and $`T_{bck}`$ such as

$$\varphi :HP_1,\mathrm{},P_j,N_1,\mathrm{},N_h.$$

where $`\varphi `$ is a name for the rule.

A translation for a consistency management of $``$ (denoted as $`\tau ()`$) is a set of the following translation from $``$ to an abductive framework $`P,A`$ where

* $`A=\{\varphi _{}^{}{}_{}{}^{}|\varphi `$ is a name of a rule in $`T_{tmp}\}`$ $`\{\varphi _{}^{+}{}_{}{}^{}|\varphi `$ is a name of a rule in $`T_{bck}\}`$
* We add every rule in $`T_{pst}`$ into $`P`$.
* We translate every rule in $`T_{tmp}`$ with a name $`\varphi `$

$$\varphi :HP_1,\mathrm{},P_j,N_1,\mathrm{},N_h$$

into the following rule in $`P`$:

$$HP_1,\mathrm{},P_j,N_1,\mathrm{},N_h,\varphi _{}^{}{}_{}{}^{}(𝐱)$$

where $`𝐱`$ is a tuple of variables in the clause.
* We translate every rule in $`T_{bck}`$ with a name $`\varphi `$

$$\varphi :HP_1,\mathrm{},P_j,N_1,\mathrm{},N_h$$

into the following rule in $`P`$:

$$HP_1,\mathrm{},P_j,\varphi _{}^{+}{}_{}{}^{}(𝐱),N_1,\mathrm{},N_h.$$

The following shows that an revised program corresponds with a generalized stable model.

###### Theorem 1

Let $``$ be a revision framework $`(T_{pst}T_{tmp}),T_{bck}`$ and $`R_{new}`$ be an added clause. $`(T_{pst}\{R_{new}\})(T_{tmp}T_{del}T_{new})`$ is a (minimally, resp.) revised program if and only if there is a generalized stable model of $`\tau ((T_{pst}\{R_{new}\})T_{tmp},T_{bck})`$ with a (minimal, resp.) set of abducibles $`\mathrm{\Theta }`$ s.t.

* $`T_{del}=\{R|(\varphi _{}^{}{}_{}{}^{}(𝐱)\theta )\mathrm{\Theta }`$

where $`\varphi `$ is a name of $`RT_{tmp}\}`$.
* $`T_{new}=`$
$`\{R\theta |(\varphi _{}^{+}{}_{}{}^{}(𝐱)\theta )\mathrm{\Theta }`$

where $`\varphi `$ is a name of $`RT_{bck}\}`$ $``$
$`\{head(R)body(R),(EQ(\theta _1)),\mathrm{},(EQ(\theta _n))|`$

$`(\varphi _{}^{}{}_{}{}^{}(𝐱)\theta _i)\mathrm{\Theta }`$ where $`\varphi `$ is a name of $`RT_{tmp}`$

and $`EQ(\theta _i)=((x_1=(x_1\theta _i))\mathrm{}(x_k=(x_k\theta _i)))`$

and $`𝐱=x_1,\mathrm{},x_k\}`$

We say that $`\mathrm{\Theta }`$ (minimally, resp.) realizes revision of $`R_{new}`$ to $``$.

Note that in the above theorem, we delete whole rules related to inconsistency and then add modified rules with negation of conjunctions of disequality in the body of the deleted rules. The modified rules are logically equivalent to rules in Definition 4 since we assume domain closure axiom and unique name axiom.

###### Example 2

Consider the revision framework in Example 1. Let us give names to the rules in $`T_{tmp}`$ and $`T_{bck}`$ as follows:

$`\varphi _1:r(X)c(X),b(X).`$

$`\varphi _2:b(X)c(X),r(X).`$

Then $`\tau (((T_{pst}\{R_{new}\})T_{tmp}),T_{bck})`$ is:

* $`A=\{\varphi _{1}^{}{}_{}{}^{},\varphi _{2}^{+}{}_{}{}^{}\}`$.
* $`P`$ becomes as follows:
$`c(c_1).`$
$`c(c_2).`$
$`r(c_1)`$.
$`r(X)c(X),b(X),\varphi _{1}^{}{}_{}{}^{}(X).`$
$`b(X)c(X),\varphi _{2}^{+}{}_{}{}^{}(X),r(X).`$

Then, we have two generalized models with minimal abducibles:

1. $`\mathrm{\Theta }=\{\varphi _{1}^{}{}_{}{}^{}(c_1)\}`$. Then, a minimally revised program is:

$`(T_{pst}\{R_{new}\})`$ and $`r(X)Xa,c(X),b(X).`$
2. $`\mathrm{\Theta }=\{\varphi _{2}^{+}{}_{}{}^{}(c_1)\}`$. Then, a minimally revised program is:

$`(T_{pst}\{R_{new}\})`$ and $`T_{tmp}`$ and $`b(c_1)c(c_1),r(c_1).`$

## Computing Revision by Abduction

To compute a revision, it is sufficient to compute a generalized stable model of $`\tau ((T_{pst}\{R_{new}\})T_{tmp},T_{bck})`$. But, if we concern a minimal revision, we need to compute all the generalized stable models and then compare sets of abducibles in these models to choose minimal sets of abducibles. For this purpose, it is desirable to restrict sets of abducibles to be compared as small as possible. This can be done if we compute only revision related to $`R_{new}`$. For example, suppose that some of temporary rules are not relevant to inconsistency of addition of $`R_{new}`$. If we naively compute all the generalized stable models, then we have to compare all the combination of in/out of abducibles for these irrelevant rules.

In order to avoid this kind of redundancy, we modify Satoh and Iwayama’s query evaluation procedure on stable models (?). Basically, we change the order of application of subprocedures so that we can use the procedure for consistency checking.

We impose rules in a revision framework must be range-restricted, that is, any variable in a rule $`R`$ must occur in $`pos(R)`$. However, any rule can be translated into range-restricted form by inserting a new predicate “$`dom`$” describing Herbrand universe for every non-range-restricted variable in the rule.

Before showing our procedure to compute revision, we need the following definitions. Let $`l`$ be a literal. Then, $`\overline{l}`$ denotes the complement of $`l`$.

###### Definition 8

Let $`P`$ be a logic program. A set of resolvents w.r.t. a ground literal $`l`$ and $`T`$, $`resolve(l,P)`$ is the following set of rules: $`resolve(l,P)=`$

$`\{(L_1,\mathrm{},L_k)\theta |`$ $`l`$ is negative and

$`HL_1,\mathrm{},L_kP`$ and $`\overline{l}=H\theta `$ by a ground substitution $`\theta \}`$

$`\{(HL_1,\mathrm{},L_{i1},L_{i+1},\mathrm{},L_k)\theta |`$

$`HL_1,\mathrm{},L_kP`$ and $`l=L_i\theta `$ by a ground substitution $`\theta \}`$

###### Definition 9

Let $`P`$ be a logic program. A set of deleted rules w.r.t. a ground literal $`l`$ and $`P`$, $`del(l,P)`$, is the following set of rules: $`del(l,P)=\{(HL_1,\mathrm{},L_k)\theta |`$ $`HL_1,\mathrm{},L_kP`$ and $`\overline{l}=L_i\theta `$ by a ground substitution $`\theta \}`$

###### Definition 10

Let $`P`$ be a logic program and $`P^{}`$ be an abducible-and-negation-removed program obtained by removing all integrity constraints in $`P`$ and all the negative literals and abducibles in the body of remaining rule and $`min(P^{})`$ be the least minimal model of $`P^{}`$.We define a relevant ground program $`\mathrm{\Omega }_P`$ for $`P`$ as follows: $`\mathrm{\Omega }_P=\{HB_1,\mathrm{},B_k,A_1,\mathrm{},A_m\mathrm{\Pi }_P|`$ $`B_imin(P^{})\text{ for each }i=1,\mathrm{},k.\}`$

We briefly explain our procedure. Our procedure consists of 4 subprocedures, $`rule\mathrm{\_}con(R,\mathrm{\Delta })`$, $`derive(p,\mathrm{\Delta })`$, $`literal\mathrm{\_}con(l,\mathrm{\Delta })`$, and $`deleted\mathrm{\_}con(R,\mathrm{\Delta })`$ where $`p`$ is a non-abducible atom and $`\mathrm{\Delta }`$ is a set of ground literals already assumed and $`l`$ is a ground literal and $`R`$ is a rule. $`rule\mathrm{\_}con(R,\mathrm{\Delta })`$, $`literal\mathrm{\_}con(l,\mathrm{\Delta })`$, and $`deleted\mathrm{\_}con(R,\mathrm{\Delta })`$ return union of $`\mathrm{\Delta }`$ and a set of ground literals which are assumed during the execution of the subprocedures. $`derive(p,\mathrm{\Delta })`$ return the above union and a substitution for $`p`$ which are made during the execution of $`derive(p,\mathrm{\Delta })`$.

In the procedure, we have a select operation and a fail operation. The select operation expresses a nondeterministic choice among alternatives. The fail operation expresses immediate termination of an execution with failure. Therefore, a procedure succeeds when its inner calls of subprocedures do not encounter fail. We say a subprocedure succeeds with (a substitution $`\theta `$ and) a set of assumptions $`\mathrm{\Delta }`$ when the subprocedure successfully returns ($`\theta `$ and) $`\mathrm{\Delta }`$.

Our procedure firstly starts from $`rule\mathrm{\_}con(R_{new},\{\})`$. $`rule\mathrm{\_}con(R_{new},\{\})`$ checks the consistency of a rule $`R_{new}`$ with a program $`P\{R_{new}\}`$. We can show the consistency of addition of $`R_{new}`$ by showing one of the following.

1. A literal $`l`$ in $`body(R_{new})`$ can be falsified. To do so, we invoke subprocedure $`literal\mathrm{\_}con`$ for $`\overline{l}`$.
2. Every positive literal $`p`$ in $`body(R_{new})`$ can be made true and every negative and every abducible literal $`l`$ can be consistently assumed and $`head(R_{new})`$ consistent. To do so, we invoke subprocedure $`derive`$ for $`p`$ and $`literal\mathrm{\_}con`$ for $`l`$ and $`head(R_{new})`$.

The informal specification of the other 3 subprocedures is as follows.

1. $`literal\mathrm{\_}con(l,\mathrm{\Delta })`$ checks the consistency of a ground literal $`l`$ with $`P\{R_{new}\}`$ and $`\mathrm{\Delta }`$. To show the consistency for assuming $`l`$, we add $`l`$ to $`\mathrm{\Delta }`$; then, we check the consistency of resolvents and deleted rules w.r.t. $`l`$ and $`P\{R_{new}\}`$.
2. $`derive(p,\mathrm{\Delta })`$ searches a rule $`R`$ of $`p`$ in a program $`P\{R_{new}\}`$ whose body can be made true with a ground substitution $`\theta `$ under a set of assumptions $`\mathrm{\Delta }`$. To show that every literal in the body can be made true, we call $`derive`$ for non-abducible positive literals in the body. Then, we check the consistency of other literals in the body with $`P\{R_{new}\}`$ and $`\mathrm{\Delta }`$. Note that because of the range-restrictedness, other literals in $`R`$ become ground after all the calls of $`derive`$ for non-abducible positive literals.
3. $`deleted\mathrm{\_}con(R,\mathrm{\Delta })`$ checks if a deletion of $`R`$ does not cause any contradictions with $`P\{R_{new}\}`$ and $`\mathrm{\Delta }`$. To show the consistency of the implicit deletion of $`R`$, it is sufficient to prove that the head of every ground instance $`R\theta `$ in $`\mathrm{\Omega }_{P\{R_{new}\}}`$ can be made either true or false.

Now, we describe a complete specification of the subprocedures in Figure 1 and Figure 2. In Figures, we denote a set of non-abducible positive literals, non-abducible negative literals, and abducibles (either negative or positive) in a rule $`R`$ as $`pos(R)`$, $`neg(R)`$ and $`abd(R)`$ respectively, and we denotes empty substitution as $`\epsilon `$, and $`\theta _i\sigma _i`$ expresses a composition of two substitutions $`\theta _i`$ and $`\sigma _i`$.

The following theorem on correctness for rule checking can be derived from correctness on query evaluation procedure of (?).

###### Theorem 2

Let $`P,A`$ be a consistent abductive framework. Suppose $`rule\mathrm{\_}con(R_{new},\{\})`$ succeeds for $`P`$ with $`\mathrm{\Delta }`$, then there is a generalized stable model $`M(\mathrm{\Theta })`$ for $`PR_{new},A`$ such that $`\mathrm{\Theta }`$ includes positive abducibles in $`\mathrm{\Delta }`$.

par

The above theorem only guarantees that $`R`$ is consistent with $`P`$ and the procedure produces some abducibles included in a generalized stable model. To compute revision, however, we must have the stronger result that $`\mathrm{\Delta }`$ includes all the necessary $`\varphi _{}^{+}{}_{}{}^{}`$’s and $`\varphi _{}^{}{}_{}{}^{}`$’s. Actually, we can guarantee this by the following theorem.

###### Theorem 3

Let $``$ be a revision framework $`(T_{pst}T_{tmp}),T_{bck}`$ such that $`T_{pst}T_{tmp}`$ is consistent and $`R_{new}`$ be an added rule. Suppose $`rule\mathrm{\_}con(R_{new},\{\})`$ succeeds for $`\tau ()`$ with $`\mathrm{\Delta }`$, then, a set of positive abducibles in $`\mathrm{\Delta }`$ realizes revision of $`R_{new}`$ to $``$.

The following theorem means that if we can search exhaustively in selecting the rules or cases and there is a generalized stable model whose abducibles minimally realizes a revision for addition of rule $`R_{new}`$, then we can find such a set of abducibles by our procedure. Note that this property is always guaranteed if a program is a finite propositional program or has finite constant symbols and no function symbols.

###### Theorem 4

Let $``$ be a revision framework $`(T_{pst}T_{tmp}),T_{bck}`$ and $`R_{new}`$ be an added rule. Suppose that every selection of rules or cases terminates for $`rule\mathrm{\_}con(R_{new},\{\})`$ with either success or failure for $`\tau ()`$. If $`\mathrm{\Theta }`$ minimally realizes revision of $`R_{new}`$ to $`T`$, then there is a selection of rules and cases such that $`rule\mathrm{\_}con(R_{new},\{\})`$ succeeds with $`\mathrm{\Delta }`$ where a set of abducibles in $`\mathrm{\Delta }`$ is equivalent to $`\mathrm{\Theta }`$.

Note that we cannot guarantee that positive abducibles of every $`\mathrm{\Delta }`$ always corresponds with a minimal revision. This problem is inherited from Satoh’s procedure in that it is not guaranteed for the procedure to produce a minimal abducibles. However, using the procedure, we can restrict sets of abducibles related with inconsistency and, thus, considered sets of abducibles to choosing minimal sets are smaller than sets of abducibles from a naive calculation of all the generalized stable models.

###### Example 3

Consider the revision framework in Example 1. The following are two sequences of main calls of subprocedures for $`rule\mathrm{\_}con(R_{new},\{\})`$ to $`\tau (U)`$ shown in Example 2. In the following, $`rc`$, $`lc`$, $`dr`$ and $`dc`$ corresponds with $`rule\mathrm{\_}con`$, $`literal\mathrm{\_}con`$, $`derive`$ and $`deleted\mathrm{\_}con`$ respectively, and indexes in the front express a nesting structure of the calls. Note that existence of “$`c(c_2)`$.” in $`T_{pst}`$ does not influence these derivations.

Sequence 1 (for $`I_1,O_1`$ in Example 1)

$`rc((r(c_1)),\{\})`$

1 $`lc(r(c_1),\{\})`$

1.1 $`rc((c(c_1),b(c_1),\varphi _{1}^{}{}_{}{}^{}(c_1)),\{r(c_1)\})`$

1.1.1 $`dr(c(c_1)\{r(c_1)\})`$

select $`c(c_1).`$

1.1.1.2 $`lc(c(c_1)\{r(c_1)\})`$

1.1.1.2.1 $`rc((r(c_1)b(c_1),\varphi _{1}^{}{}_{}{}^{}(c_1)),\{c(c_1),r(c_1)\})`$

1.1.1.2.1.1 $`lc(b(c_1),\{c(c_1),r(c_1)\})`$

1.1.1.2.1.1.1 $`rc((r(c_1)c(c_1),\varphi _{1}^{}{}_{}{}^{}(c_1)),`$

$`\{c(c_1),b(c_1),r(c_1)\})`$

1.1.1.2.1.1.1.1 $`dr(\varphi _{1}^{}{}_{}{}^{}(c_1),\{c(c_1),b(c_1),r(c_1)\})`$

1.1.1.2.1.1.1.1.1 $`lc(\varphi _{1}^{}{}_{}{}^{}(c_1),\{c(c_1),b(c_1),r(c_1)\})`$

1.1.1.2.1.1.1.1.1.1 $`dc((r(c_1)c(c_1),b(c_1),\varphi _{1}^{}{}_{}{}^{}(c_1)),`$

$`\{\varphi _{1}^{}{}_{}{}^{}(c_1),c(c_1),b(c_1),r(c_1)\})`$

1.1.1.2.1.1.2 $`rc((c(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),r(c_1)),`$

$`\{\varphi _{1}^{}{}_{}{}^{}(c_1),c(c_1),b(c_1),r(c_1)\})`$

1.1.1.2.1.1.2.1 $`lc(\varphi _{2}^{+}{}_{}{}^{}(c_1),`$

$`\{\varphi _{1}^{}{}_{}{}^{}(c_1),c(c_1),b(c_1),r(c_1)\})`$

1.1.1.2.1.1.2.1.1 $`dc((b(c_1)c(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),r(c_1)),`$

$`\{\varphi _{1}^{}{}_{}{}^{}(c_1),c(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),b(c_1),r(c_1)\})`$

1.1.1.2.2 $`rc((b(c_1)\varphi _{2}^{+}{}_{}{}^{}(c_1),r(c_1)),`$

$`\{\varphi _{1}^{}{}_{}{}^{}(c_1),c(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),b(c_1),r(c_1)\})`$

1.2 $`rc((b(c_1)c(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1)),`$

$`\{\varphi _{1}^{}{}_{}{}^{}(c_1),c(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),b(c_1),r(c_1)\})`$

1.3 $`dc((r(c_1)),`$

$`\{\underset{¯}{\varphi _{1}^{}{}_{}{}^{}(c_1)},c(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),b(c_1),r(c_1)\})`$

Sequence 2 (for $`I_2,O_2`$ in Example 1)

$`rc((r(c_1)),\{\})`$

1 $`lc(r(c_1),\{\})`$

1.1 $`rc((c(c_1),b(c_1),\varphi _{1}^{}{}_{}{}^{}(c_1)),\{r(c_1)\})`$

1.1.1 $`dr(c(c_1)\{r(c_1)\})`$

select $`c(c_1).`$

1.1.1.2 $`lc(c(c_1)\{r(c_1)\})`$

1.1.1.2.1 $`rc((r(c_1)b(c_1),\varphi _{1}^{}{}_{}{}^{}(c_1)),\{c(c_1),r(c_1)\})`$

1.1.1.2.1.1 $`dr(b(c_1),\{c(c_1),r(c_1)\})`$

select $`b(c_1)c(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),r(c_1).`$

1.1.1.2.1.1.2 $`dr(c(c_1),\{c(c_1),r(c_1)\})`$

1.1.1.2.1.1.3 $`lc(\varphi _{2}^{+}{}_{}{}^{}(c_1),\{c(c_1),r(c_1)\})`$

1.1.1.2.1.1.3.1 $`rc((b(c_1)c(c_1),r(c_1)),`$

$`\{\varphi _{2}^{+}{}_{}{}^{}(c_1),c(c_1),r(c_1)\})`$

1.1.1.2.1.1.3.1.1 $`lc(b(c_1),\{\varphi _{2}^{+}{}_{}{}^{}(c_1),c(c_1),r(c_1)\})`$

1.1.1.2.1.1.3.1.1.1 $`dc((r(c_1)c(c_1),b(c_1),\varphi _{1}^{}{}_{}{}^{}(c_1)),`$

$`\{b(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),c(c_1),r(c_1)\})`$

1.1.1.2.1.1.4 $`lc(r(c_1),\{b(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),c(c_1),r(c_1)\})`$

1.1.1.2.1.1.5 $`lc(b(c_1),\{b(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),c(c_1),r(c_1)\})`$

1.1.1.2.2 $`rc((b(c_1)\varphi _{2}^{+}{}_{}{}^{}(c_1),r(c_1)),`$

$`\{b(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),c(c_1),r(c_1)\})`$

1.2 $`rc((b(c_1)c(c_1),`$

$`\varphi _{2}^{+}{}_{}{}^{}(c_1)),\{b(c_1),\varphi _{2}^{+}{}_{}{}^{}(c_1),c(c_1),r(c_1)\})`$

1.3 $`dc((r(c_1)),\{b(c_1),\underset{¯}{\varphi _{2}^{+}{}_{}{}^{}(c_1)},c(c_1),r(c_1)\})`$

## Related Work

There are works on calculation method of updates (??). (?) propose a top-down procedure to compute view updates in a database for proving a given goal, but it is not applicable to updating a normal logic program in general. (?) give a bottom-up procedure for an update of an acyclic program to explain given observations in the perfect model of an acyclic program and therefore, cannot apply to a normal logic program which has multiple stable models. Moreover, using bottom-up computation would lead to an irrelevant derivation to an added rule.

In (?), translation from an update framework (?) to an extended logic program is provided 333Recently, (?) independently proposes exactly the same technique as our translation to show correspondence their extended abduction and ordinary abduction.. Differences between our translation and their translation are as follows.

* They give a translation to compute an update to explain a goal whereas we consider a revision to avoid inconsistency of addition of a rule.
* They introduce a new predicate symbol in stead of abducibles. This makes their translation rather complex. If we translate our translated abductive logic program to a new normal logic program by a method proposed in (?), the new normal logic program would be the same as their program.
* They consider addition/deletion of the whole rules to derive a given observation. That is, instead of considering deletion/addition of parts of $`\mathrm{\Pi }_{T_{tmp}}`$/$`\mathrm{\Pi }_{T_{bck}}`$ in Definition 4, they propose deletion/addition of parts of $`T_{tmp}`$/$`T_{bck}`$ . At least, however, to handle exception of integrity constraints in software engineering (?), we believe that our fine-grained approach is better since we would like to keep consistent part of integrity constraints for further checking of other data when some instances cause inconsistency. See the detailed discussion in (?).

There are many procedures to compute stable models, generalized stable models or abduction. If we use a bottom-up procedure for our translated abductive logic program to compute all the generalized stable models naively, then sets of abducibles to be compared would be larger since abducibles of irrelevant temporary rules and addable rules with inconsistency will be considered. Therefore, it is better to compute abducibles related with inconsistency. To our knowledge, top-down procedure which can be used for this purpose is only Satoh and Iwayama’s procedure since we need a bottom-up consistency checking of addition/deletion of literals during computing abducibles for revision. This task is similar to integrity constraint checking in (?) and Satoh and Iwayama’s procedure includes this task.

## Conclusion

In this paper, we propose an abductive top-down procedure to compute a minimal revised program which traverses only relevant parts of the program to the added rule. It is done by translating a revision framework of a normal logic program into an abductive logic program.

As a future work, we would like to find an efficient method of computing a minimal revision directly by combining our top-down procedure and ATMS-like method of memorizing justifications of revisions.

## Acknowledgments

This research is partly supported by Grant-in-Aid for Scientific Research on Priority Areas, “Principles for Constructing Evolutionary Software”, The Ministry of Education, Japan. We also thank the anonymous referees for valuable comments on this paper.