# Planetary nebulae and the chemical evolution of the Magellanic Clouds

W. J. Maciel  11affiliation: Instituto de Astronomia, Geofísica e Ciências
Atmosféricas, Universidade de São Paulo, Brazil. R. D. D. Costa
11affiliationmark:  and T. E. P. Idiart11affiliationmark:  W. J. Maciel, R. D.
D. Costa and T. E. P. Idiart: Instituto de Astronomia, Geofísica e Ciências
Atmosféricas, Universidade de São Paulo - Rua do Matão 1226, CEP 05508-900,
São Paulo SP, Brazil<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The determination of accurate chemical abundances of planetary nebulae (PN) in
different galaxies allows us to obtain important constraints of chemical
evolution models for these systems. We have a long term program to derive
abundances in the galaxies of the Local Group, particularly the Large and
Small Magellanic Clouds. In this work, we present our new results on these
objects and discuss their implications in view of recent abundance
determinations the literature. In particular, we obtain distance-independent
correlations involving He, N, O, Ne, S, and Ar, and compare the results with
data from our own Galaxy and other galaxies in the Local Group. As a result of
our observational program, we have a large database of PN in the Galaxy and
the Magellanic Clouds, so that we can obtain reliable constraints to the
nucleosynthesis processes in the progenitor stars in galaxies of different
metallicities.

ISM: planetary nebulae: general galaxies: Magellanic Clouds galaxies:
abundances

##  0.1 Introduction

The study of the chemical evolution of the galaxies in the Local Group,
particularly the Milky Way and the Magellanic Clouds, can be significantly
improved by the consideration of the chemical abundances of planetary nebulae
(PN) (see for example Maciel et al. 2006a, Richer & McCall 2006, Buzzoni et
al. 2006, and Ciardullo 2006). These objects are produced by low and
intermediate mass stars, with main sequence masses roughly between 0.8 and
8$\,M_{\odot}$, and present a reasonably large age and metallicity spread. As
a conclusion, they provide important constraints to the chemical evolution
models applied to these systems, and can also be used to test nucleosynthetic
processes in the PN progenitor stars. In particular, the PN abundances in the
nearby Magellanic Clouds can be derived with a high acuracy, comparable to the
objects in the Milky Way, so that they can be especially useful in the study
of the chemical evolution of these galaxies. In this work, we present some
recent results on the determination of chemical abundances from PN in the
Large and Small Magellanic Clouds derived by our group, and compare these
results with recent data from our own Galaxy and other galaxies in the Local
Group. We also take advantage of the inclusion of similar determinations from
the recent literature, so that the database of PN in the Magellanic Clouds is
considerably increased, allowing a better determination of observational
constraints of the nucleosynthetic processes ocurring in the progenitor stars.
Preliminary results of this work have been presented by Maciel, Costa & Idiart
(2006a, 2008).

##  0.2 The Sample

We have considered a sample of PN both in the LMC and SMC on the basis of
observations secured at the 1.6m LNA telescope located in southeast Brazil and
the ESO 1.5m telescope in La Silla, Chile. Details of the observations and the
resulting abundances can be found in the following references: de Freitas
Pacheco et al. (1993a, 1993b), Costa et al. (2000), and Idiart et al. (2007).
In these papers, abundances of He, N, O, S, Ne and Ar have been determined for
23 nebulae in the LMC and 46 objects in the SMC. The abundances presented in
Idiart et al. (2007) were based on average fluxes obtained by taking into
account some recent results from the literature, so that there may be some
differences compared with our originally derived values. For details the
reader is referred to the discussion in that paper.

In order to increase the PN database in the Magellanic Clouds, we have also
taken into account the samples by Stasińska et al. (1998), which included
abundances of He, N, O, and Ne for 61 nebulae in the SMC and 139 objects in
the LMC, and Leisy & Dennefeld (2006), containing 37 objects in the SMC and
120 nebulae in the LMC. In Stasińska et al. (1998), a collection was obtained
of photometric and spectroscopic data of PN in five different galaxies,
including the Magellanic Clouds. Although the original sources of the data are
rather heterogeneous, the plasma diagnostics and determination of the chemical
abundances were processed in the same way, so that the degree of homogeneity
of the data was considerably increased. The Leisy & Dennefeld (2006) sample is
a more homogeneous one, in which a larger fraction of the observations were
made by the authors themselves, and all abundances were re-derived in an
homogeneous way, as in Stasińska et al. (1998). As we will show in the next
section, the similarity of the methods in the abundance determinations
warrants comparable abundances, so that a larger sample was obtained.

##  0.3 Results and discussion

###  0.3.1 Average abundances

Average abundances of all elements in the SMC and LMC according to the three
samples considered are shown in Table 1. Helium abundances are given as He/H
by number as usual, while for the heavier elements the quantity given is
$\epsilon({\rm X})=\log{\rm X/H}+12$. Although the samples considered here are
probably the largest ones with carefullly derived abundances in the Magellanic
Clouds, they cannot be considered as complete. The total number of PN in these
systems is not known, but recent estimates point to about 130 and 980 objects
for the SMC and LMC, respectively (cf. Jacoby 2006 and Shaw 2006). Therefore,
incompleteness effects may still affect the results presented in this paper.

The He abundances show a good agreement in all samples within the average
uncertainties. The IAG and Leisy samples show a slightly higer He abundance in
the LMC compared to the SMC, but the differences between these objects are in
all cases smaller than the estimated uncertainties.

The O/H abundances, which are in general the best determined of all heavy
elements considered here, also show a good agreement among the samples.
Moreover, in all cases the LMC is richer than the SMC, as expected, and the
average metallicity difference is in the range 0.3 to 0.5 dex, which is
consistent with the metallicities given by Stanghellini (2008), namely
$Z=0.004$ and $Z=0.008$ for the SMC and LMC, respectively.

The Ar/H and Ne/H ratios show a similar behaviour as O/H, noticing that the
IAG data do not include Ne abundances for the LMC, and that Stasińska et al.
(1998) do not list Ar/H abundances for both galaxies. The sulfur abundances
seem to be less reliable, as can be seen from the large standard deviations
obtained in the IAG and Leisy & Dennefeld samples. Moreover, the estimated
average S/H ratio in the SMC is slightly larger than in the LMC according to
the IAG data, contrary to our expectations, while in the Leisy & Dennefeld
sample the LMC abundance is larger by only 0.27 dex in comparison with the
SMC. In fact, these characteristics of the sulfur abundances in Magellanic
Cloud PN can be observed in previous analyses, as for example in the summary
by Kwok (2000, Table 19.1, p. 202), where the S/H ratios in the SMC and LMC
are indistinguishable within the given uncertainties. Clearly, the
determination of S/H abundances in the Magellanic Cloud PN - and galactic
nebulae as well - is apparently affected by some additional effects, as
compared to the previous elements. In the following we will give further
evidences on the problem of sulfur abundances in planetary nebulae.

From Table 1, it can be seen that the nitrogen abundances also follow the same
pattern as O/H, Ar/H, and Ne/H, even though the N/H ratio is affected by the
dredge-up episodes occuring in the PN progenitor stars. This is further
discussed in Section 5, but from the results shown in the last column of Table
1, it is suggested that the average nitrogen contamination from the PN
progenitor stars is small. Average N/H abundances of of Magellanic Cloud PN
are given by Stanghellini (2008), where an effort was made to take into
account objects of different morphologies. The average N/H abundances in the
whole sample are $1.48\times 10^{-4}$ and $0.29\times 10^{-4}$ for the LMC and
SMC, respectively, which correspond to $\epsilon({\rm N})=8.17$ and 7.46, in
the notation of Table 1. These results correctly indicate that the LMC is
richer in N than the SMC, as also reported in Table 1, and the absolute value
of the SMC abundances given by Stanghellini (2008) is very similar to the
results of the 3 samples considered here, but the average abundance for the
LMC nebulae is much higher than our results. In fact, the N/H abundances of
the LMC given in Stanghellini (2008) are close to the Milky Way values, which
is paradoxical, as the LMC has a much lower metallcity than the Galaxy. Part
of the discrepancy may be caused by the fact that the sample used in that
paper includes a larger proportion of bipolar nebulae, which are ejected by
higher mass progenitor stars, which produce a larger nitrogen contamination
than the lower mass objects. This problem needs further clarification.

-2cm-2cm

Table 1: Average abundances of PN in the Magellanic Clouds.

| He | O | S | Ar | N | Ne
---|---|---|---|---|---|---
IAG/USP |  |  |  |  |  |
SMC | $0.097\pm 0.035$ | $7.89\pm 0.44$ | $6.98\pm 0.58$ | $5.59\pm 0.36$ | $7.35\pm 0.49$ | $7.14\pm 0.42$
LMC | $0.119\pm 0.023$ | $8.40\pm 0.20$ | $6.72\pm 0.31$ | $6.01\pm 0.25$ | $7.69\pm 0.50$ | —
Stasińska |  |  |  |  |  |
SMC | $0.094\pm 0.025$ | $7.74\pm 0.50$ | — | — | $7.46\pm 0.37$ | $7.10\pm 0.40$
LMC | $0.090\pm 0.032$ | $8.10\pm 0.31$ | — | — | $7.76\pm 0.45$ | $7.44\pm 0.41$
Leisy |  |  |  |  |  |
SMC | $0.093\pm 0.025$ | $8.01\pm 0.29$ | $6.86\pm 0.67$ | $5.57\pm 0.27$ | $7.39\pm 0.47$ | $7.14\pm 0.36$
LMC | $0.105\pm 0.035$ | $8.26\pm 0.35$ | $7.13\pm 0.67$ | $5.99\pm 0.26$ | $7.77\pm 0.57$ | $7.46\pm 0.48$
Orion | $0.098\pm 0.004$ | $8.55\pm 0.07$ | $7.02\pm 0.10$ | $6.52\pm 0.18$ | $7.78\pm 0.12$ | $7.82\pm 0.16$
Sun | $0.092\pm 0.009$ | $8.80\pm 0.11$ | $7.26\pm 0.08$ | $6.48\pm 0.11$ | $7.97\pm 0.07$ | $8.08\pm 0.01$
30 Dor | $0.087\pm 0.001$ | $8.33\pm 0.02$ | $6.84\pm 0.10$ | $6.09\pm 0.10$ | $7.05\pm 0.08$ | $7.65\pm 0.06$
NGC 346 | — | $8.15$ | $6.40$ | $5.82$ | $6.81$ | $7.32$

###  0.3.2 Abundances of individual nebulae

Figure 1: Abundances of O/H (solid dots), N/H (empty triangles) and Ne/H
(empty circles) from the sample by Stasińska et al. (1998) as a function of
data from the IAG/USP group for the SMC. Figure 2: The same as Fig. 1 for the
LMC. No Ne/H data is available in the IAG sample for this galaxy. Figure 3:
Abundances of O/H (solid dots), S/H (stars), Ar/H (crosses), N/H (empty
triangles), and Ne/H (empty circles) from the sample by Leisy & Dennefeld
(2006) as a function of data from the IAG/USP group for the SMC. Figure 4: The
same as Fig. 3 for the LMC. No Ne/H data is available in the IAG sample.

In order to illustrate the internal agreement of the three PN samples
considered in this work, we present in Figs. 1 and 2 the abundances of O/H
(solid dots), N/H (empty triangles) and Ne/H (empty circles) as derived by
Stasińska et al. (1998) as a function of the IAG/USP data, for the SMC and LMC
nebulae, respectively. The same comparisons are shown in Figs. 3 and 4 taking
into account the data by Leisy & Dennefeld (2006), in which case we also
include abundances of S/H (stars) and Ar/H data (crosses). An average error
bar is included at the lower right corner of the figures. The agreement of
both samples with our own data is generally very good, within the average
uncertainties of the abundance data, which are about 0.1 to 0.2 dex for the
best derived abundances, and of 0.2 to 0.3 for the less accurate element
ratios. Some scatter is to be expected, especially taking into account that
the abundances of several nebulae are flagged as uncertain (:) by Leisy &
Dennefeld (2006). The main discrepancies between the IAG data and the results
by Stasińska et al. (1998) occur for a few objects in the SMC, for which our
O/H and Ne/H abundances differ by an amount larger than the average
uncertainty (cf. Fig. 1), while for the LMC a small group of nebulae have
higher N/H abundances as derived by Stasińska et al. (1998) (cf. Fig. 2).
Concerning the Leisy & Dennefeld (2006) sample, the main discrepancies are
restricted to some S/H data, as can be seen from Figs. 3 and 4. The origin of
these discrepancies is not clear, but it should be stressed that the vast
majority of the objects in common in the 3 samples have similar results, as
illustrated in Figs. 1 to 4.

###  0.3.3 Metallicity differences: the Galaxy and the Magellanic Clouds

The PN abundances of the heavy elements O, S, Ne, and Ar as given in Table 1
are expected to reflect the average metallicities of the Magellanic Clouds,
which are a few dex lower than in the Milky Way, as these elements are not
produced by the PN progenitor stars. This can be confirmed by comparing the PN
abundances with the abundances in the Orion Nebula, which can be taken as
representative of the present heavy element abundances in the Galaxy. From the
compilation by Stasińska (2004), we obtain the abundances given at the end of
Table 1. For comparison purposes, the average solar abundances from the same
source are also included. For the Orion Nebula and the Sun the uncertainties
given are not the intrinsic uncertainties of the data, but the dispersion of
the measurements in the recent literature as considered by Stasińska (2004).
It can be seen that the Orion Nebula abundances are higher than the Magellanic
Clouds PN by about 0.2 to 0.5 dex for the LMC and 0.5 to 0.8 dex for the SMC
in the case of oxygen. The average for the Orion Nebula, $\epsilon_{ON}({\rm
O})\simeq 8.55$, is also essentially the same as in the galactic PN,
$\epsilon_{PN}({\rm O})\simeq 8.65$ (cf. Maciel et al. 2006a). For S, Ne, and
Ar a similar comparison is obtained, although the S abundance in the LMC is
actually somewhat higher than in the Orion Nebula according to the data by
Leisy & Dennefeld (2006). The difference in the abundances is also smaller in
the case of nitrogen, which is a clear evidence of the N enhancement in the PN
progenitor stars.

###  0.3.4 The metallicity distribution

Figure 5: The O/H abundance distribution of the Magellanic Clouds from the
IAG/USP data. Figure 6: The same as Fig. 5 for the data by Stasińska et al.
(1998). Figure 7: The same as Fig. 5 for the data by Leisy & Dennefeld (2006).

The available data on PN in the Magellanic Clouds can be used to infer the
metallicity distribution in these systems, on the basis of the derived
abundances of O, S, Ne, and Ar. A comparison of the distributions in different
systems can be used to infer their average metallicities, with consequences on
the star formation rates. As an example, Figs. 5. 6 and 7 show the O/H
distribution in the Magellanic Clouds according to the three samples
considered in this work. The metallicity difference between the SMC and the
LMC can be clearly observed in all samples, amounting to about 0.4 to 0.5 dex
in average. The difference is especially well defined in our sample, as shown
in Fig. 5. In a comparison with the Milky Way, the galactic disk nebulae
extend to a higher metallicity, up to $\epsilon({\rm O})\simeq 9.2$, while the
LMC objects reach $\epsilon({\rm O})\simeq 8.8$ and the lowest metallicities
in the SMC are about $\epsilon({\rm O})\simeq 7.0$. Concerning the remaining
elements that are not affected by the evolution of the PN progenitor stars,
the Ar/H abundance distribution has a similar pattern, while the S/H data is
less clear, as already mentioned. We will discuss this element in more detail
in the next section. For Ne/H we have no IAG data for the LMC, but the larger
Leisy & Dennefeld (2006) sample clearly confirms the 0.4 to 0.5 dex difference
between the LMC and the SMC.

The metallicity distribution of the PN as shown in Figs. 5, 6, and 7 can also
be compared with galactic data, both for disk and bulge PN. Cuisinier et al.
(2000) considered a sample of 30 bulge nebulae and a compilation containing
about 200 disk PN, and concluded that both O/H distributions are similar,
peaking around 8.7–8.8 dex, and extending form $\epsilon({\rm O})\simeq 8.0$
to $\epsilon({\rm O})\simeq 9.2$. More recently, Escudero et al. (2004)
obtained a similar distribution using a bulge sample twice as large, which
extended to about 7.5 dex (see also Costa et al. 2008). According to Figs.
5–7, the O/H distributions are displaced relative to the Milky Way by
approximately 0.4 and 0.7 dex towards shorter metallicities for the LMC and
SMC, respectively, in good agreement with the results discussed in Section
4.1.

###  0.3.5 Abundance correlations: elements not produced by the progenitor
stars

Photoionized nebulae, comprising both PN and HII regions, are extremely useful
to study chemical abundances in different systems. While HII regions reflect
the present chemical composition of star-forming systems, PN is helpful to
trace the time evolution of the abundances, especially when an effort is made
to establish their age distribution (see for example Maciel et al. 2006b). The
elements S, Ar and Ne are probably not produced by the PN progenitor stars, as
they are manufactured in the late evolutionary stages of massive stars.
Therefore, S, Ar, and Ne abundances as measured in PN should reflect the
interstellar composition at the time the progenitor stars were formed. Since
in the interstellar medium of star-forming galaxies such as the Magellanic
Clouds the production of O and Ne is believed to be dominated by type II
supernovae, we may conclude that the original O and Ne abundances are not
significantly modified by the stellar progenitors of bright PN.

The variation of the ratios S/H, Ar/H and Ne/H with O/H usually show a good
positive correlation for all studied systems in the Local Group, with similar
slopes close to unity. The main differences lie in the average metallicity of
the different galaxies, which can be inferred from the observed metallicity
range, as we have seen in the previous section.

Fig. 8 shows the Ne/H ratio as a function of O/H for the SMC, while Fig. 9
corresponds to the LMC. In these figures we include the combined samples
mentioned in Section 2 as follows: IAG/USP data (filled circles), Stasińska et
al. (1998) (empty circles), and Leisy & Dennefeld (2006) (crosses). Average
error bars are included at the lower right corner of the figures. It can be
seen that the correlation is very good, with a slope in the range 0.8–0.9 in
both cases. The Ne/H $\times$ O/H relation is probably the best example
provided by PN regarding the nucleosynthesis in massive stars. This
correlation is very well defined, as shown in Figs. 8 and 9, and is
essentially the same as derived from HII regions in different star forming
galaxies of the Local Group, including the Milky Way, and in emission line
galaxies as well, as clearly shown by Richer & McCall (2006) and Richer (2006,
see also Henry et al. 2006).

The Ar/H data shows a similar correlation with O/H, as can be seen from Figs.
10 and 11, but the correlation is poorer, which may be due to the fact that
the samples are smaller, since Stasińska et al. (1998) do not present argon
data. Again, the main discrepancy lies in the S/H data, as can be seen from
Figs. 12 and 13. Although most objects define a positive correlation, which is
especially true for the LMC, the dispersion is much larger in the S/H data
compared to the previous elements, again suggesting that a problem remains in
the interpretation of the S/H abundances in planetary nebulae. In particular,
both the IAG/USP and Leisy & Dennefeld data suggest a scattering diagram on
the S/H $\times$ O/H plane for the SMC, with an average abundance around
$\epsilon({\rm S/H})=\log({\rm S/H})+12\simeq 7.0$. A weaker correlation
involving sulfur is to be expected, since the diagnostic lines for this
element are weaker than e.g. for oxygen or neon. However, the real situation
may be more complex, so that a more detailed discussion is appropriate.

Figure 8: Distance-independent correlation of Ne/H $\times$ O/H for the SMC.
Filled circles: IAG/USP data; empty circles: Stasińska et al. (1998); crosses:
Leisy & Dennefeld 2006). Figure 9: The same as Fig. 8, for the LMC. No IAG/USP
data is available for this object. Figure 10: Distance-independent correlation
of Ar/H $\times$ O/H for the SMC. Symbols are as in Fig. 8. Figure 11: The
same as Fig. 10, for the LMC. Figure 12: Distance-independent correlation of
S/H $\times$ O/H for the SMC. Symbols are as in Fig. 8. Figure 13: The same as
Fig. 12, for the LMC. Figure 14: Comparison of the Spitzer results by Bernard-
Salas et al. (2008) and the IAG/USP sample. circles: SMC, Ne/H data;
triangles: SMC, S/H abundances; crosses: LMC, S/H data.

A hint on the problem of the sulfur abundances in PN can be obtained by
comparing our S/H abundances with the recent determinations by Bernard-Salas
et al. (2008), who have presented Ne/H and S/H abundances for 25 PN in the
Magellanic Clouds using Spitzer data. These results have been obtained on the
basis of high-resolution spectroscopic observations in the infrared, and are
in principle more accurate compared with the abundances of our present sample,
since the uncertainties in the electron temperatures do not affect the
infrared lines, the interstellar extinction effects are smaller, and the use
of the often uncertain ionization correction factors is greatly reduced (cf.
Bernard-Salas et al. 2008). A comparison of the Ne/H and S/H abundances from
this source and those by the IAG/USP group is shown in Fig. 14, where the
adopted uncertainties are also shown. There are eleven objects in common,
which is a small but representative sample. In the figure, the circles refer
to Ne/H and the triangles for S/H for the SMC, while the crosses are S/H data
for PN in the LMC.

It can be seen that the Ne/H abundances show a very good agreement with the
infrared data, while for S/H there is a tedency for our values to be larger
than those by Bernard-Salas et al. (2008). Although the differences are not
very large except for a few nebulae, it may be suggested that the S/H data
presented here should be considered as upper limits. Inspecting Figs. 12 and
13, that would be expected especially for those nebulae having lower oxygen
abundances, which would explain the scatter diagram observed in Fig. 12. In
Bernard-Salas et al. (2008), a similar comparison of the Spitzer S/H
abundances with data by Leisy & Dennefeld (2006) was presented, and it was
shown that the latter are also systematically larger than the infrared
results. This was interpreted by Bernard-Salas et al. (2008) as the ionization
correction factors used by Leisy & Dennefeld (2006) overestimated the
contribution of the S+3 ion to the total sulfur abundances. In fact, several
of the S/H values for Magellanic Cloud PN in Leisy & Dennefeld (2006) are
flagged as upper limits. While commenting on the large dispersion of their
$\log{\rm S/H}\ \times\log{\rm O/H}$ plot, the authors stress that the sulfur
abundances are affected by several problems, such as the lack of [SIV] or
[SIII] lines, blending with oxygen lines, and innacuracies in the adopted
electron temperatures. By considering only the nebulae for which the sulfur
data is more reliable, Leisy & Dennefeld (2006) obtain a somewhat reduced
dispersion on the $\log{\rm S/H}\ \times\log{\rm O/H}$ plane, but it is still
concluded that the sulfur abundances are not good metallicity indicators for
Magellanic Cloud planetary nebulae.

A discussion of the sulfur abundance problem in PN was recently given by Henry
et al. (2004, 2006). These authors identified a so-called “sulfur anomaly”, or
the lack of agreement of the S/H ratio in PN with corresponding data from HII
regions and other objects. From an analysis of the abundances in Milky Way
planetary nebulae, HII regions and blue compact galaxies, it was suggested
that the origin of the “sulfur anomaly” is probably linked to the presence of
S+3 ions, which would affect the total sulfur abundances, at least in some
nebulae. According to this view, the abundances of at least some of the
galactic PN are underestimated, in the sense that the measured S/H ratio is
lower than expected on the basis of the derived O/H abundances. If this
explanation is valid for Magellanic Cloud PN, it would probably affect those
objects with higher O/H ratios, so it is an alternative to the previous
suggestion based on the comparison of optical abundances with infrared data.

However, other factors may play a role, such as the weakness of the sulfur
lines, the assumptions leading to the ionization correction factors, etc., so
that this problem deserves further investigation.

###  0.3.6 Abundance correlations: elements produced by the progenitor stars

Considering now the elements that are produced during the evolution of the PN
progenitor stars, namely, He and N, Figs. 15 and 16 show the derived
correlations of N/H and O/H for the SMC and LMC, respectively. As expected, a
positive correlation is observed, which is especially evident in the case of
the LMC, but the dispersion of the data is larger than in the case of Ne and
Ar. This is due to the fact that the PN display both the original N present at
the formation of the star and the contamination that is dredged up at the AGB
branch of the stellar evolution. In other words, the N/H ratio measured in PN
shows some contamination, or enrichment, in comparison with the original
abundances in the progenitor star.

Figure 15: Distance-independent correlation of N/H $\times$ O/H for the SMC.
Symbols are as in Fig. 8. Figure 16: The same as Fig. 15, for the LMC. Figure
17: Distance-independent correlation of N/H $\times$ He/H for the SMC. Symbols
are as in Fig. 8. Figure 18: The same as Fig. 17, for the LMC. Figure 19:
Distance-independent correlation of N/O $\times$ He/H for the SMC. Symbols are
as in Fig. 8. Figure 20: The same as Fig. 19, for the LMC. Figure 21:
Distance-independent correlation of N/O $\times$ O/H for the SMC. Symbols are
as in Fig. 8. Figure 22: The same as Fig. 21, for the LMC.

An estimate of the nitrogen enrichment from the PN progenitor stars can be
made by comparing the average N/H abundances of Table 1 with those of HII
regions. The Orion value given in the table is similar to the PN abundances
for the 3 samples considered, but HII regions in the lower metallicity
Magellanic Clouds have accordingly lower nitrogen abundances. As an example,
for 30 Doradus, the brightest HII region in the LMC, Peimbert (2003) estimates
$\epsilon({\rm N})=7.05$ based on echelle spectrophotometry, assuming no
temperature fluctuations ($t^{2}=0.00$). Comparing this result with the data
of Table 1, an average enrichment of about 0.6–0.7 dex is obtained for the N/H
ratio. Concerning HII regions in the SMC, Relaño et al. (2002) estimate
$\epsilon({\rm N})=6.81$ for NGC 346 on the basis of photoionization models,
which implies an enrichment of 0.5–0.6 dex for the PN samples listed in Table
1. These enrichment factors may be affected by the chemical evolution of the
host galaxy, which includes the average increase of the metallicity as the
galaxy evolves, but it is interesting that similar factors are obtained both
for the LMC and SMC. The quoted values for 30 Dor and NGC 346 are included at
the bottom of Table 1, as representative of HII in the Magellanic Clouds.

Figs. 17 and 18 show the N/H abundances as a function of the He/H ratio, while
Figs. 19 and 20 are the corresponding plots for N/O as a function of He/H. As
pointed out in the literature (cf. Kwok 2000), these ratios present
enhancements relative to the average interstellar values. The dispersion is
again large, but a positive correlation can also be observed, as expected,
since the same processes that increase the nitrogen abundances in PN also
affect the He/H ratio. A plot similar to Figs. 19 and 20 was presented by Shaw
(2006), in an effort to separate PN of different morphologies. In the LMC,
some objects in the sample by Stasińska et al. (1998) have very low He
abundances while the N/O ratio is normal, suggesting that neutral helium may
be present in these objects. As pointed out by Maciel et al. (2006a), the N/O
$\times$ He/H ratios in the Magellanic Clouds support the correlation observed
in the Milky Way, but the N/O ratio is comparatively lower. The O/H ratio
corresponding to the SMC is also lower, which can be interpreted as an
evidence that the lower metallicity environment in the SMC leads to a smaller
fraction of Type I PN, which are formed by the more massive stars in the
Intermediate Mass Star bracket (cf. Stanghellini et al. 2003).

Finally, Figs. 21 and 22 show the N/O ratios as a function of the O/H
abundances. The conversion of oxygen into nitrogen by the ON cycling in the PN
progenitor stars has been suggested in the literature as an explanation for
the anticorrelation between N/O and O/H in planetary nebulae (cf. Costa et al.
2000, Stasińska et al. 1998, Perinotto et al. 2006). This relation is
approximately valid on the basis of PN data in several galaxies of the Local
Group, as discussed by Richer & McCall (2006). From Figs. 21 and 22, we
conclude that the Magellanic Cloud data support such anticorrelation,
particularly in the case of the SMC. As discussed by Maciel et al. (2006a) the
Milky Way data define a mild anticorrelation, especially in the case of
$\epsilon({\rm O})=\log({\rm O/H})+12>8.0$, which is better defined by the
SMC/LMC.

Acknowledgements. This work was partly supported by FAPESP and CNPq.

## References

  * Bernard-Salas et al. (2008) Bernard-Salas, J., Pottasch, S. R., Gutenkunst, S., Morris, P. W., & Houck, J. R. 2008, ApJ, 672, 274
  * Buzzoni et al. (2006) Buzzoni, A., Arnaboldi, M., & Corradi, R. L. M. 2006, MNRAS, 368, 877
  * Ciardullo (2006) Ciardullo, R. 2006, In: IAU Symposium 234, Eds. M. J. Barlow, R. H. Méndez. (Cambridge: Cambridge University Press), 325
  * Costa et al. (2000) Costa, R. D. D., de Freitas Pacheco, J. A., & Idiart, T. E. P. 2000, A&AS, 145, 467
  * Costa et al. (2008) Costa, R. D. D., Maciel, W. J., & Escudero, A. V. 2008, Baltic Astron. (in press)
  * Cuisinier et al. (2000) Cuisinier, F., Maciel, W. J., Köppen, J., Acker, A., & Stenholm, B., 2000, A&A, 353, 543
  * Escudero et al. (2004) Escudero, A. V., Costa, R. D. D., & Maciel, W. J., 2004, A&A, 414, 211
  * de Freitas Pacheco et al. (1993a) de Freitas Pacheco, J. A., Barbuy, B., Costa, R. D. D., & Idiart, T. E. P. 1993, A&A, 271, 429
  * de Freitas Pacheco et al. (1993b) de Freitas Pacheco, J. A., Costa, R. D. D., & Maciel, W. J. 1993, A&A, 279, 567
  * Henry et al. (2004) Henry, R. B., Kwitter, K. B., & Balick, B. 2004, AJ, 127, 2284
  * Henry et al. (2006) Henry, R. B., Skinner, J. N., Kwitter, K. B., & Milingo, J. B. 2006, In: IAU Symposium 234, Eds. M. J. Barlow, R. H. Méndez. (Cambridge: Cambridge University Press), 417
  * Idiart et al. (2007) Idiart, T. P., Maciel, W. J., & Costa, R. D. D. 2007, A&A, 472, 101
  * Jacoby (2006) Jacoby, G. H. 2006, In: Planetary nebulae beyond the Milky Way, ed. L. Stanghellini, J. R. Walsh, & N. G. Douglas. (Heidelberg: Springer), 17
  * Kwok (2000) Kwok, S. 2000, The origin and evolution of planetary nebulae. (Cambridge: Cambridge University Press)
  * Leisy & Dennefeld (2006) Leisy, P., & Dennefeld, M. 2006, A&A, 456, 451
  * Maciel et al. (2006a) Maciel, W. J., Costa, R. D. D., & Idiart, T. E. P. 2006a, In: Planetary nebulae beyond the Milky Way, ed. L. Stanghellini, J. R. Walsh, & N. G. Douglas. (Heidelberg: Springer), 209
  * Maciel et al. (2006b) Maciel, W. J., Lago, L. G., & Costa, R. D. D., 2006b, A&A, 453, 587
  * Maciel et al. (2008) Maciel, W. J., Costa, R. D. D., & Idiart, T. E. P. 2008, In: IAU Symp. 256, The Magellanic Clouds: stars, gas, and galaxies, Eds. J. Th. van Loon, J. M. Oliveira, (electronic publication)
  * Peimbert (2003) Peimbert, A., 2003, ApJ, 584, 735
  * Perinotto et al. (2006) Perinotto, M., Magrini, L., Mampaso, A., & Corradi, R. L. M. T. E. P. 2006, In: Planetary nebulae beyond the Milky Way, ed. L. Stanghellini, J. R. Walsh, & N. G. Douglas. (Heidelberg: Springer), 232
  * Relaño et al. (2002) Relaño, M., Peimbert, M., & Beckman, J., 2002, ApJ, 564, 704
  * Richer (2006) Richer, M. G. 2006, In: IAU Symposium 234, Eds. M. J. Barlow, R. H. Méndez. (Cambridge: Cambridge University Press), 317
  * Richer & McCall (2006) Richer, M. G., & McCall, M. 2006, In: Planetary nebulae beyond the Milky Way, ed. L. Stanghellini, J. R. Walsh, & N. G. Douglas. (Heidelberg: Springer), 220
  * Shaw (2006) Shaw, R. A. 2006, In: IAU Symposium 234, Eds. M. J. Barlow, R. H. Méndez. (Cambridge: Cambridge University Press), 305
  * Stanghellini (2008) Stanghellini, L. 2008, In: IAU Symposium 256, The Magellanic Clouds: stars, gas, and galaxies, ed. J. van Loon, J. M. Oliveira (Cambridge: Cambridge University Press), in press [astro-ph: 0810.4167]
  * Stanghellini et al. (2003) Stanghellini, L., Shaw, R. A., Balick, B., Mutchler, M., Blades, J. C., & Villaver, E. 2006, ApJ, 596, 1014
  * Stasińska (2004) Stasińska, G. 2004, In: Cosmochemistry: The melting pot of the elements, XIII Canary Islands Winter School of Astrophysics, ed. C. Esteban, R. J. García López, A. Herrero, F. Sánchez (Cambridge: Cambridge University Press), 115
  * Stasińska et al. (1998) Stasińska, G., Richer, M. G., & McCall, M. 1998, A&A, 336, 667


2010597-608Nancy, France 597

Angelo Montanari Gabriele Puppis Pietro Sala Guido Sciavicco

# Decidability of the interval temporal
logic $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ over the natural numbers

A. Montanari  Department of Mathematics and Computer Science, Udine
University, Italy<EMAIL_ADDRESS>,  G. Puppis
Computing Laboratory, Oxford University, England
<EMAIL_ADDRESS>,  P. Sala  and  G. Sciavicco  Department of
Information, Engineering and Communications, Murcia University, Spain
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we focus our attention on the interval temporal logic of the
Allen’s relations “meets”, “begins”, and “begun by”
($A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ for short), interpreted over
natural numbers. We first introduce the logic and we show that it is
expressive enough to model distinctive interval properties, such as
accomplishment conditions, to capture basic modalities of point-based temporal
logic, such as the until operator, and to encode relevant metric constraints.
Then, we prove that the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ over natural numbers is decidable by
providing a small model theorem based on an original contraction method.
Finally, we prove the EXPSPACE-completeness of the problem.

###### Key words and phrases:

interval temporal logics, compass structures, decidability, complexity

###### 1991 Mathematics Subject Classification:

F.3: logics and meaning of programs; F.4: mathematical logic and formal
languages

The work has been partially supported by the GNCS project: “Logics, automata,
and games for the formal verification of complex systems”. Guido Sciavicco has
also been supported by the Spain/South Africa Integrated Action N. HS2008-0006
on: “Metric interval temporal logics: Theory and Applications”.

##  1\. Introduction

Interval temporal logics are modal logics that allow one to represent and to
reason about time intervals. It is well known that, on a linear ordering, one
among thirteen different binary relations may hold between any pair of
intervals, namely, “ends”, “during”, “begins”, “overlaps”, “meets”, “before”,
together with their inverses, and the relation “equals” (the so-called Allen’s
relations [1])111We do not consider here the case of ternary relations.
Amongst the multitude of ternary relations among intervals there is one of
particular importance, which corresponds to the binary operation of
concatenation of meeting intervals. The logic of such a ternary interval
relation has been investigated by Venema in [20]. A systematic analysis of its
fragments has been recently given by Hodkinson et al. [13].. Allen’s relations
give rise to respective unary modal operators, thus defining the modal logic
of time intervals HS introduced by Halpern and Shoham in [12]. Some of these
modal operators are actually definable in terms of others; in particular, if
singleton intervals are included in the structure, it suffices to choose as
basic the modalities corresponding to the relations “begins” $B$ and “ends”
$E$, and their transposes $\,\overline{\\!B\\!}\,$, $\,\overline{\\!E\\!}\,$.
HS turns out to be highly undecidable under very weak assumptions on the class
of interval structures over which its formulas are interpreted [12]. In
particular, undecidability holds for any class of interval structures over
linear orderings that contains at least one linear ordering with an infinite
ascending or descending chain, thus including the natural time flows
$\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$. Undecidability of
HS over finite structures directly follows from results in [15]. In [14],
Lodaya sharpens the undecidability of HS showing that the two modalities $B,E$
suffice for undecidability over dense linear orderings (in fact, the result
applies to the class of all linear orderings [11]). Even though HS is very
natural and the meaning of its operators is quite intuitive, for a long time
such sweeping undecidability results have discouraged the search for practical
applications and further investigations in the field. A renewed interest in
interval temporal logics has been recently stimulated by the identification of
some decidable fragments of HS, whose decidability does not depend on
simplifying semantic assumptions such as locality and homogeneity [11]. This
is the case with the fragments $B\,\overline{\\!B\\!}\,$,
$E\,\overline{\\!E\\!}\,$ (logics of the “begins/begun by” and “ends/ended by”
relations) [11], $A$, $A\,\overline{\\!A\\!}\,$ (logics of temporal
neighborhood, whose modalities capture the “meets/met by” relations [10]), and
$D$, $D\,\overline{\\!D\\!}\,$ (logics of the subinterval/superinterval
relations) [3, 16].

In this paper, we focus our attention on the product logic
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$, obtained from the join of
$B\,\overline{\\!B\\!}\,$ and $A$ (the case of
$\,\overline{\\!A\\!}\,\mspace{-0.3mu}E\,\overline{\\!E\\!}\,$ is fully
symmetric), interpreted over the linear order $\mathbb{N}$ of the natural
numbers (or a finite prefix of it). The decidability of
$B\,\overline{\\!B\\!}\,$ can be proved by translating it into the point-based
propositional temporal logic of linear time with temporal modalities $F$
(sometime in the future) and $P$ (sometime in the past), which has the finite
(pseudo-)model property and is decidable, e.g., [9]. In general, such a
reduction to point-based temporal logics does not work: formulas of interval
temporal logics are evaluated over pairs of points and translate into binary
relations. For instance, this is the case with $A$. Unlike the case of
$B\,\overline{\\!B\\!}\,$, when dealing with $A$ one cannot abstract way from
the left endpoint of intervals, as contradictory formulas may hold over
intervals with the same right endpoint and a different left endpoint. The
decidability of $A\,\overline{\\!A\\!}\,$, and thus that of its fragment $A$,
over various classes of linear orderings has been proved by Bresolin et al. by
reducing its satisfiability problem to that of the two-variable fragment of
first-order logic over the same classes of structures [4], whose decidability
has been proved by Otto in [18]. Optimal tableau methods for $A$ with respect
to various classes of interval structures can be found in [6, 7]. A decidable
metric extension of $A$ over the natural numbers has been proposed in [8]. A
number of undecidable extensions of $A$, and $A\,\overline{\\!A\\!}\,$, have
been given in [2, 5].

$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ retains the simplicity of its
constituents $B\,\overline{\\!B\\!}\,$ and $A$, but it improves a lot on their
expressive power (as we shall show, such an increase in expressiveness is
achieved at the cost of an increase in complexity). First, it allows one to
express assertions that may be true at certain intervals, but at no
subinterval of them, such as the conditions of accomplishment. Moreover, it
makes it possible to easily encode the until operator of point-based temporal
logic (this is possible neither with $B\,\overline{\\!B\\!}\,$ nor with $A$).
Finally, meaningful metric constraints about the length of intervals can be
expressed in $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$, that is, one can
constrain an interval to be at least (resp., at most, exactly) $k$ points
long. We prove the decidability of $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$
interpreted over $\mathbb{N}$ by providing a small model theorem based on an
original contraction method. To prove it, we take advantage of a natural
(equivalent) interpretation of $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$
formulas over grid-like structures based on a bijection between the set of
intervals over $\mathbb{N}$ and (a suitable subset of) the set of points of
the $\mathbb{N}\times\mathbb{N}$ grid. In addition, we prove that the
satisfiability problem for $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ is
EXPSPACE-complete (that for $A$ is NEXPTIME-complete). In the proof of
hardness, we use a reduction from the exponential-corridor tiling problem.

The paper is organized as follows. In Section 2 we introduce
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$. In Section 3, we prove the
decidability of its satisfiability problem. We first describe the application
of the contraction method to finite models and then we generalize it to
infinite ones. In Section 4 we deal with computational complexity issues.
Conclusions provide an assessment of the work and outline future research
directions. Missing proofs can be found in [17].

##  2\. The interval temporal logic $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$

In this section, we briefly introduce syntax and semantics of the logic
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$, which features three modal
operators ${\langle A\rangle}$, ${\langle B\rangle}$, and
${\langle\,\overline{\\!B\\!}\,\rangle}$ corresponding to the three Allen’s
relations $A$ (“meets”), $B$ (“begins”), and $\,\overline{\\!B\\!}\,$ (“begun
by”), respectively. We show that $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ is
expressive enough to capture the notion of accomplishment, to define the
standard until operator of point-based temporal logics, and to encode metric
conditions. Then, we introduce the basic notions of atom, type, and
dependency. We conclude the section by providing an alternative interpretation
of $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ over labeled grid-like
structures.

###  2.1. Syntax and semantics

Given a set $\mathcal{P}\mathit{rop}$ of propositional variables, formulas of
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ are built up from
$\mathcal{P}\mathit{rop}$ using the boolean connectives $\neg$ and $\;\vee\;$
and the unary modal operators ${\langle A\rangle}$, ${\langle B\rangle}$,
${\langle\,\overline{\\!B\\!}\,\rangle}$. As usual, we shall take advantage of
shorthands like
$\varphi_{1}\;\wedge\;\varphi_{2}=\neg(\neg\varphi_{1}\;\vee\;\neg\varphi_{2})$,
$[A]\varphi=\neg{\langle A\rangle}\neg\varphi$, $[B]\varphi=\neg{\langle
B\rangle}\neg\varphi$, $\top=p\vee\neg p$, and $\bot=p\wedge\neg p$, with
$p\in\mathcal{P}\mathit{rop}$. Hereafter, we denote by ${\lvert\varphi\rvert}$
the size of $\varphi$.

We interpret formulas of $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ in interval
temporal structures over natural numbers endowed with the relations “meets”,
“begins”, and “begun by”. Precisely, we identify any given ordinal
$N\leq\omega$ with the prefix of length $N$ of the linear order of the natural
numbers and we accordingly define $\mathbb{I}_{N}$ as the set of all non-
singleton closed intervals $[x,y]$, with $x,y\in N$ and $x<y$. For any pair of
intervals $[x,y],[x^{\prime},y^{\prime}]\in\mathbb{I}_{N}$, the Allen’s
relations “meets” $A$, “begins” $B$, and “begun by” $\,\overline{\\!B\\!}\,$
are defined as follows (note that $\,\overline{\\!B\\!}\,$ is the inverse
relation of $B$):

  * •

“meets” relation: $[x,y]\;A\;[x^{\prime},y^{\prime}]$ iff $y=x^{\prime}$;

  * •

“begins” relation: $[x,y]\;B\;[x^{\prime},y^{\prime}]$ iff $x=x^{\prime}$ and
$y^{\prime}<y$;

  * •

“begun by” relation: $[x,y]\;\,\overline{\\!B\\!}\,\;[x^{\prime},y^{\prime}]$
iff $x=x^{\prime}$ and $y<y^{\prime}$.

Given an _interval structure_
$\mathcal{S}=(\mathbb{I}_{N},A,B,\,\overline{\\!B\\!}\,,\sigma)$, where
$\sigma:\mathbb{I}_{N}\;\rightarrow\;\mathscr{P}(\mathcal{P}\mathit{rop})$ is
a labeling function that maps intervals in $\mathbb{I}_{N}$ to sets of
propositional variables, and an initial interval $I$, we define the semantics
of an $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ formula as follows:

  * •

$\mathcal{S},I\vDash a$ iff $a\in\sigma(I)$, for any
$a\in\mathcal{P}\mathit{rop}$;

  * •

$\mathcal{S},I\vDash\neg\varphi$ iff $\mathcal{S},I\not\vDash\varphi$;

  * •

$\mathcal{S},I\vDash\varphi_{1}\;\vee\;\varphi_{2}$ iff
$\mathcal{S},I\vDash\varphi_{1}$ or $\mathcal{S},I\vDash\varphi_{2}$;

  * •

for every relation $R\in\\{A,B,\,\overline{\\!B\\!}\,\\}$,
$\mathcal{S},I\vDash{\langle R\rangle}\varphi$ iff there is an interval
$J\in\mathbb{I}_{N}$ such that $I\;R\;J$ and $\mathcal{S},J\vDash\varphi$.

Given an interval structure $\mathcal{S}$ and a formula $\varphi$, we say that
$\mathcal{S}$ _satisfies_ $\varphi$ if there is an interval $I$ in
$\mathcal{S}$ such that $\mathcal{S},I\vDash\varphi$. We say that $\varphi$ is
_satisfiable_ if there exists an interval structure that satisfies it. We
define the _satisfiability problem_ for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ as the problem of establishing
whether a given $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$-formula $\varphi$ is
satisfiable.

We conclude the section with some examples that account for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ expressive power. The first one
shows how to encode in $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ conditions of
accomplishment (think of formula $\varphi$ as the assertion: “Mr. Jones flew
from Venice to Nancy”): ${\langle
A\rangle}\bigl{(}\varphi\;\wedge\;[B](\neg\varphi\;\wedge\;[A]\neg\varphi)\;\wedge\;[\,\overline{\\!B\\!}\,]\neg\varphi\bigr{)}$.
Formulas of point-based temporal logics of the form $\psi\;U\;\varphi$, using
the standard until operator, can be encoded in
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ (where atomic intervals are two-
point intervals) as follows: ${\langle
A\rangle}\bigl{(}[B]\bot\\!\;\wedge\;\\!\varphi\bigr{)}\;\vee\;{\langle
A\rangle}\bigl{(}{\langle
A\rangle}([B]\bot\\!\;\wedge\;\\!\varphi)\;\wedge\;[B]({\langle
A\rangle}([B]\bot\\!\;\wedge\;\\!\psi))\bigr{)}.$ Finally, metric conditions
like: “$\varphi$ holds over a right neighbor interval of length greater than
$k$ (resp., less than $k$, equal to $k$)” can be captured by the following
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ formula: ${\langle
A\rangle}\bigl{(}\varphi\;\wedge\;{\langle B\rangle}^{k}\top\bigr{)}$ (resp.,
${\langle A\rangle}\bigl{(}\varphi\;\wedge\;[B]^{k-1}\bot\bigr{)}$, ${\langle
A\rangle}\bigl{(}\varphi\;\wedge\;[B]^{k}\bot\;\wedge\;{\langle
B\rangle}^{k-1}\top\bigr{)}$)222It is not difficult to show that
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ subsumes the metric extension of $A$
given in [8]. A simple game-theoretic argument shows that the former is in
fact strictly more expressive than the latter..

###  2.2. Atoms, types, and dependencies

Let $\mathcal{S}=(\mathbb{I}_{N},A,B,\,\overline{\\!B\\!}\,,\sigma)$ be an
interval structure and $\varphi$ be a formula of
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$. In the sequel, we shall compare
intervals in $\mathcal{S}$ with respect to the set of subformulas of $\varphi$
they satisfy. To do that, we introduce the key notions of $\varphi$-atom,
$\varphi$-type, $\varphi$-cluster, and $\varphi$-shading.

First of all, we define the _closure_ $\mathcal{C}\mathit{l}(\varphi)$ of
$\varphi$ as the set of all subformulas of $\varphi$ and of their negations
(we identify $\neg\neg\alpha$ with $\alpha$, $\neg{\langle A\rangle}\alpha$
with $[A]\neg\alpha$, etc.). For technical reasons, we also introduce the
_extended closure_ $\mathcal{C}\mathit{l}^{+}(\varphi)$, which is defined as
the set of all formulas in $\mathcal{C}\mathit{l}(\varphi)$ plus all formulas
of the forms ${\langle R\rangle}\alpha$ and $\neg{\langle R\rangle}\alpha$,
with $R\in\\{A,B,\,\overline{\\!B\\!}\,\\}$ and
$\alpha\in\mathcal{C}\mathit{l}(\varphi)$.

A _$\varphi$ -atom_ is any non-empty set
$F\subseteq\mathcal{C}\mathit{l}^{+}(\varphi)$ such that (i) for every
$\alpha\in\mathcal{C}\mathit{l}^{+}(\varphi)$, we have $\alpha\in F$ iff
$\neg\alpha\not\in F$ and (ii) for every
$\gamma=\alpha\;\vee\;\beta\in\mathcal{C}\mathit{l}^{+}(\varphi)$, we have
$\gamma\in F$ iff $\alpha\in F$ or $\beta\in F$ (intuitively, a _$\varphi$
-atom_ is a maximal locally consistent set of formulas chosen from
$\mathcal{C}\mathit{l}^{+}(\varphi)$). Note that the cardinalities of both
sets $\mathcal{C}\mathit{l}(\varphi)$ and $\mathcal{C}\mathit{l}^{+}(\varphi)$
are linear in the number ${\lvert\varphi\rvert}$ of subformulas of $\varphi$,
while the number of $\varphi$-atoms is at most exponential in
${\lvert\varphi\rvert}$ (precisely, we have
${\lvert\mathcal{C}\mathit{l}(\varphi)\rvert}=2{\lvert\varphi\rvert}$,
${\lvert\mathcal{C}\mathit{l}^{+}(\varphi)\rvert}=14{\lvert\varphi\rvert}$,
and there are at most $2^{7{\lvert\varphi\rvert}}$ distinct atoms).

We also associate with each interval $I\in\mathcal{S}$ the set of all formulas
$\alpha\in\mathcal{C}\mathit{l}^{+}(\varphi)$ such that
$\mathcal{S},I\vDash\alpha$. Such a set is called _$\varphi$ -type_ of $I$ and
it is denoted by $\mathcal{T}\mathit{ype}_{\mathcal{S}}(I)$. We have that
every $\varphi$-type is a $\varphi$-atom, but not vice versa. Hereafter, we
shall omit the argument $\varphi$, thus calling a $\varphi$-atom (resp., a
$\varphi$-type) simply an atom (resp., a type).

Given an atom $F$, we denote by $\mathcal{O}\mathit{bs}(F)$ the set of all
_observables_ of $F$, namely, the formulas
$\alpha\in\mathcal{C}\mathit{l}(\varphi)$ such that $\alpha\in F$. Similarly,
given an atom $F$ and a relation $R\in\\{A,B,\,\overline{\\!B\\!}\,\\}$, we
denote by $\mathcal{R}\mathit{eq}_{R}(F)$ the set of all _$R$ -requests_ of
$F$, namely, the formulas $\alpha\in\mathcal{C}\mathit{l}(\varphi)$ such that
${\langle R\rangle}\alpha\in F$. Taking advantage of the above sets, we can
define the following two relations between atoms $F$ and $G$:

$\begin{array}[]{rcl}F\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$}}\,G&\;\quad\text{iff}&\mathcal{R}\mathit{eq}_{A}(F)\;=\;\mathcal{O}\mathit{bs}(G)\,\cup\,\mathcal{R}\mathit{eq}_{B}(G)\,\cup\,\mathcal{R}\mathit{eq}_{\,\overline{\\!B\\!}\,}(G);\vspace{2mm}\\\
F\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,G&\;\quad\text{iff}&\begin{cases}\mathcal{O}\mathit{bs}(F)\,\cup\,\mathcal{R}\mathit{eq}_{\,\overline{\\!B\\!}\,}(F)\;\subseteq\;\mathcal{R}\mathit{eq}_{\,\overline{\\!B\\!}\,}(G)\;\subseteq\;\mathcal{O}\mathit{bs}(F)\,\cup\,\mathcal{R}\mathit{eq}_{\,\overline{\\!B\\!}\,}(F)\,\cup\,\mathcal{R}\mathit{eq}_{B}(F),\vspace{1mm}\\\
\mathcal{O}\mathit{bs}(G)\,\cup\,\mathcal{R}\mathit{eq}_{B}(G)\;\subseteq\;\mathcal{R}\mathit{eq}_{B}(F)\;\subseteq\;\mathcal{O}\mathit{bs}(G)\,\cup\,\mathcal{R}\mathit{eq}_{B}(G)\,\cup\,\mathcal{R}\mathit{eq}_{\,\overline{\\!B\\!}\,}(G).\end{cases}\end{array}$

Note that the relation
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$
is transitive, while
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$
is not. Moreover, both
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$
and
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$
satisfy a _view-to-type dependency_ , namely, for every pair of intervals
$I,J$ in $\mathcal{S}$, we have that

$\begin{array}[]{rcl}I\;A\;J&\;\quad\text{implies}&\mathcal{T}\mathit{ype}_{\mathcal{S}}(I)\,\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$}}\,{}\,\mathcal{T}\mathit{ype}_{\mathcal{S}}(J)\vspace{1mm}\\\
I\;B\;J&\;\quad\text{implies}&\mathcal{T}\mathit{ype}_{\mathcal{S}}(I)\,\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,{}\,\mathcal{T}\mathit{ype}_{\mathcal{S}}(J).\end{array}$

Relations
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$
and
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$
will come into play in the definition of consistency conditions (see
Definition 2.1).

###  2.3. Compass structures

Figure 1. Correspondence between intervals and points of a discrete grid.

The logic $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ can be equivalently
interpreted over grid-like structures (the so-called compass structures [20])
by exploiting the existence of a natural bijection between the intervals
$I=[x,y]$ and the points $p=(x,y)$ of an $N\times N$ grid such that $x<y$. As
an example, Figure 1 depicts four intervals $I_{0},...,I_{3}$ such that
$I_{0}\;A\;I_{1}$, $I_{0}\;B\;I_{2}$, and
$I_{0}\;\,\overline{\\!B\\!}\,\;I_{3}$, together with the corresponding points
$p_{0},...,p_{3}$ of a discrete grid (note that the three Allen’s relations
$A,B,\,\overline{\\!B\\!}\,$ between intervals are mapped to corresponding
spatial relations between points; for the sake of readability, we name the
latter ones as the former ones).

######  Definition 2.1.

Given an $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ formula $\varphi$, a
(consistent and fulfilling) _compass_ ($\varphi$-)_structure_ of length
$N\leq\omega$ is a pair $\mathcal{G}=(\mathbb{P}_{N},\mathcal{L})$, where
$\mathbb{P}_{N}$ is the set of points $p=(x,y)$, with $0\leq x<y<N$, and
$\mathcal{L}$ is function that maps any point $p\in\mathbb{P}_{N}$ to a
($\varphi$-)atom $\mathcal{L}(p)$ in such a way that

  * •

for every pair of points $p,q\in\mathbb{P}_{N}$ and every relation
$R\in\\{A,B\\}$, if $p\;R\;q$ holds, then
$\mathcal{L}(p)\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{R\,}$}}}{\longrightarrow}$}}\,\mathcal{L}(q)$
follows (consistency);

  * •

for every point $p\in\mathbb{P}_{N}$, every relation
$R\in\\{A,B,\,\overline{\\!B\\!}\,\\}$, and every formula
$\alpha\in\mathcal{R}\mathit{eq}_{R}\bigl{(}\mathcal{L}(p)\bigr{)}$, there is
a point $q\in\mathbb{P}_{N}$ such that $p\;R\;q$ and
$\alpha\in\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}(q)\bigr{)}$ (fulfillment).

We say that a compass ($\varphi$-)structure
$\mathcal{G}=(\mathbb{P}_{N},\mathcal{L})$ _features_ a formula $\alpha$ if
there is a point $p\in\mathbb{P}_{N}$ such that $\alpha\in\mathcal{L}(p)$. The
following proposition implies that the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ is reducible to the problem of
deciding, for any given formula $\varphi$, whether there exists a
$\varphi$-compass structure that features $\varphi$.

######  Proposition 2.2.

An $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$-formula $\varphi$ is satisfied by
some interval structure if and only if it is featured by some
($\varphi$-)compass structure.

##  3\. Deciding the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$

In this section, we prove that the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ is decidable by providing a “small-
model theorem” for the satisfiable formulas of the logic. For the sake of
simplicity, we first show that the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ interpreted over finite interval
structures is decidable and then we generalize such a result to all (finite or
infinite) interval structures.

As a preliminary step, we introduce the key notion of shading. Let
$\mathcal{G}=(\mathbb{P}_{N},\mathcal{L})$ be a compass structure of length
$N\leq\omega$ and let $0\leq y<N$. The _shading of the row $y$ of
$\mathcal{G}$_ is the set
$\mathcal{S}\mathit{hading}_{\mathcal{G}}(y)=\bigl{\\{}\mathcal{L}(x,y)\,:\,0\leq
x<y\bigr{\\}}$, namely, the set of the atoms of all points in $\mathbb{P}_{N}$
whose vertical coordinate has value $y$ (basically, we interpret different
atoms as different colors). Clearly, for every pair of atoms $F$ and
$F^{\prime}$ in $\mathcal{S}\mathit{hading}_{\mathcal{G}}(y)$, we have
$\mathcal{R}\mathit{eq}_{A}(F)=\mathcal{R}\mathit{eq}_{A}(F^{\prime})$.

###  3.1. A small-model theorem for finite structures

Let $\varphi$ be an $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ formula. Let us
assume that $\varphi$ is featured by a finite compass structure
$\mathcal{G}=(\mathbb{P}_{N},\mathcal{L})$, with $N<\omega$. In fact, without
loss of generality, we can assume that $\varphi$ belongs to the atom
associated with a point $p=(0,y)$ of $\mathcal{G}$, with $0<y<N$. We prove
that we can restrict our attention to compass structures
$\mathcal{G}=(\mathbb{P}_{N},\mathcal{L})$, where $N$ is bounded by a double
exponential in ${\lvert\varphi\rvert}$. We start with the following lemma that
proves a simple, but crucial, property of the relations
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$
and
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$
(the proof can be found in [17]).

######  Lemma 3.1.

If
$F\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$}}\,H$
and
$G\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,H$
hold for some atoms $F,G,H$, then
$F\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$}}\,G$
holds as well.

The next lemma shows that, under suitable conditions, a given compass
structure $\mathcal{G}$ may be reduced in length, preserving the existence of
atoms featuring $\varphi$.

######  Lemma 3.2.

Let $\mathcal{G}$ be a compass structure featuring $\varphi$. If there exist
two rows $0<y_{0}<y_{1}<N$ in $\mathcal{G}$ such that
$\mathcal{S}\mathit{hading}_{\mathcal{G}}(y_{0})\subseteq\mathcal{S}\mathit{hading}_{\mathcal{G}}(y_{1})$,
then there exists a compass structure $\mathcal{G}^{\prime}$ of length
$N^{\prime}<N$ that features $\varphi$.

Figure 2. Contraction $\mathcal{G}^{\prime}$ of a compass structure
$\mathcal{G}$.

######  Proof 3.3.

Suppose that $0<y_{0}<y_{1}<N$ are two rows of $\mathcal{G}$ such that
$\mathcal{S}\mathit{hading}_{\mathcal{G}}(y_{0})\subseteq\mathcal{S}\mathit{hading}_{\mathcal{G}}(y_{1})$.
Then, there is a function
$f:\\{0,...,y_{0}-1\\}\;\rightarrow\;\\{0,...,y_{1}-1\\}$ such that, for every
$0\leq x<y_{0}$, $\mathcal{L}(x,y_{0})=\mathcal{L}(f(x),y_{1})$. Let
$k=y_{1}-y_{0}$, $N^{\prime}=N-k$ ($<N$), and $\mathbb{P}_{N^{\prime}}$ be the
portion of the grid that consists of all points $p=(x,y)$, with $0\leq
x<y<N^{\prime}$. We extend $f$ to a function that maps points in
$\mathbb{P}_{N^{\prime}}$ to points in $\mathbb{P}_{N}$ as follows:

  * •

if $p=(x,y)$, with $0\leq x<y<y_{0}$, then we simply let $f(p)=p$;

  * •

if $p=(x,y)$, with $0\leq x<y_{0}\leq y$, then we let $f(p)=(f(x),y+k)$;

  * •

if $p=(x,y)$, with $y_{0}\leq x<y$, then we let $f(p)=(x+k,y+k)$.

We denote by $\mathcal{L}^{\prime}$ the labeling of $\mathbb{P}_{N^{\prime}}$
such that, for every point $p\in\mathbb{P}_{N^{\prime}}$,
$\mathcal{L}^{\prime}(p)=\mathcal{L}(f(p))$ and we denote by
$\mathcal{G}^{\prime}$ the resulting structure
$(\mathbb{P}_{N^{\prime}},\mathcal{L}^{\prime})$ (see Figure 2). We have to
prove that $\mathcal{G}^{\prime}$ is a consistent and fulfilling compass
structure that features $\varphi$ (see Definition 2.1). First, we show that
$\mathcal{G}^{\prime}$ satisfies the consistency conditions for the relations
$B$ and $A$; then we show that $\mathcal{G}^{\prime}$ satisfies the
fulfillment conditions for the $\,\overline{\\!B\\!}\,$-, $B$-, and
$A$-requests; finally, we show that $\mathcal{G}^{\prime}$ features $\varphi$.

Consistency with relation $B$.  Consider two points $p=(x,y)$ and
$p^{\prime}=(x^{\prime},y^{\prime})$ in $\mathcal{G}^{\prime}$ such that
$p\;B\;p^{\prime}$, i.e., $0\leq x=x^{\prime}<y^{\prime}<y<N^{\prime}$. We
prove that
$\mathcal{L}^{\prime}(p)\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,\mathcal{L}^{\prime}(p^{\prime})$
by distinguishing among the following three cases (note that exactly one of
such cases holds):

  1. (1)

$y<y_{0}$ and $y^{\prime}<y_{0}$,

  2. (2)

$y\geq y_{0}$ and $y^{\prime}\geq y_{0}$,

  3. (3)

$y\geq y_{0}$ and $y^{\prime}<y_{0}$.

If $y<y_{0}$ and $y^{\prime}<y_{0}$, then, by construction, we have $f(p)=p$
and $f(p^{\prime})=p^{\prime}$. Since $\mathcal{G}$ is a (consistent) compass
structure, we immediately obtain
$\mathcal{L}^{\prime}(p)=\mathcal{L}(p)\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,\mathcal{L}(p^{\prime})=\mathcal{L}^{\prime}(p^{\prime})$.

If $y\geq y_{0}$ and $y\geq y_{0}$, then, by construction, we have either
$f(p)=(f(x),y+k)$ or $f(p)=(x+k,y+k)$, depending on whether $x<y_{0}$ or
$x\geq y_{0}$. Similarly, we have either
$f(p^{\prime})=(f(x^{\prime}),y^{\prime}+k)=(f(x),y^{\prime}+k)$ or
$f(p^{\prime})=(x^{\prime}+k,y^{\prime}+k)=(x+k,y^{\prime}+k)$. This implies
$f(p)\;B\;f(p^{\prime})$ and thus, since $\mathcal{G}$ is a (consistent)
compass structure, we have $\mathcal{L}^{\prime}(p)=\mathcal{L}(f(p))$
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$
$\mathcal{L}(f(p^{\prime}))=\mathcal{L}^{\prime}(p^{\prime})$.

If $y\geq y_{0}$ and $y^{\prime}<y_{0}$, then, since $x<y^{\prime}<y_{0}$, we
have by construction $f(p)=(f(x),y+k)$ and $f(p^{\prime})=p^{\prime}$.
Moreover, if we consider the point $p^{\prime\prime}=(x,y_{0})$ in
$\mathcal{G}^{\prime}$, we easily see that (i)
$f(p^{\prime\prime})=(f(x),y_{1})$, (ii) $f(p)\;B\;f(p^{\prime\prime})$
(whence
$\mathcal{L}(f(p))\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,\mathcal{L}(f(p^{\prime\prime}))$),
(iii) $\mathcal{L}(f(p^{\prime\prime}))=\mathcal{L}(p^{\prime\prime})$, and
(iv) $p^{\prime\prime}\;B\;p^{\prime}$ (whence
$\mathcal{L}(p^{\prime\prime})\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,\mathcal{L}(p^{\prime})$).
It thus follows that
$\mathcal{L}^{\prime}(p)=\mathcal{L}(f(p))\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,\mathcal{L}(f(p^{\prime\prime}))$
$=\mathcal{L}(p^{\prime\prime})$
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$
$\mathcal{L}(p^{\prime})=\mathcal{L}(f(p^{\prime}))=\mathcal{L}^{\prime}(p^{\prime})$.
Finally, by exploiting the transitivity of the relation
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$
, we obtain
$\mathcal{L}^{\prime}(p)\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,\mathcal{L}^{\prime}(p^{\prime})$.

Consistency with relation $A$.  Consider two points $p=(x,y)$ and
$p^{\prime}=(x^{\prime},y^{\prime})$ such that $p\;A\;p^{\prime}$, i.e.,
$0\leq x<y=x^{\prime}<y^{\prime}<N^{\prime}$. We define
$p^{\prime\prime}=(y,y+1)$ in such a way that $p\;A\;p^{\prime\prime}$ and
$p^{\prime}\;B\;p^{\prime\prime}$ and we distinguish between the following two
cases:

  1. (1)

$y\geq y_{0}$,

  2. (2)

$y<y_{0}$.

If $y\geq y_{0}$, then, by construction, we have
$f(p)\;A\;f(p^{\prime\prime})$. Since $\mathcal{G}$ is a (consistent) compass
structure, it follows that $\mathcal{L}^{\prime}(p)=\mathcal{L}(f(p))$
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$
$\mathcal{L}(f(p^{\prime\prime}))=\mathcal{L}^{\prime}(p^{\prime\prime})$.

If $y<y_{0}$, then, by construction, we have
$\mathcal{L}(p^{\prime\prime})=\mathcal{L}(f(p^{\prime\prime}))$. Again, since
$\mathcal{G}$ is a (consistent) compass structure, it follows that
$\mathcal{L}^{\prime}(p)=\mathcal{L}(f(p))=\mathcal{L}(p)$
$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$
$\mathcal{L}(p^{\prime\prime})=\mathcal{L}(f(p^{\prime\prime}))=\mathcal{L}^{\prime}(p^{\prime\prime})$.

In both cases we have
$\mathcal{L}^{\prime}(p)\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$}}\,\mathcal{L}^{\prime}(p^{\prime\prime})$.
Now, we recall that $p^{\prime}\;B\;p^{\prime\prime}$ and that, by previous
arguments, $\mathcal{G}^{\prime}$ is consistent with the relation $B$. We thus
have
$\mathcal{L}^{\prime}(p^{\prime})\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{B\,}$}}}{\longrightarrow}$}}\,\mathcal{L}^{\prime}(p^{\prime\prime})$.
Finally, by applying Lemma 3.1, we obtain
$\mathcal{L}^{\prime}(p)\,\text{\raisebox{-0.86108pt}{$\overset{\text{\raisebox{-0.43057pt}[0.0pt][-0.43057pt]{${}_{A\,}$}}}{\longrightarrow}$}}\,\mathcal{L}^{\prime}(p^{\prime})$.

Fulfillment of $B$-requests.  Consider a point $p=(x,y)$ in
$\mathcal{G}^{\prime}$ and some $B$-request
$\alpha\in\mathcal{R}\mathit{eq}_{B}\bigl{(}\mathcal{L}^{\prime}(p)\bigr{)}$
associated with it. Since, by construction,
$\alpha\in\mathcal{R}\mathit{eq}_{B}\bigl{(}\mathcal{L}(f(p))\bigr{)}$ and
$\mathcal{G}$ is a (fulfilling) compass structure, we know that $\mathcal{G}$
contains a point $q^{\prime}=(x^{\prime},y^{\prime})$ such that
$f(p)\;B\;q^{\prime}$ and
$\alpha\in\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}(q^{\prime})\bigr{)}$. We
prove that $\mathcal{G}^{\prime}$ contains a point $p^{\prime}$ such that
$p\;B\;p^{\prime}$ and
$\alpha\in\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}^{\prime}(p^{\prime})\bigr{)}$
by distinguishing among the following three cases (note that exactly one of
such cases holds):

  1. (1)

$y<y_{0}$

  2. (2)

$y^{\prime}\geq y_{1}$,

  3. (3)

$y\geq y_{0}$ and $y^{\prime}<y_{1}$.

If $y<y_{0}$, then, by construction, we have $p=f(p)$ and
$q^{\prime}=f(q^{\prime})$. Therefore, we simply define
$p^{\prime}=q^{\prime}$ in such a way that $p=f(p)\;B\;q^{\prime}=p^{\prime}$
and
$\alpha\in\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}^{\prime}(p^{\prime})\bigr{)}$
($=\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}(f(p^{\prime}))\bigr{)}=\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}(q^{\prime})\bigr{)}$).

If $y^{\prime}\geq y_{1}$, then, by construction, we have either
$f(p)=(f(x),y+k)$ or $f(p)=(x+k,y+k)$, depending on whether $x<y_{0}$ or
$x\geq y_{0}$. We define $p^{\prime}=(x,y^{\prime}-k)$ in such a way that
$p\;B\;p^{\prime}$. Moreover, we observe that either
$f(p^{\prime})=(f(x),y^{\prime})$ or $f(p^{\prime})=(x+k,y^{\prime})$,
depending on whether $x<y_{0}$ or $x\geq y_{0}$, and in both cases
$f(p^{\prime})=q^{\prime}$ follows. This shows that
$\alpha\in\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}^{\prime}(p^{\prime})\bigr{)}$
($=\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}(f(p^{\prime})\bigr{)}=\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}(q^{\prime})\bigr{)}$).

If $y\geq y_{0}$ and $y^{\prime}<y_{1}$, then we define
$\,\overline{\\!p\\!}\,=(x,y_{0})$ and
$\,\overline{\\!q\\!}\,=(x^{\prime},y_{1})$ and we observe that
$f(p)\;B\;\,\overline{\\!q\\!}\,$, $\,\overline{\\!q\\!}\,\;B\;q^{\prime}$,
and $f(\,\overline{\\!p\\!}\,)=\,\overline{\\!q\\!}\,$. From
$f(p)\;B\;\,\overline{\\!q\\!}\,$ and $\,\overline{\\!q\\!}\,\;B\;q^{\prime}$,
it follows that
$\alpha\in\mathcal{R}\mathit{eq}_{B}\bigl{(}\mathcal{L}(\,\overline{\\!q\\!}\,)\bigr{)}$
and hence
$\alpha\in\mathcal{R}\mathit{eq}_{B}\bigl{(}\mathcal{L}(\,\overline{\\!p\\!}\,)\bigr{)}$.
Since $\mathcal{G}$ is a (fulfilling) compass structure, we know that there is
a point $p^{\prime}$ such that $\,\overline{\\!p\\!}\,\;B\;p^{\prime}$ and
$\alpha\in\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}(\,\overline{\\!p\\!}\,^{\prime})\bigr{)}$.
Moreover, since $\,\overline{\\!p\\!}\,\;B\;p^{\prime}$, we have
$f(p^{\prime})=p^{\prime}$, from which we obtain $p\;B\;p^{\prime}$ and
$\alpha\in\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}(p^{\prime})\bigr{)}$.

Fulfillment of $\,\overline{\\!B\\!}\,$-requests.  The proof that
$\mathcal{G}^{\prime}$ fulfills all $\,\overline{\\!B\\!}\,$-requests of its
atoms is symmetric with respect to the previous one.

Fulfillment of $A$-requests.  Consider a point $p=(x,y)$ in
$\mathcal{G}^{\prime}$ and some $A$-request
$\alpha\in\mathcal{R}\mathit{eq}_{A}\bigl{(}\mathcal{L}^{\prime}(p)\bigr{)}$
associated with $p$ in $\mathcal{G}^{\prime}$. Since, by previous arguments,
$\mathcal{G}^{\prime}$ fulfills all $\,\overline{\\!B\\!}\,$-requests of its
atoms, it is sufficient to prove that either
$\alpha\in\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}^{\prime}(p^{\prime})\bigr{)}$
or
$\alpha\in\mathcal{R}\mathit{eq}_{\,\overline{\\!B\\!}\,}\bigl{(}\mathcal{L}^{\prime}(p^{\prime})\bigr{)}$,
where $p^{\prime}=(y,y+1)$. This can be easily proved by distinguishing among
the three cases $y<y_{0}-1$, $y=y_{0}-1$, and $y\geq y_{0}$.

Featured formulas.  Recall that, by previous assumptions, $\mathcal{G}$
contains a point $p=(0,y)$, with $0<y<N$, such that
$\varphi\in\mathcal{L}(p)$. If $y\leq y_{0}$, then, by construction, we have
$\varphi\in\mathcal{L}^{\prime}(p)$ ($=\mathcal{L}(f(p))=\mathcal{L}(p)$).
Otherwise, if $y>y_{0}$, we define $q=(0,y_{0})$ and we observe that
$q\;\,\overline{\\!B\\!}\,\;p$. Since $\mathcal{G}$ is a (consistent) compass
structure and
${\langle\,\overline{\\!B\\!}\,\rangle}\varphi\in\mathcal{C}\mathit{l}^{+}(\varphi)$,
we have that
$\varphi\in\mathcal{R}\mathit{eq}_{\,\overline{\\!B\\!}\,}\bigl{(}\mathcal{L}(q)\bigr{)}$.
Moreover, by construction, we have $\mathcal{L}^{\prime}(q)=\mathcal{L}(f(q))$
and hence
$\varphi\in\mathcal{R}\mathit{eq}_{\,\overline{\\!B\\!}\,}\bigl{(}\mathcal{L}^{\prime}(q)\bigr{)}$.
Finally, since $\mathcal{G}^{\prime}$ is a (fulfilling) compass structure, we
know that there is a point $p^{\prime}$ in $\mathcal{G}^{\prime}$ such that
$f(q)\;\,\overline{\\!B\\!}\,\;p^{\prime}$ and
$\varphi\in\mathcal{O}\mathit{bs}\bigl{(}\mathcal{L}^{\prime}(p^{\prime})\bigr{)}$.

On the grounds of the above result, we can provide a suitable upper bound for
the length of a minimal finite interval structure that satisfies $\varphi$, if
there exists any. This yields a straightforward, but inefficient, 2EXPSPACE
algorithm that decides whether a given
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$-formula $\varphi$ is satisfiable
over finite interval structures.

######  Theorem 3.4.

An $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$-formula $\varphi$ is satisfied by
some finite interval structure iff it is featured by some compass structure of
length $N\leq 2^{2^{7{\lvert\varphi\rvert}}}$ (i.e., double exponential in
${\lvert\varphi\rvert}$).

######  Proof 3.5.

One direction is trivial. We prove the other one (“only if” part). Suppose
that $\varphi$ is satisfied by a finite interval structure $\mathcal{S}$. By
Proposition 2.2, there is a compass structure $\mathcal{G}$ that features
$\varphi$ and has finite length $N<\omega$. Without loss of generality, we can
assume that $N$ is minimal among all finite compass structures that feature
$\varphi$. We recall from Section 2.2 that $\mathcal{G}$ contains at most
$2^{7{\lvert\varphi\rvert}}$ distinct atoms. This implies that there exist at
most $2^{2^{7{\lvert\varphi\rvert}}}$ different shadings of the form
$\mathcal{S}\mathit{hading}_{\mathcal{G}}(y)$, with $0\leq y<N$. Finally, by
applying Lemma 3.2, we obtain $N\leq 2^{2^{7{\lvert\varphi\rvert}}}$
(otherwise, there would exist two rows $0<y_{0}<y_{1}<N$ such that
$\mathcal{S}\mathit{hading}_{\mathcal{G}}(y_{0})=\mathcal{S}\mathit{hading}_{\mathcal{G}}(y_{1})$,
which is against the hypothesis of minimality of $N$).

###  3.2. A small-model theorem for infinite structures

In general, compass structures that feature $\varphi$ may be infinite. Here,
we prove that, without loss of generality, we can restrict our attention to
sufficiently “regular” infinite compass structures, which can be represented
in double exponential space with respect to ${\lvert\varphi\rvert}$. To do
that, we introduce the notion of periodic compass structure.

######  Definition 3.6.

An infinite compass structure $\mathcal{G}=(\mathbb{P}_{\omega},\mathcal{L})$
is _periodic_ , with _threshold_ $\widetilde{y}_{0}$, _period_
$\widetilde{y}$, and _binding_
$\widetilde{g}:\\{0,...,\widetilde{y}_{0}+\widetilde{y}-1\\}\;\rightarrow\;\\{0,...,\widetilde{y}_{0}-1\\}$,
if the following conditions are satisfied:

  * •

for every $\widetilde{y}_{0}+\widetilde{y}\leq x<y$, we have
$\mathcal{L}(x,y)=\mathcal{L}(x-\widetilde{y},y-\widetilde{y})$,

  * •

for every $0\leq x<\widetilde{y}_{0}+\widetilde{y}\leq y$, we have
$\mathcal{L}(x,y)=\mathcal{L}(\widetilde{g}(x),y-\widetilde{y})$.

Figure 3 gives an example of a periodic compass structure (the arrows
represent some relationships between points induced by the binding function
$\widetilde{g}$). Note that any periodic compass structure
$\mathcal{G}=(\mathbb{P}_{\omega},\mathcal{L})$ can be finitely represented by
specifying (i) its threshold $\widetilde{y}_{0}$, (ii) its period
$\widetilde{y}$, (iii) its binding $\widetilde{g}$, and (iv) the labeling
$\mathcal{L}$ restricted to the portion
$\mathbb{P}_{\widetilde{y}_{0}+\widetilde{y}-1}$ of the domain.

Figure 3. A periodic compass structure with threshold $\widetilde{y}_{0}$,
period $\widetilde{y}$, and binding $\widetilde{g}$.

The following theorem leads immediately to a 2EXPSPACE algorithm that decides
whether a given $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$-formula $\varphi$ is
satisfiable over infinite interval structures (the proof is provided in [17]).

######  Theorem 3.7.

An $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$-formula $\varphi$ is satisfied by
an infinite interval structure iff it is featured by a periodic compass
structure with threshold $\widetilde{y}_{0}<2^{2^{7{\lvert\varphi\rvert}}}$
and period $\widetilde{y}<2{\lvert\varphi\rvert}\cdot
2^{2^{7{\lvert\varphi\rvert}}}\cdot 2^{2^{7{\lvert\varphi\rvert}}}$.

##  4\. Tight complexity bounds to the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$

In this section, we show that the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ interpreted over (either finite or
infinite) interval temporal structures is EXPSPACE-complete.

The EXPSPACE-hardness of the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ follows from a reduction from the
_exponential-corridor tiling problem_ , which is known to be EXPSPACE-complete
[19]. Formally, an instance of the exponential-corridor tiling problem is a
tuple $\mathcal{T}=(T,t_{\bot},t_{\top},H,$ $V,n)$ consisting of a finite set
$T$ of tiles, a bottom tile $t_{\bot}\in T$, a top tile $t_{\top}\in T$, two
binary relations $H,V$ over $T$ (specifying the horizontal and vertical
constraints), and a positive natural number $n$ (represented in unary
notation). The problem consists in deciding whether there exists a tiling
$f:\mathbb{N}\times\\{0,...,2^{n}-1\\}\;\rightarrow\;T$ of the infinite
discrete corridor of height $2^{n}$, that associates the tile $t_{\bot}$
(resp., $t_{\top}$) with the bottom (resp., top) row of the corridor and that
respects the horizontal and vertical constraints $H$ and $V$, namely,

  1. i)

for every $x\in\mathbb{N}$, we have $f(x,0)=t_{\bot}$,

  2. ii)

for every $x\in\mathbb{N}$, we have $f(x,2^{n}-1)=t_{\top}$,

  3. iii)

for every $x\in\mathbb{N}$ and every $0\leq y<2^{n}$, we have
$f(x,y)\;H\;f(x+1,y)$,

  4. iv)

for every $x\in\mathbb{N}$ and every $0\leq y<2^{n}-1$, we have
$f(x,y)\;V\;f(x,y+1)$.

The proof of the following lemma, which reduces the exponential-corridor
tiling problem to the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$, can be found in [17]. Intuitively,
such a reduction exploits (i) the correspondence between the points $p=(x,y)$
inside the infinite corridor $\mathbb{N}\times\\{0,...,2^{n}-1\\}$ and the
intervals of the form $I_{p}=[y+2^{n}x,y+2^{n}x+1]$, (ii) ${\lvert T\rvert}$
propositional variables which represent the tiling function $f$, (iii) $n$
additional propositional variables which represent (the binary expansion of)
the $y$-coordinate of each row of the corridor, and (iv) the modal operators
${\langle A\rangle}$ and ${\langle B\rangle}$ by means of which one can
enforce the local constrains over the tiling function $f$ (as a matter of
fact, this shows that the satisfiability problem for the $A\mspace{-0.3mu}B$
fragment is already hard for EXPSPACE).

######  Lemma 4.1.

There is a polynomial-time reduction from the exponential-corridor tiling
problem to the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$.

As for the EXPSPACE-completeness, we claim that the existence of a compass
structure $\mathcal{G}$ that features a given formula $\varphi$ can be decided
by verifying suitable local (and stronger) consistency conditions over all
pairs of contiguous rows. In fact, in order to check that these local
conditions hold between two contiguous rows $y$ and $y+1$, it is sufficient to
store into memory a bounded amount of information, namely, (i) a counter $y$
that ranges over
$\bigl{\\{}1,...,2^{2^{7{\lvert\varphi\rvert}}}+{\lvert\varphi\rvert}\cdot
2^{2^{7{\lvert\varphi\rvert}}}\bigr{\\}}$, (ii) the two guessed shadings $S$
and $S^{\prime}$ associated with the rows $y$ and $y+1$, and (iii) a function
$g:S\;\rightarrow\;S^{\prime}$ that captures the horizontal alignment relation
between points with an associated atom from $S$ and points with an associated
atom from $S^{\prime}$. This shows that the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ can be decided in exponential space,
as claimed by the following lemma. Further details about the decision
procedure, including soundness and completeness proofs, can be found in [17].

######  Lemma 4.2.

There is an EXPSPACE non-deterministic procedure that decides whether a given
formula of $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ is satisfiable or not.

Summing up, we obtain the following tight complexity result.

######  Theorem 4.3.

The satisfiability problem for $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$
interpreted over (prefixes of) natural numbers is EXPSPACE-complete.

##  5\. Conclusions

In this paper, we proved that the satisfiability problem for
$A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ interpreted over (prefixes of) the
natural numbers is EXPSPACE-complete. We restricted our attention to these
domains because it is a common commitment in computer science. Moreover, this
gave us the possibility of expressing meaningful metric constraints in a
fairly natural way. Nevertheless, we believe it possible to extend our results
to the class of all linear orderings as well as to relevant subclasses of it.
Another restriction that can be relaxed is the one about singleton intervals:
all results in the paper can be easily generalized to include singleton
intervals in the underlying structure $\mathbb{I}_{N}$. The most exciting
challenge is to establish whether the modality $\,\overline{\\!A\\!}\,$ can be
added to $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ preserving decidability
(and complexity). It is easy to show that there is not a straightforward way
to lift the proof for $A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,$ to
${A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,\,\overline{\\!A\\!}\,}$ (notice that
${\langle A\rangle}$, ${\langle B\rangle}$, and
${\langle\,\overline{\\!B\\!}\,\rangle}$ are all future modalities, while
${\langle\,\overline{\\!A\\!}\,\rangle}$ is a past one).

## References

  * [1] J.F. Allen.  Maintaining knowledge about temporal intervals.  Communications of the Association for Computing Machinery, 26(11):832–843, 1983.
  * [2] D. Bresolin, D. Della Monica, V. Goranko, A. Montanari, and G. Sciavicco.  Decidable and undecidable fragments of Halpern and Shoham’s interval temporal logic: towards a complete classification.  In Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), volume 5330 of Lecture Notes in Computer Science, pages 590–604. Springer, 2008.
  * [3] D. Bresolin, V. Goranko, A. Montanari, and P. Sala.  Tableau-based decision procedures for the logics of subinterval structures over dense orderings.  Journal of Logic and Computation, doi:10.1093/logcom/exn063, 2008\.
  * [4] D. Bresolin, V. Goranko, A. Montanari, and G. Sciavicco.  On decidability and expressiveness of propositional interval neighborhood logics.  In Proceedings of the International Symposium on Logical Foundations of Computer Science (LFCS), volume 4514 of Lecture Notes in Computer Science, pages 84–99. Springer, 2007.
  * [5] D. Bresolin, V. Goranko, A. Montanari, and G. Sciavicco.  Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions.  Annals of Pure and Applied Logic, 161(3):289–304, 2009.
  * [6] D. Bresolin, A. Montanari, P. Sala, and G. Sciavicco.  Optimal tableaux for right propositional neighborhood logic over linear orders.  In Proceedings of the 11th European Conference on Logics in Artificial Intelligence (JELIA), volume 5293 of Lecture Notes in Artificial Intelligence, pages 62–75. Springer, 2008.
  * [7] D. Bresolin, A. Montanari, and G. Sciavicco.  An optimal decision procedure for Right Propositional Neighborhood Logic.  Journal of Automated Reasoning, 38(1-3):173–199, 2007.
  * [8] D. Bresolin, V. Goranko A. Montanari, and G. Sciavicco.  Right propositional neighborhood logic over natural numbers with integer constraints for interval lengths.  In Proceedings of the 7th IEEE International Conference on Software Engineering and Formal Methods (SEFM), pages 240–249. IEEE Comp. Society Press, 2009.
  * [9] D. Gabbay, I. Hodkinson, and M. Reynolds.  Temporal Logic: mathematical foundations and computational aspects.  Oxford University Press, 1994.
  * [10] V. Goranko, A. Montanari, and G. Sciavicco.  Propositional interval neighborhood temporal logics.  Journal of Universal Computer Science, 9(9):1137–1167, 2003.
  * [11] V. Goranko, A. Montanari, and G. Sciavicco.  A road map of interval temporal logics and duration calculi.  Applied Non-classical Logics, 14(1-2):9–54, 2004.
  * [12] J.Y. Halpern and Y. Shoham.  A propositional modal logic of time intervals.  Journal of the Association for Computing Machinery, 38:279–292, 1991.
  * [13] I. Hodkinson, A. Montanari, and G. Sciavicco.  Non-finite axiomatizability and undecidability of interval temporal logics with C, D, and T.  In Proceedings of the 17th Annual Conference of the EACSL, volume 5213 of Lecture Notes in Computer Science, pages 308–322. Springer, 2008.
  * [14] K. Lodaya.  Sharpening the undecidability of interval temporal logic.  In Proceedings of the 6th Asian Computing Science Conference on Advances in Computing Science, volume 1961 of Lecture Notes in Computer Science, pages 290–298. Springer, 2000.
  * [15] C. Lutz and F. Wolter.  Modal logics of topological relations.  Logical Methods in Computer Science, 2(2), 2006.
  * [16] A. Montanari, G. Puppis, and P. Sala.  A decidable spatial logic with cone-shaped cardinal directions.  In Proceedings of the 18th Annual Conference of the EACSL, volume 5771 of Lecture Notes in Computer Science, pages 394–408. Springer, 2009.
  * [17] A. Montanari, G. Puppis, P. Sala, and G. Sciavicco.  Decidability of the interval temporal logic ${A\mspace{-0.3mu}B\,\overline{\\!B\\!}\,}$ over the natural numbers.  Research Report UDMI/2009/07, Department of Mathematics and Computer Science, University of Udine, Udine, Italy, 2009, http://users.dimi.uniud.it/$\sim$angelo.montanari/rr200907.pdf.
  * [18] M. Otto.  Two variable first-order logic over ordered domains.  Journal of Symbolic Logic, 66(2):685–702, 2001.
  * [19] P. Van Emde Boas.  The convenience of tilings.  In Complexity, Logic and Recursion Theory, volume 187 of Lecture Notes in Pure and Applied Mathematics, pages 331–363. Marcel Dekker Inc., 1997.
  * [20] Y. Venema.  A modal logic for chopping intervals.  Journal of Logic and Computation, 1(4):453–476, 1991.