# CMPUT 600 Project Report: Homonym Identification using BERT

Rohan Saha
Department of Computing Science / University of Alberta
<EMAIL_ADDRESS>
###### Abstract

Homonym identification is an important for WSD that require coarse grained
partitions of senses. The goal of this project is to determine whether
contextual information is sufficient for identifying a homonymous word. To
capture the context, BERT embeddings are used as opposed to Word2Vec, which
conflates senses into one vector. SemCor is leveraged to retrieve the
embeddings. Various clustering algorithms are applied on the embeddings.
Finally, the embeddings are visualized in a lower-dimensional space to
understand the feasibility of the clustering process.

##  1 Introduction

The study of homonymy is often debated and may be considered to be
undifferentiated to polysemy by many. Nevertheless, the study of homonymy is
important for many tasks in lexical semanticsNavigli (2018). Some tasks in
lexical semantics depend on how fine-grained the lexical resources are. For
example, in some cases, it may not be possible to use WordNetFellbaum (1998)
because many studies have shown that the distinction among senses in WordNet
is too fine grained and work has also been done to merge senses that are
similar resulting in a coarse grained sense inventorySnow et al. (2007).

The task of homonym identification can also help to indirectly alleviate this
problem because the task requires the clustering of words types into different
groups based on the semantic similarity of the word senses. An example of a
homonym would be the word type ’bank’ shown in table 1Hauer and Kondrak
(2019).

As a formal definition for the task, given a word $w$, classify $w$ as a
homonymous or a non-homonymous word. Loosely, the task is formulated as a
binary classification problem. For the purpose of explaining the methodology
and the results, the word ’light’ will be used for $w$. ’Light’ has three
homonymous senses - illumination, skinny, and lessen. The goal is to devise an
experiment that can identify at least two of these three homonymous senses
which will classify $w$ as a homonymous word. Similarly if the procedure when
applied on $w$ results in only the identification of only one homonymous
sense, then $w$ is not a homonym.

The methodology described in section 4 leverages contextual information
represented in the form of token level embeddings. Using these contextual
embeddings, the hope is to observe more than one cluster for a homonymous word
in an $n$-dimensional space, where $n$ is the number of dimensions of the
contextual embedding, and zero or no clusters for a non-homonymous word.

Bank(n1) | Bank (n2)
---|---
#2 financial institution | #1 sloping land
#5 stock held in reserve | #3 long ridge or pile
#6 funds held by a house | #4 arrangement of objects
#8 container for money | #7 slope in a road
#9 building | #10 flight maneuver
Table 1: The senses of the noun ‘bank’ from WordNet 3.0, grouped by its two
homonyms with respective sense numbers. Bank(n1) represents the first homonym
of ’Bank’ that is a noun. Bank(n2) represents the second homonym of ’Bank’
that is a noun.

##  2 Related Work

Most of the previous work for homonym detection uses embeddings that are not
truly contextual, for example, embeddings from Word2Vec. The most closely
related work on homonym detection is the work of van den Beukel and Aroyo
(2018) where humour in short text is recognized by integrating homophone and
homograph based features into existing humour recognition systems. Another
work tries to the understand the semantic classification of homonyms with
respect to human understanding by finding the most suitable computational
model. One other interesting work address the importance of distinguishing
polysemy and homonymy in information retrieval using morphology, part-of-
speech, and phrasesKrovetz (1997). Though this project address clustering
which is an unsupervised machine learning technique, the work of Wiedemann et
al. (2019) uses contextual embeddings from BERT, ELMo and Flair NLP to
classify WordNet senses using a supervised classification algorithm (K-Nearest
Neighbours).

##  3 Background Knowledge

The experiment uses various clustering and dimensionality reduction techniques
on the embeddings. In addition, the state-of-the-art BERT model is also used
to obtain the contextual embeddings.

###  3.1 BERT

BERTDevlin et al. (2018) is a transformer based model that uses an encoder to
map the input data (words) to a numerical vector or an embedding. It uses an
attention mechanism to account for all the surrounding words of the target
word. Therefore, one word token may have a different embedding depending on
its intended meaning in the sentence. BERT embeddings are appropriate for the
task given that it deals with polysemes. Sense disambiguation for a polyseme
has been previously been carried out using BERTDu et al. (2019) and here BERT
is used to distinguish between word types in a more coarse-grained manner than
polysemes. In this project, a simplified
API111https://github.com/imgarylai/bert-embedding for BERT is used where the
input is a sentence, and the output is the contextual embeddings for each of
the word tokens in that sentence.

###  3.2 Clustering Techniques

Three clustering methods were used on the contextual embeddings. First was a
hierarchical clustering known as Agglomerative Clustering222https://scikit-
learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html.
Agglomerative Clustering mergers pairs of observations with the goal of
minimally increasing a given linkage distance. In the experiment, the variance
of the clusters being merged was minimized.

The second clustering method was the MeanShift algorithm333https://scikit-
learn.org/stable/modules/generated/sklearn.cluster.MeanShift.html which works
by updating candidates for centroids to be the mean of the clusters. The third
algorithm that was used is the DBScan algorithm444https://scikit-
learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html. DBScan is a
density based clustering algorithm that clusters observations with high
spatial density in n-dimensions.

###  3.3 Dimensionality Reduction Techniques

In addition to the clustering methods, various dimensionality reductions
techniques were used. Techniques used in this project were T-SNE, PCA, Isomap,
locally linear embedding, and multi-dimensional scaling555https://scikit-
learn.org/stable/modules/manifold.html. Among these techniques, only the
results using T-SNE are shown in the paper as other methods produced
visualizations using which no significant inferences could be derived.

##  4 Experiment Design and Approach

The approach to addressing the task involves a series of steps starting from
pre-processing the dataset to clustering the contextual embeddings.

###  4.1 Pre-processing and Homonym mapping

First, a cleaned up version of SemCor is used, which is a subset of the full
data set used in Raganato et al. (2017). First, all the sentences from SemCor
are filtered out that do not match a Lemma in the list of resource homonyms
file666https://webdocs.cs.ualberta.ca/~kondrak/homonyms.html All the remaining
target words in the cleaned up version of SemCor were then mapped to their
corresponding sense key in WordNet. This mapping is required for an averaging
process of the embeddings that is be explained later. Now, for each of the
target words in this partially processed dataset, the homonymous groups need
to be mapped. In other words, the polysemous senses of the target word $w$ in
each sentence in SemCor need to be assigned a homonymous group. To do this, a
resource mapping file containing the homonym group for each sense number is
used6. This file contains the WordNet sense numbers for each word type and the
corresponding group. First, the partially processed dataset is mapped to the
sense numbers for target words and then using the sense numbers, the
homonymous group are assigned. Some homonymous senses are extremely rare and a
corresponding sentence may not appear in SemCor. Such homonyms are not
considered because the clustering algorithm will have no basis do distinguish
between groups of homonyms. Therefore, sentences that are assigned only one
group of homonyms for a target word are filtered out from SemCor.

The final list of homonyms consisted only 37 homonymous word types for which
SemCor contained sentences that represent at least two or more groups of
homonyms.

###  4.2 BERT Embeddings

Using the pre-processed dataset, BERT embeddings are retrieved for the
sentences in SemCor. The input supplied to the pre-trained BERT contains only
10 words on either side of the target word in the sentence because the API is
not able to process sentences of greater length. Ten words usually preserves
contextual information and there is no information loss. All the features of
the embeddings are used for clustering because it is fundamental to minimize
any information loss.

The obtained embeddings are not directly fed into the clustering algorithm,
instead they go through a averaging process. For each target word $w$, the
embeddings are grouped according to the sense key. For example for sense key
$a$, there may be five sentences where the target word $w$ is mapped to sense
key $a$. All the contextual embeddings for these five instances of $w$ are
averaged to create one contextual embedding. Therefore, for each word $w$ the
number of averaged embeddings is equal to its number of senses in SemCor. As a
result, the number of embeddings is equal to the number of senses for $w$.

###  4.3 Clustering Contextual Embeddings

Now, the averaged embeddings are used as input to the clustering algorithm.
The algorithms used had one common feature in that the number of the clusters
in undefined. Therefore, the clustering algorithm does not know how many
clusters are present in the embeddings; the algorithm is dependent only on its
parameters to group the embeddings. The clustering in general, does not
segregate the embeddings into distinct groups. The assigned labels from the
clustering algorithms were then compared to the true labels to observe
clustering performance.

##  5 Results and Analysis

The results are shown in this section for the word $w=light$. There was no
specific motive to choose ’light’ but only the fact that there were sentences
in SemCor that represented at least two homonymous senses namely
$illumination$ and $skinny$ corresponding to groups $100$ and $200$ in the
resource homonyms6.

Here, only the results for Hierarchical Clustering is shown because among the
three clustering algorithm used, Hierarchical Clustering actually assigns
clusters to the points, whereas other algorithms mostly treated all points as
outliers. Hierarchial Clustering tries to create clusters equal to number of
actual groups of homonyms($hom\\_type$). All the results can be replicated
using the corresponding
code777https://github.com/simpleParadox/CMPUT-600-Project. Different
dimensionality reduction techniques are also used here that help to analyze
the visualization.

Figure 1: Results for Hierarchical Clustering with T-SNE

Figure 1 shows the results when using Hierarchical Clustering using T-SNE as a
dimensionality reduction technique. It can be observed that when using T-SNE,
the points are really spaced out. This is because T-SNE by default tries to
compensate for ’crowding’ of points when projecting to a lower dimensional
space. It may be fair to argue that for the purposes of this task, T-SNE may
not be a good method for visualization. Also, we can observe that the
clustering algorithm classifies all the points into three different clusters
where cluster label 1 has only one point. The cluster labels are the outcome
of the clustering algorithm and $hom\\_type$ is the actual true
label(homonymous group) of the homonym. The $hom\\_type$ are either homonymous
groups 100 or 400 (for $w=light$), represented by solid circle and cross
respectively. The labels are colored which show the cluster number from the
clustering algorithm. Therefore, if the points are circle and black, then the
true homonymous group is 100 and the cluster label is 2. If the point is black
and a cross, then the true homonymous group is 400 but the clustering
algorithm assigned it the label 2, and hence incorrect.

Figure 2: Results for Hierarchical Clustering with PCA

In figure 2, the results for Hierarchical Clustering are shown with principal
components analysis as a dimensionality reduction technique. In this case, the
points seem to be close to each other in the lower dimensional space. PCA
works by preserving only those variables that are independent of other
variables and contribute to the highest variation in the data. From the
visualization, it can be seen that there is a ’crowding’ of points in one area
of the figure and this is because PCA is a linear transformation, and does not
account for any non-linearity in data. The figure shows that embeddings of
homonym types 100 and 400 overlap and are are difficult to assign distinct
clusters. And this is the reason for a ’crowding’ of points at the bottom left
of the figure; embeddings in group 100 and 400 are assigned cluster label 2
even though they should be assigned different cluster labels.

Figure 3: Results for Hierarchical Clustering with Multidimensional Scaling

Figure 3 shows the results for Hierarchical Clustering when visualized using a
dimensionality reduction technique known as Multidimensional Scaling(MDS).
Figure 3 show groups of points in small area and thus the probable success of
the clustering process but on close observation it can be seen the there are
numerous points belonging to the homonymous group $100$ and $400$ being
assigned cluster label 2. Therefore, figure 3 may indicate the presence of
clusters, but the clustering algorithm fails to assign correct labels. It must
be noted that MDS works better than other dimensionality reduction techniques
because it attempts to model similarity or dissimilarity of data as distances
in higher dimensional spaces. Thus, the visualizations here are more
indicative of similar embeddings than in figure 1. However, it does not
explain the inability of the clustering algorithm to assign correct label.

From the visualizations and the analysis, it is easy to observe that the
accuracy is below chance which raises doubts on the usage of a clustering
approach for the task. In addition, from the experiment it was also observed
that if the clustering algorithms were successful in assigning correct labels
for one word using one hyperparameter setting, the same hyperparameters were
unsuccessful for other words. Therefore, the algorithms lack generalization.

##  6 Conclusion

In this project, the problem of homonym identification was investigated where
an experiment was performed to check the validity of a hypothesis underlying
homonyms, that is contextual information in the form of word embeddings is
sufficient for identifying homonyms.

From the experiment, it seems that the stated hypothesis may not be true owing
to the inability of the clustering algorithms to assign distinct clusters in
high-dimensional space. An explanation for such a finding is that though the
senses in a homonymous group are semantically related (and are polysemous),
the polysemes when represented in an n-dimensional space are almost evenly
spaced out, and therefore provides a challenge for clustering the embeddings.

An extension to the task will be to use a supervised learning algorithm using
embeddings as features for classifying candidate word types into homonyms and
non-homonyms. Though such a technique will require intensive effort in terms
of data collection and preparation, a supervised learning algorithm may help
create new baselines for any future research with regard to homonym
identification.

##  7 Acknowledgement

I would like to thank Professor Grzegorz Kondrak for clarifying any questions
and concerns about the project and organizing project meetings, which helped
to monitor progress and address challenges. I would like to thank Bradley
Hauer for compiling the list of known homonyms and also providing the cleaned
up version of SemCor. In addition, my classmate Garnet Liam Peet-Pare was
extremely helpful for the project with regard to mathematical aspects of the
task.

## References

  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding http://arxiv.org/abs/1810.04805.
  * Du et al. (2019) Jiaju Du, Fanchao Qi, and Maosong Sun. 2019.  Using BERT for Word Sense Disambiguation http://arxiv.org/abs/1909.08358.
  * Fellbaum (1998) Christiane Fellbaum. 1998.  WordNet: An Electronic Lexical Database.  Bradford Books.
  * Hauer and Kondrak (2019) Bradley Hauer and Grzegorz Kondrak. 2019.  One Homonym per Translation www.aaai.org http://arxiv.org/abs/1904.08533.
  * Krovetz (1997) Robert Krovetz. 1997.  Homonymy and polysemy in information retrieval.  In 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics. Association for Computational Linguistics, Madrid, Spain, pages 72–79.  https://doi.org/10.3115/976909.979627.
  * Navigli (2018) Roberto Navigli. 2018.  Natural language understanding: Instructions for (present and future) use.  In IJCAI International Joint Conference on Artificial Intelligence. volume 2018-July, pages 5697–5702.  https://doi.org/10.24963/ijcai.2018/812.
  * Raganato et al. (2017) Alessandro Raganato, Jose Camacho-Collados, and Roberto Navigli. 2017.  Word Sense Disambiguation: A Unified Evaluation Framework and Empirical Comparison.  Technical report.  http://nlp.lsi.upc.edu/tools/.
  * Snow et al. (2007) Rion Snow, Sushant Prakash, Daniel Jurafsky, and Andrew Y Ng. 2007.  Learning to merge word senses.  In EMNLP-CoNLL 2007 - Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. pages 1005–1014.
  * van den Beukel and Aroyo (2018) Sven van den Beukel and Lora Aroyo. 2018.  Homonym detection for humor recognition in short text.  In Proceedings of the 9th Workshop on Computational Approaches to Subjectivity, Sentiment and Social Media Analysis. Association for Computational Linguistics, Brussels, Belgium, pages 286–291.  https://doi.org/10.18653/v1/W18-6242.
  * Wiedemann et al. (2019) Gregor Wiedemann, Steffen Remus, Avi Chawla, and Chris Biemann. 2019.  Does BERT Make Any Sense? Interpretable Word Sense Disambiguation with Contextualized Embeddings http://arxiv.org/abs/1909.10430.

##  Appendix A Appendices

In the report, only the results from the Hierarchical Clustering method are
shown various dimensionality reduction techniques for $w=light$. In the
appendix, the visualizations from the remaining clustering techniques with
various dimensionality reduction techniques.

Figure 4: Results for MeanShift Clustering with T-SNE, PCA, and MDS for
w=light

Subfigure 1 in figure 4 shows the visualization for MeanShift Clustering
technique with T-SNE as a dimensionality reduction technique for the word
$w=light$. It must be noted here that MeanShift assigns four clusters whereas
Hierarchical clustering assigns three. It can also be observed from the figure
that clustering fails to assign consistent labels with respect to the homonym
types 100 and 400. Also, the points are really spaced apart because T-SNE
respects the distances in higher dimensional space.

Subfigure 2 in figure 4 shows the visualization for MeanShift Clustering
Technique for $w=light$ with PCA. Again initial observation may indicate
presence of clusters, it can be seen that the labels are incorrect. Points
belonging to different homonymous groups (denoted by cross and solid circle)
are assigned the same labels and proves the inability of algorithm to find
clusters.

Subfigure 3 in 4 shows the results for MeanShift Clustering with MDS. Again,
similar to the results for PCA, the points are assigned the same cluster label
even though they belong to distinct homonymous groups.

Figure 5 shows results for $w=light$ with DBScan as the clustering algorithm.

Figure 5: Results for DBScan with T-SNE, PCA, MDS for w=light

For the DBScan algorithm, the visualizations are not significantly different
than those for Hierarchical Clustering and MeanShift Clustering but only
supports the inability of the algorithm to form clusters.

Figure 6, figure 7, and 8 for the word $w=mean$. ’mean’ was chosen from the
list of homonyms because SemCor contains sentences that represent at least two
of the homonymous groups that is 100 and 200 for the homonymous senses
$signify$ and $unkind$ respectively. It is useful to note that the number of
sentences in SemCor for $w=mean$ is more than $w=light$. However, the actual
number of senses is less compared to those of $w=light$(many sentences have
the same sense for mean). As a result, the number of averaged embeddings is
much lesser.

Figure shows 6 the results for Hierarchical clustering with PCA and MDS. We
see that the points appear to be closer in a low dimensional space but the
cluster labels are assigned incorrectly by the clustering algorithm. In figure
7 shows the results for the MeanShift clustering algorithm with PCA and MDS
for $w=mean$. MeanShift performs worse than Heirarchical clustering because
the number of cluster labels decided by the algorithm is more than the actual
number of homonymous groups. Figure 8 shows a similar visualization but the
algorithm treats many points as outliers and thus assigns the label -1.

All in all, Hierarchical Clustering (Agglomerative Clustering) performs
relatively better than all the other clustering methods.

Figure 6: Results for Hierarchial Clustering with PCA and MDS for w=mean.

Figure 7: Results for MeanShift Clustering with PCA and MDS for w=mean.

Figure 8: Results for DBScan Clustering with PCA and MDS for w=mean.


# An Approach to Forgetting in Disjunctive Logic Programs that Preserves
Strong Equivalence

James P. Delgrande
School of Computing Science
Simon Fraser University
Burnaby, B.C. V5A 1S6
Canada
<EMAIL_ADDRESS>&Kewen Wang
School of Information and Communication Technology
Griffith University,
Brisbane, QLD 4111
Australia
<EMAIL_ADDRESS>
###### Abstract

In this paper we investigate forgetting in disjunctive logic programs, where
forgetting an atom from a program amounts to a reduction in the signature of
that program. The goal is to provide an approach that is syntax-independent,
in that if two programs are strongly equivalent, then the results of
forgetting an atom in each program should also be strongly equivalent. Our
central definition of forgetting is impractical but satisfies this goal:
Forgetting an atom is characterised by the set of SE consequences of the
program that do not mention the atom to be forgotten. We then provide an
equivalent, practical definition, wherein forgetting an atom $p$ is given by
those rules in the program that don’t mention $p$, together with rules
obtained by a single inference step from rules that do mention $p$. Forgetting
is shown to have appropriate properties; as well, the finite characterisation
results in a modest (at worst quadratic) blowup. Finally we have also obtained
a prototype implementation of this approach to forgetting.

## Introduction

_Forgetting_ is an operation for eliminating variables from a knowledge base
(?; ?). It constitutes a reduction in an agent’s language or, more accurately,
signature, and has been studied under different names, such as variable
elimination, uniform interpolation and relevance (?). Forgetting has various
potential uses in a reasoning system. For example, in query answering, if one
can determine what is relevant to a query, then forgetting the irrelevant part
of a knowledge base may yield a more efficient operation. Forgetting may also
provide a formal account and justification of predicate hiding, for example
for privacy issues. As well, forgetting may be useful in summarising a
knowledge base or reusing part of a knowledge base or in clarifying relations
between predicates.

The best-known definition of forgetting is with respect to classical
propositional logic, and is due to George Boole (?). To forget an atom $p$
from a formula $\phi$ in propositional logic, one disjoins the result of
uniformly substituting $\top$ for $p$ in $\phi$ with the result of
substituting $\bot$; that is, forgetting is given by
$\phi[p/\top]\vee\phi[p/\bot]$. (?) investigated the theory of forgetting for
first order logic and its application in reasoning about action. Forgetting
has been applied in resolving conflicts (?; ?), and ontology comparison and
reuse (?; ?).

The knowledge base of an agent may be represented in a non-classical logic, in
particular a nonmonotonic approach such as answer set programming (ASP) (?; ?;
?). However, the Boole definition clearly does not extend readily to logic
programs. In the past few years, several approaches have been proposed for
forgetting in ASP (?; ?; ?; ?; ?). The approach to forgetting in (?; ?) is
syntactic, in the sense that their definition of forgetting is given in terms
of program transformations, but is not based on answer set semantics or SE
models111See the next section for definitions. (for normal logic programs). A
semantic theory of forgetting for normal logic programs under answer set
semantics is introduced in (?), in which a sound and complete algorithm is
developed based a series of program transformations. This theory is further
developed and extended to disjunctive logic programs (?; ?). However, this
theory of forgetting is defined in terms of standard answer set semantics
instead of SE models.

In order to use forgetting in its full generality, for dealing with relevance
or predicate hiding, or in composing, decomposing, and reusing answer set
programs, it is desirable for a definition to be given in terms of the
_logical content_ of a program, that is in terms of SE models. For example,
the reuse of knowledge bases requires that when a sub-program $Q$ in a large
program $P$ is substituted with another program $Q^{\prime}$, the resulting
program should be equivalent to $P$. This is not the case for answer set
semantics due to its nonmonotonicity. As a result, two definitions of
forgetting have been introduced in HT-logic (?; ?). These approaches
indirectly establish theories of forgetting under SE models as HT-logic
provides a natural extension of SE models. The approach to interpolation for
equilibrium logic introduced in (?) is more general than forgetting. However,
the issue of directly establishing a theory of forgetting for disjunctive
logic programs under SE models is still not fully resolved yet. In addition,
it is even more challenging to develop efficient algorithm for computing a
result of forgetting under SE models.

A key intuition behind forgetting is that the logical consequences of a set of
formulas that don’t mention forgotten symbols should still be believed after
forgetting. This leads to a very simple (abstract) knowledge-level definition,
provided that a consequence operator is provided in the underlying logic. In
particular, the semantics of a logic usually associates a set of models
${\mathit{Mod}({{\mathcal{K}}})}$ with each knowledge base ${\mathcal{K}}$.
This makes it straightforward to formulate a definition of forgetting based on
the above intuition. However, such a definition of forgetting suffers from the
problem of inexpressibility, i.e., the result of forgetting may not be
expressible in the logic. In this paper, we establish such a theory of
forgetting for disjunctive logic programs under SE models. Besides several
important properties, we show that the result of forgetting for a given
disjunctive program is still a disjunctive program. This result confirms the
existence and expressibility of forgetting for DLP under SE models and in fact
provides an algorithm for computing forgetting under SE models. We investigate
some optimisation techniques for the algorithm and report a prototype
implementation of the algorithm.

## Answer Set Programming

Here we briefly review pertinent concepts in answer set programming; for
details see (?; ?; ?).

Let $\mathcal{A}$ be an alphabet, consisting of a set of _atoms_. A
(_disjunctive_) _logic program_ over $\mathcal{A}$ is a finite set of rules of
the form

$a_{1};\dots;a_{m}\leftarrow
b_{1},\dots,{b_{n}},{\sim}{c_{1}},\cdots,{\sim}{c_{p}}.$ (1)

where $a_{i},b_{j},c_{k}\in\mathcal{A}$, and $m,n,p\geq 0$ and $m+n+p>0$.
Binary operators ‘;’ and ‘,’ express disjunction and conjunction respectively.
For atom $a$, ${\sim}{a}$ is (default) negation. We will use ${\cal
L}_{\mathcal{A}}$ to denote the language (viz. set of rules) generated by
$\mathcal{A}$.

Without loss of generality, we assume that there are no repeated literals in a
rule. The _head_ and _body_ of a rule $r$, $H(r)$ and $\mathit{B}(r)$, are
defined by:

$\displaystyle H(r)$ $\displaystyle=$
$\displaystyle\\{a_{1},\dots,a_{m}\\}\qquad\mbox{and}$
$\displaystyle\mathit{B}(r)$ $\displaystyle=$
$\displaystyle\\{{b_{1}},\dots,{b_{n}},{\sim}{c_{1}},\dots,{\sim}{c_{p}}\\}.$

Given a set $X$ of literals, we define

$\displaystyle X^{+}$ $\displaystyle=$ $\displaystyle\\{a\in\mathcal{A}\mid
a\in X\\},$ $\displaystyle X^{-}$ $\displaystyle=$
$\displaystyle\\{a\in\mathcal{A}\mid{\sim}{a}\in X\\},\mbox{ and}$
$\displaystyle{\sim}{X}$ $\displaystyle=$ $\displaystyle\\{{\sim}{a}\mid a\in
X\cap\mathcal{A}\\}.$

For simplicity, we sometimes use a set-based notation, expressing a rule as in
(1) as

$H(r)\\!\leftarrow B(r)^{+},{\sim}{B(r)^{-}}\ .$

The _reduct_ of a program $P$ with respect to a set of atoms $Y$, denoted
$P^{Y}$, is the set of rules:

$\\{H(r)\\!\leftarrow B(r)^{+}\mid r\in P,\;B(r)^{-}\cap Y=\emptyset\\}.$

Note that the reduct consists of negation-free rules only. An _answer set_ $Y$
of a program $P$ is a subset-minimal model of $P^{Y}$. A program induces 0, 1,
or more _answer sets_. The set of all answer sets of a program $P$ is denoted
by $\mathit{AS}(P)$. For example, the program $P=\\{a\leftarrow.\quad
c;d\leftarrow a,{\sim}{b}\\}$ has answer sets
$\mathit{AS}(P)=\\{\\{a,c\\},\\{a,d\\}\\}$. Notably, a program is nonmonotonic
with respect to its answer sets. For example, the program
$\\{q\leftarrow{\sim}{p}\\}$ has answer set $\\{q\\}$ while
$\\{q\leftarrow{\sim}{p}.\;\;p\leftarrow\\}$ has answer set $\\{p\\}$.

### SE Models

As defined by (?), an _SE interpretation_ on a signature $\mathcal{A}$ is a
pair $(X,Y)$ of interpretations such that $X\subseteq Y\subseteq\mathcal{A}$.
An SE interpretation is an _SE model_ of a program $P$ if $Y\models P$ and
$X\models P^{Y}$, where $\models$ is the relation of logical entailment in
classical logic. The set of all SE models of a program $P$ is denoted by
$\mathit{SE}(P)$. Then, $Y$ is an answer set of $P$ iff
$(Y,Y)\in\mathit{SE}(P)$ and no $(X,Y)\in\mathit{SE}(P)$ with $X\subset Y$
exists. Also, we have $(Y,Y)\in\mathit{SE}(P)$ iff $Y\in{\mathit{Mod}({P})}$.

A program $P$ is _satisfiable_ just if $\mathit{SE}(P)\neq\emptyset$.222Note
that many authors in the literature define satisfiability in terms of answer
sets, in that for them a program is satisfiable if it has an answer set, i.e.,
$\mathit{AS}(P)\neq\emptyset$. Thus, for example, we consider
$P=\\{p\leftarrow{\sim}{p}\\}$ to be satisfiable, since
$\mathit{SE}(P)\neq\emptyset$ even though $\mathit{AS}(P)=\emptyset$. Two
programs $P$ and $Q$ are _strongly equivalent_ , symbolically $P\equiv_{s}Q$,
iff $\mathit{SE}(P)=\mathit{SE}(Q)$. Alternatively, $P\equiv_{s}Q$ holds iff
$\mathit{AS}(P\cup R)=\mathit{AS}(Q\cup R)$, for every program $R$ (?). We
also write $P\models_{s}Q$ iff $\mathit{SE}(P)\subseteq\mathit{SE}(Q)$.

### SE Consequence

While the notion of SE models puts ASP on a monotonic footing with respect to
model theory, (?) has subsequently provided an inferential system for rules
that preserves strong equivalence, where his notion of _SE consequence_ is
shown to be sound and complete with respect to the semantic notion of _SE
models_. His inference system is given as follows, where lower case letters
are atoms, upper case are sets of atoms, and for a set of atoms
$C=\\{c_{1},\dots,c_{n}\\}$, ${\sim}{C}$ stands for
$\\{{\sim}{c}_{1},\dots,{\sim}{c}_{n}\\}$.

Inference Rules for SE Consequence:

Taut

$x\leftarrow x$

Contra

$\leftarrow x,{\sim}{x}$

Nonmin

From $A\leftarrow B,{\sim}{C}$ infer

$A;X\leftarrow B,Y,{\sim}{C},{\sim}{Z}$

WGPPE

From $A_{1}\\!\leftarrow\\!B_{1},x,{\sim}{C}_{1}$ and

$A_{2};x\\!\leftarrow\\!B_{2},{\sim}{C}_{2}$ infer

$A_{1};A_{2}\leftarrow B_{1},B_{2},{\sim}{C}_{1},{\sim}{C}_{2}$

S-HYP

From $A_{1}\leftarrow B_{1},{\sim}{x}_{1},{\sim}{C}_{1}$,

…,

$A_{n}\leftarrow B_{n},{\sim}{x}_{n},{\sim}{C}_{n},$

$A\leftarrow x_{1},\dots,x_{n},{\sim}{C}$ infer

$A_{1};\dots;A_{n}\leftarrow$

$B_{1},\dots,B_{n},{\sim}{C}_{1},\dots,{\sim}{C}_{n},{\sim}{A},{\sim}{C}$

Several of these rules are analogous to or similar to well-known rules in the
literature. For example, Nonmin is weakening; WGPPE is analogous to cut; and
S-HYP is a version of hyper-resolution. Let $\vdash_{s}$ denote the
consequence relation generated by these rules, for convenience allowing sets
of rules on the right hand side of $\vdash_{s}$. Then
$P\leftrightarrow_{s}P^{\prime}$ abbreviates $P\vdash_{s}P^{\prime}$ and
$P^{\prime}\vdash_{s}P$. As well, define

$\mbox{${\cal C}n_{\mathcal{A}}(P)$}=\\{r\in{\cal L}_{\mathcal{A}}\mid
P\vdash_{s}r\\}.$

Then the above set of inference rules is sound and complete with respect to
the entailment $\models_{s}$.

######  Theorem 1 ((?))

$P\models_{s}r$ iff $P\vdash_{s}r$.

## The Approach

### Formal Preliminaries

Since forgetting in our approach amounts to decreasing the alphabet, or
signature, of a logic program, we need additional notation for relating
signatures. Let $\mathcal{A}$ and $\mathcal{A}^{\prime}$ be two signatures
where $\mathcal{A}^{\prime}\subset\mathcal{A}$. Then $\mathcal{A}^{\prime}$ is
a _reduction_ 333The standard term in model theory is _reduct_ (?; ?; ?).
However _reduct_ has its own meaning in ASP, and so we adopt this variation.
of $\mathcal{A}$, and $\mathcal{A}$ is an _expansion_ of
$\mathcal{A}^{\prime}$. Furthermore, if $w$ is an SE interpretation on
$\mathcal{A}$ and $w^{\prime}$ is an SE interpretation on
$\mathcal{A}^{\prime}$ where $w$ and $w^{\prime}$ agree on the interpretation
of symbols in $\mathcal{A}^{\prime}$ then $w^{\prime}$ is the _$\mathcal{A}$
-reduction_ of $w$, and $w$ is an _$\mathcal{A}^{\prime}$ -expansion_ of
$w^{\prime}$. For fixed $\mathcal{A}^{\prime}\subset\mathcal{A}$, reductions
are clearly unique whereas expansions are not.

For a logic program $P$, $\sigma(P)$ denotes the signature of $P$, that is,
the set of atoms mentioned in $P$. SE models are defined with respect to an
understood alphabet; for SE model $w$ we also use $\sigma(w)$ to refer to this
alphabet. Thus for example if $\mathcal{A}=\\{a,b,c\\}$ then, with respect to
$\mathcal{A}$, the SE model $w=(\\{a\\},\\{a,b\\})$ is more perspicuously
written as $(\\{a,\neg b,\neg c\\},\\{a,b,\neg c\\})$, and so in this case
$\sigma(w)=\\{a,b,c\\}$.

If $\mathcal{A}^{\prime}\subset\mathcal{A}$ and for SE models $w$,
$w^{\prime}$ we have $\sigma(w)=\mathcal{A}$ and
$\sigma(w^{\prime})=\mathcal{A}^{\prime}$ then we use
$w_{\mid\mathcal{A}^{\prime}}$ to denote the reduction of $w$ with respect to
$\mathcal{A}^{\prime}$ and we use $w^{\prime}_{\uparrow\mathcal{A}}$ to denote
the set of expansions of $w^{\prime}$ with respect to $\mathcal{A}$. This
notation extends to sets of models in the obvious way. As well, we use the
notion of a reduction for logic programs; that is, for
$\mathcal{A}^{\prime}\subseteq\mathcal{A}$,

$P_{\mid\mathcal{A}^{\prime}}=\\{r\in
P\mid\sigma(r)\subseteq\mathcal{A}^{\prime}\\}.$

### An Abstract Characterisation of Forgetting

As described, our goal is to define forgetting with respect to the logical
content of a logic program. For example, if we were to forget $b$ from the
program $\\{a\leftarrow b.,\;b\leftarrow c.\\}$, we would expect the rule
$a\leftarrow c$ to be in the result, since it is implicit in the original
program. Consequently, our primary definition is the following.

###### Definition 1

Let $P$ be a disjunctive logic program over signature $\mathcal{A}$. The
result of _forgetting $\mathcal{A}^{\prime}$ in $P$_, denoted
$Forget(P,\mathcal{A}^{\prime})$, is given by:

$Forget(P,\mathcal{A}^{\prime})=\mbox{${\cal C}n_{\mathcal{A}}(P)$}\cap{\cal
L}_{\mathcal{A}\setminus\mathcal{A}^{\prime}}.$

That is, the result of forgetting a set of atoms $\mathcal{A}^{\prime}$ in
program $P$ is simply the set of SE consequences that of $P$ over the original
alphabet, but excluding atoms from $\mathcal{A}^{\prime}$.

This definition is very simple. This characterization is abstract, at the
_knowledge level_. As a consequence, many formal results are very easy to
show. On the other hand, the definition is not immediately practically useful
since forgetting results in an infinite set of rules. Consequently a key
question is to determine a finite characterisation (that is to say, a uniform
interpolant) of $Forget$. We explore these issues next.

The following results are elementary, but show that the definition of
forgetting has the “right” properties.

###### Proposition 1

Let $P$ and $P^{\prime}$ be disjunctive logic program and let $\mathcal{A}$
(possibly primed or subscripted) be alphabets.

  1. 1.

$P\vdash_{s}Forget(P,\mathcal{A})$

  2. 2.

If $P\leftrightarrow_{s}P^{\prime}$ then
$Forget(P,\mathcal{A})\leftrightarrow_{s}Forget(P^{\prime},\mathcal{A})$

  3. 3.

$Forget(P,\mathcal{A})=\mbox{${\cal
C}n_{\mathcal{A}^{\prime}}(Forget(P,\mathcal{A}))$}$

where $\mathcal{A}^{\prime}=\sigma(P)\setminus\mathcal{A}$.

  4. 4.

$Forget(P,\mathcal{A})=$

$Forget(Forget(P,\mathcal{A}\setminus\\{a\\}),\\{a\\}))$

  5. 5.

$Forget(P,\mathcal{A}_{1}\cup\mathcal{A}_{2})=$

$Forget(Forget(P,\mathcal{A}_{1}),\mathcal{A}_{2}))$

  6. 6.

$P$ is a _conservative extension_ of $Forget(P,\mathcal{A})$.

Thus, forgetting results in no consequences not in the original theory. As
well, the result of forgetting is independent of syntax and yields a
deductively-closed theory (Parts 2 and 3). Part 4 gives an iterative means of
determining forgetting on an element-by-element basis. The next part, which
generalises the previous, shows that forgetting is decomposable with respect
to a signature, which in turn implies that forgetting is a commutative
operation with respect to its second argument. Last, $P$ is a conservative
extension of the result of forgetting, which is to say, trivially
$\sigma(P)\setminus\mathcal{A}^{\prime}\subseteq\sigma(P)$, and the
consequences of $P$ and $Forget(P,\mathcal{A})$ coincide over the language
${\cal L}_{\sigma(P)\setminus\mathcal{A}^{\prime}}$.

With regards to SE models, we obtain the following results giving an
alternative characterisation of forgetting. Here only we use the notation
$\mathit{SE}_{\mathcal{A}}({P})$ to indicate the SE models of program $P$ over
alphabet $\mathcal{A}$.

###### Proposition 2

Let $\mathcal{A}^{\prime}\subseteq\mathcal{A}$, and let
$\sigma(P)\subseteq\mathcal{A}$.

  1. 1.

$\mathit{SE}_{\mathcal{A}\setminus\mathcal{A}^{\prime}}({Forget(P,\mathcal{A}^{\prime})})=\mathit{SE}_{\mathcal{A}}({P})_{\mid(\mathcal{A}\setminus\mathcal{A}^{\prime})}$

  2. 2.

$\mathit{SE}_{\mathcal{A}}({Forget(P,\mathcal{A}^{\prime})})=(\mathit{SE}_{\mathcal{A}}({P})_{\mid(\mathcal{A}\setminus\mathcal{A}^{\prime})})_{\uparrow\mathcal{A}}$

The first part provides a semantic characterisation of forgetting: the SE
models of $Forget(P,\mathcal{A}^{\prime})$ are exactly the SE models of $P$
restricted to the signature $\mathcal{A}\setminus\mathcal{A}^{\prime}$. Very
informally, what this means is that the SE models of
$Forget(P,\mathcal{A}^{\prime})$ can be determined by simply dropping the
symbols in $\mathcal{A}^{\prime}$ from the SE models of $P$. The second part,
which is a simple corollary of the first, expresses forgetting with respect to
the original signature.

Of course, one may wish to re-express the effect of forgetting in the original
language of $P$; in fact, many approaches to forgetting assume that the
underlying language is unchanged. To this end, we can consider a variant of
Definition 1 as follows, where $\mathcal{A}^{\prime}\subseteq\mathcal{A}$.

$Forget_{\mathcal{A}}(P,\mathcal{A}^{\prime})\equiv\mbox{${\cal
C}n_{\mathcal{A}}(Forget(P,\mathcal{A}^{\prime}))$}$ (2)

That is, $Forget(P,\mathcal{A}^{\prime})$ is re-expressed in the original
language with signature $\mathcal{A}$. The result is a theory over the
original language, but where the resulting theory carries no contingent
information about the domain of application regarding elements of
$\mathcal{A}^{\prime}$.

The following definition is useful in stating results concerning forgetting.

###### Definition 2

Signature $\mathcal{A}$ is _irrelevant_ to $P$, ${I\\!R}(P,\mathcal{A})$, iff
there is $P^{\prime}$ such that $P\leftrightarrow_{s}P^{\prime}$ and
$\sigma(P^{\prime})\cap\mathcal{A}=\emptyset$.

Zhang and Zhou (?) give four postulates characterising their approach to
forgetting in the modal logic S5. An analogous result follows here with
respect to forgetting re-expressed in the original signature:

###### Proposition 3

Let $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ and let $\sigma(P)$,
$\sigma(P^{\prime})\subseteq\mathcal{A}$.

Then $P^{\prime}=Forget_{\mathcal{A}}(P,\mathcal{A}^{\prime})$ iff

  1. 1.

$P\vdash_{s}P^{\prime}$

  2. 2.

If ${I\\!R}(r,\mathcal{A}^{\prime})$ and $P\vdash_{s}r$ then
$P^{\prime}\vdash_{s}r$

  3. 3.

If ${I\\!R}(r,\mathcal{A}^{\prime})$ and $P\not\vdash_{s}r$ then
$P^{\prime}\not\vdash_{s}r$

  4. 4.

${I\\!R}(P^{\prime},\mathcal{A}^{\prime})$

For the last three parts we have that, if a rule $r$ is independent of a
signature $\mathcal{A}^{\prime}$, then forgetting $\mathcal{A}^{\prime}$ has
no effect on whether that formula is a consequence of the original knowledge
base or not (Parts 2 and 3). The last part is a “success” postulate: the
result of forgetting $\mathcal{A}^{\prime}$ yields a theory expressible
without $\mathcal{A}^{\prime}$.

### A Finite Characterisation of Forgetting

#### Aside: Forgetting in Propositional Logic

We first take a quick detour to forgetting in propositional logic to
illustrate the general approach to finitely characterising forgetting. Let
$\phi$ be a formula in propositional logic and let $p$ be an atom; the
standard definition for forgetting $p$ from $\phi$ in propositional logic is
defined to be $\phi[p/\top]\vee\phi[p/\bot]$. It is not difficult to show that
this is equivalent to Definition 1, but suitably re-expressed in terms of
propositional logic. This definition however is not particularly convenient.
It is applicable only to finite sets of formulas. As well, it results in a
formula whose main connective is a disjunction.

An alternative is given as follows. Assume that a formula (or formulas) for
forgetting is expressed in clause form, where a (disjunctive) clause is
expressed as a set of literals. For forgetting an atom $p$, consider the set
of all clauses obtained by resolving on $p$:

###### Definition 3

Let $S$ be a set of propositional clauses and $p\in{\cal P}$. Define

$\displaystyle Res(S,p)=$ $\displaystyle\\{\phi\mid\exists\phi_{1},\phi_{2}\in
S\mbox{ such that }\;$ $\displaystyle p\in\phi_{1}\mbox{ and }\neg
p\in\phi_{2},\;\mbox{ and }$
$\displaystyle\phi=(\phi_{1}\setminus\\{p\\})\cup(\phi_{2}\setminus\\{\neg
p\\})\\}$

We obtain the following, where $Forget_{P\\!C}$ refers to forgetting in
propositional logic:

###### Theorem 2

Let $S$ be a set of propositional clauses over signature ${\cal P}$ and
$p\in{\cal P}$.

$Forget_{P\\!C}(P,p)\;\leftrightarrow\;{S}_{\mid({\cal
P}\setminus\\{p\\})}\cup Res(S,p).$

This provides an arguably more convenient means of computing forgetting, in
that it is easily implementable, and one remains with a set of clauses.

#### Back to Forgetting in Logic Programming:

We can use the same overall strategy for computing forgetting in a disjunctive
logic program. In particular, for forgetting an atom $a$, we can use the
inference rules from (?) to compute “resolvents” of rules that don’t mention
$a$. It proves to be the case that the corresponding definition is a bit more
intricate, since it involves various combinations of WGPPE and S-HYP, but
overall the strategy is the same as for propositional logic.

In the definition below, $ResL\\!P$ corresponds to $Res$ for forgetting in
propositional logic. In propositional logic, $Res$ was used to compute all
resolvents on an atom $a$. Here the same thing is done: we consider instances
of WGPPE and S-HYP in place of propositional resolution; these instances are
given by the two parts of the union, respectively, below.

###### Definition 4

Let $P$ be a disjunctive logic program and $a\in\mathcal{A}$.

Define:

$\displaystyle ResL\\!P(P,a)=$ $\displaystyle\\{r\mid\exists r_{1},r_{2}\in
P\mbox{ such that }\;$ $\displaystyle\quad
r_{1}=A_{1}\\!\leftarrow\\!B_{1},a,{\sim}{C}_{1},$ $\displaystyle\quad
r_{2}=A_{2};a\\!\leftarrow\\!B_{2},{\sim}{C}_{2},$ $\displaystyle\quad
r=A_{1};A_{2}\leftarrow B_{1},B_{2},{\sim}{C}_{1},{\sim}{C}_{2}\;\\}$
$\displaystyle\cup$ $\displaystyle\\{r\mid\exists
r_{1},\dots,r_{n},r^{\prime}\in P\mbox{ such that }a=a_{1}\;$
$\displaystyle\quad
r_{i}=A_{i}\\!\leftarrow\\!B_{i},{\sim}{a}_{i},{\sim}{C}_{i},\quad 1\leq i\leq
n$ $\displaystyle\quad r^{\prime}=A\leftarrow a_{1},\dots
a_{n},{\sim}{C}\quad\mbox{and}$ $\displaystyle\quad
r=A_{1};\dots;A_{n}\leftarrow$ $\displaystyle\qquad\qquad
B_{1},\dots,B_{n},{\sim}{C}_{1},\dots,{\sim}{C}_{n},{\sim}{A},{\sim}{C}\;\\}$

We obtain the following:

###### Theorem 3

Let $P$ be a disjunctive logic program over $\mathcal{A}$ and
$a\in\mathcal{A}$. Assume that any rule $r\in P$ is satisfiable, non-
tautologous, and contains no redundant occurrences of any atom.

Then:

$Forget(P,a)\leftrightarrow_{s}{P}_{\mid(\mathcal{A}\setminus\\{a\\})}\;\cup\;ResL\\!P(P,a).$

Proof Outline: From Definition 1, $Forget(P,a)$ is defined to be the set of
those SE consequences of program $P$ that do not mention $a$. Thus for
disjunctive rule $r$, $r\in Forget(P,a)$ means that $P\vdash_{s}r$ and
$a\not\in\sigma(r)$. Thus the left-to-right direction is immediate: Any
$r\in{P}_{\mid(\mathcal{A}\setminus\\{a\\})}$ or $r\in ResL\\!P(P,a)$ is a SE
consequence of $P$ that does not mention $a$.

For the other direction, assume that we have a proof of $r$ from $P$,
represented as a sequence of rules. If no rule in the proof mentions $a$, then
we are done. Otherwise, since $r$ does not mention $a$, there is a last rule
in the proof, call it $r_{n}$ that does not mention $a$, but is obtained from
rules that do mention $a$. The case where $r_{n}$ is obtained via Taut,
Contra, or Nonmin is easily handled. If $r_{n}$ is obtained via WGPPE or S-HYP
then there are rules $r_{k}$ and $r_{l}$ that mention $a$ (and perhaps other
rules in the case of S-HYP). If $r_{k}$,$r_{l}\in P$ then $r_{n}\in
ResLP(P,a)$. If one of $r_{k}$, $r_{l}$ is not in $P$ (say, $r_{k}$) then
there are several cases, but in each case it can be shown that the proof can
be transformed to another proof where the index of $r_{k}$ in the proof
sequence is decreased and the index of no rule mentioning $a$ is increased.
This process must terminate (since a proof is a finite sequence), where the
premisses of the proof are either rules of $P$ that do not mention $a$,
elements of $ResL\\!P(P,a)$, or tautologies.

Consider the following case, where $r_{n}=A_{1};A_{2};A_{3}\leftarrow
B_{1},B_{2},B_{3}$, and we use the notation that each $A_{i}$ is a set of
implicitly-disjoined atoms while each $B_{i}$ is a set of implicitly-conjoined
literals. Assume that $r_{n}$ is obtained by an application of WGPPE from
$r_{k}=a;A_{1};A_{2}\leftarrow B_{1},B_{2}$ and $r_{l}=A_{3}\leftarrow
a,B_{3}$. Assume further that $r_{k}$ is obtained from
$r_{i}=a;b;A_{1}\leftarrow B_{1}$ and $r_{j}=A_{2}\leftarrow b,B_{2}$ by an
application of WGPPE. This situation is illustrated in Figure 1a.

Figure 1a

Then essentially the steps involving the two applications of WGPPE can be
“swapped”, as illustrated in Figure 1b, where $r_{k}$ is replaced by
$r_{k}^{\prime}=a;A_{1};A_{2}\leftarrow B_{1},B_{2}$.

Figure 1b

Thus the step involving $a$ is informally “moved up” in the proof. There are
12 other cases, involving various combinations of the inference rules, but all
proceed the same as in the above. $\Box$

The theorem is expressed in terms of forgetting a single atom. Via Proposition
1.4 this readily extends to forgetting a set of atoms. Moreover, since we
inherit the results of Propositions 1 and 3, we get that the results of
forgetting are independent of syntax, even though the expression on the right
hand side of Theorem 3 is a set of rules obtained by transforming and
selecting rules in $P$. It can also be observed that forgetting an atom
results in at worst a quadratic blowup in the size of the program. While this
may seem comparatively modest, it implies that forgetting a set of atoms may
result in an exponential blowup.

###### Example 1

Let $P=\\{p\leftarrow{\sim}{q}.\;\;r\leftarrow p\\}$. Forgetting $p$ yields
$\\{r\leftarrow{\sim}{q}\\}$ (where $r\leftarrow{\sim}{q}$ is obtained by an
application of WGPPE), while forgetting $q$ and $r$ yield programs
$\\{r\leftarrow p\\}$ and $\\{p\leftarrow{\sim}{q}\\}$ respectively.

### Computation of Forgetting

By Theorem 3, we have the following algorithm for computing the result of
forgetting. A rule $r$ is a tautology if it is of the form $r=A;b\leftarrow
b,B,{\sim}{C}$; a rule $r$ is a contradictory if it is of the form
$r=A;c\leftarrow B,{\sim}{c},{\sim}{C}$; a rule $r$ is minimal if there is no
rule $r^{\prime}$ in $P$ such that $B(r^{\prime})\subseteq B(r)$,
$H(r^{\prime})\subseteq H(r)$ and one of these two subset relations is proper;
otherwise, $r$ is non-minimal.

Algorithm 1 (Computing a result of forgetting)

Input: Disjunctive program $P$ and literal $a$ in $P$.

Output: $Forget(P,a)$.

Procedure:

Step 1. Remove tautology rules, contradiction rules and non-minimal rules from
$P$. The resulting disjunctive program is still denoted $P$.

Step 2. Collect all rules in $P$ that do not contain the atom $a$, denoted
$P^{\prime}$.

Step 3. For each pair of rules
$r_{1}=A_{1}\\!\leftarrow\\!B_{1},a,{\sim}{C}_{1}$ and
$r_{2}=A_{2};a\\!\leftarrow\\!B_{2},{\sim}{C}_{2}$, add the rule
$r=A_{1};A_{2}\leftarrow B_{1},B_{2},{\sim}{C}_{1},{\sim}{C}_{2}$ to
$P^{\prime}$

Step 4. For each rule $r^{\prime}=A\leftarrow a_{1},\dots a_{n},{\sim}{C}$
where for some $i$, $a_{i}=a$, and for each set of $n$ rules
$\\{r_{i}=A_{i}\\!\leftarrow\\!B_{i},{\sim}{a}_{i},{\sim}{C}_{i}\;|\;1\leq
i\leq n\\}$, add the rule $r=A_{1};\dots;A_{n}\leftarrow
B_{1},\dots,B_{n},{\sim}{C}_{1},\dots,{\sim}{C}_{n},{\sim}{A},{\sim}{C}$ to
$P^{\prime}$.

Step 5. Return $P^{\prime}$ as $Forget(P,a)$.

Some remarks for the algorithm are in order. Obviously, Step 1 is to
preprocesss the input program by eliminating tautology rules, contradiction
rules and non-minimal rules from $P$. Initially, all rules that do not contain
$a$, which are trivial SE-consequences of $P$, are included in the result of
forgetting. In many practical applications, such a part of input program is
usually not very large and thus forgetting can be efficiently done although
the input program can be very large. Step 3 and Step 4 implement two
resolution rules WGPPE and S-HYP, respectively.

### Conflict Resolving by Forgetting: Revisited

(?; ?) explore how their semantic forgetting for logic programs can be used to
resolve conflicts in multi-agent systems. However, their notion of forgetting
is based on answer sets and thus does not preserve the syntactic structure of
original logic programs, as pointed out in (?). In this subsection, we
demonstrate how this shortcoming of Eiter and Wang’s forgetting can be
overcome in our SE-forgetting for disjunctive programs.

The basic idea of conflict resolving (?; ?) consists of two observations:

  1. 1.

each answer set corresponds to an agreement among some agents;

  2. 2.

conflicts are resolved by forgetting some literals/concepts for some
agents/ontologies.

###### Definition 5

Let $\mathcal{S}=(P_{1},P_{2},\ldots,P_{n})$, where each logic program $P_{i}$
represents the preferences/constraints of Agent $i$. A compromise of
$\mathcal{S}$ is a sequence $C=(F_{1},F_{2},\ldots,F_{n})$ where each $F_{i}$
is a set of atoms to be forgotten from $P_{i}$. An agreement of $\mathcal{S}$
on $C$ is an answer set of
$\mathsf{forget}(\mathcal{S},C)=\mathsf{forget}(P_{1},F_{1})\cup\mathsf{forget}(P_{2},F_{2})\cup\cdots\cup\mathsf{forget}(P_{n},F_{n})$.

For specific applications, we may need to impose certain conditions on each
$F_{i}$. However, the two algorithms (Algorithms 1 and 2) in (?) may not
produce intuitive results if directly used in a practical application.
Consider a simple scenario with two agents.

###### Example 2

(?) Suppose that two agents A1 and A2 try to reach an agreement on submitting
a paper to a conference, as a regular paper or as a system description. If a
paper is prepared as a system description, then the system may be implemented
either in Java or Prolog. The preferences and constraints are as follows.

  1. 1.

The same paper cannot be submitted as both a regular paper and system
description.

  2. 2.

A1 would like to submit the paper as a regular one and, in case the paper is
submitted as a system description and there is no conflict, he would prefer to
use Java.

  3. 3.

A2 would like to submit the paper as a system description but not prefer
regular paper.

Obviously, the preferences of these two agents are jointly inconsistent and
thus it is impossible to satisfy both at the same time. The scenario can be
encoded as a collection of three disjunctive programs ($P_{0}$ stands for
general constraints): $\mathcal{S}=(P_{0},P_{1},P_{2})$ where $R,S,J,P$ mean
“regular paper,” “system description,” “Java” and “Prolog,” respectively:
$P_{0}=\\{\leftarrow R,S\\},P_{1}=\\{R\leftarrow\mathit{.\quad}J\leftarrow
S,{\sim}{P}\\},P_{2}=\\{\leftarrow R\mathit{.\quad}S\leftarrow\\}$.

Intuitively, if $A_{1}$ can make a compromise by forgetting $R$, then there
will be an agreement $\\{S,J\\}$, that is, a system description is prepared
and Java is used for implementing the system. However, if we directly use
forgetting in conflict resolution, by forgetting $R$, we can only obtain an
agreement $\\{S\\}$ which does not contain $J$. In fact, this is caused by the
removal of $J\leftarrow S,{\sim}{P}$ in the process of forgetting. This rule
is abundant in $P_{1}$ but becomes relevant when we consider the interaction
of A1 with other agents (here A2).

As pointed out in (?), it is necessary to develop a theory of forgetting for
disjunctive programs such that locally abundant (or locally irrelevant) rules
in the process of forgetting can be preserved. Our SE forgetting provides an
ideal solution to the above problem. This can be seen from the definition of
SE-forgetting and Algorithm 1 (if needed, we don’t have to eliminate non-
minimal rules in Step 1). In fact, $Forget(P_{1},R)=\\{J\leftarrow
S,{\sim}{P}\\}$, which preserves the locally redundant rule $J\leftarrow
S,{\sim}{P}$.

## Conclusion

In this paper we have addressed forgetting under SE models in disjunctive
logic programs, wherein forgetting amounts to a reduction in the signature of
a program. Essentially, the result of forgetting an atom (or set of atoms)
from a program is the set of SE consequences of the program that do not
mention that atom or set of atoms. This definition then is at the _knowledge
level_ , that is, it is abstract and is independent of how a program is
represented. Hence this theory of forgetting is useful for tasks such as
knowledge base comparison and reuse. A result of the proposed forgetting under
SE models is also a result of forgetting under answer sets but not vice versa.
Moreover, we have developed an efficient algorithm for computing forgetting in
disjunctive logic programs, which is complete and sound with respect to the
original knowledge-level definition.

A prototype implementation, of forgetting has been implemented in Java and is
available publicly at http://www.ict.griffith.edu.au/~kewen/SE-Forget/. While
our experiments on the efficiency of the system are still underway,
preliminary results show that the algorithm is very efficient. Currently we
are still working on improving efficiency of the implementation and are
experimenting on applying it to large practical logic programs and randomly
generated programs. We plan to apply this notion of forgetting to knowledge
base comparison and reuse. For future work we also plan to investigate a
similar approach to forgetting for other classes of logic programs.

## References

  * [Baral 2003] Chitta Baral.  Knowledge Representation, Reasoning and Declarative Problem Solving.  Cambridge University Press, 2003.
  * [Boole 1854] George Boole.  An Investigation of the Laws of Thought.  Walton, London, 1854.  (Reprinted by Dover Books, New York, 1954).
  * [Chang and Keisler 2012] Chen C. Chang and H. Jerome Keisler.  Model Theory.  Dover Publications, third edition, 2012.
  * [Cheng et al. 2006] Fu-Leung Cheng, Thomas Eiter, Nathan Robinson, Abdul Sattar, and Kewen Wang.  LPForget: A system of forgetting in answer set programming.  In Proceedings of the 19th Joint Australian Conference on Artificial Intelligence, pages 1101–1105, 2006.
  * [Doets 1996] Kees Doets.  Basic Model Theory.  CSLI Publications, 1996.
  * [Eiter and Wang 2006] Thomas Eiter and Kewen Wang.  Forgetting and conflict resolving in disjunctive logic programming.  In Proceedings of the Twenty-First National Conference on Artificial Intelligence, pages 238–243. AAAI Press, 2006.
  * [Eiter and Wang 2008] Thomas Eiter and Kewen Wang.  Forgetting in answer set programming.  Artificial Intelligence, 172(14):1644–1672, 2008.
  * [Gabbay et al. 2011] Dov M. Gabbay, David Pearce, and Agustín Valverde.  Interpolable formulas in equilibrium logic and answer set programming.  J. Artif. Intell. Res. (JAIR), 42:917–943, 2011.
  * [Gebser et al. 2012] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub.  Answer Set Solving in Practice.  Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2012.
  * [Gelfond and Lifschitz 1988] Michael Gelfond and Vladimir Lifschitz.  The stable model semantics for logic programming.  In Proceedings of the Fifth International Conference and Symposium of Logic Programming (ICLP’88), pages 1070–1080. The MIT Press, 1988\.
  * [Hodges 1997] Wilfrid Hodges.  A Shorter Model Theory.  Cambridge University Press, Cambridge, UK, 1997.
  * [Konev et al. 2013] Boris Konev, Carsten Lutz, Dirk Walther, and Frank Wolter.  Model-theoretic inseparability and modularity of description logic ontologies.  Artificial Intelligence, 203:66–103, 2013.
  * [Kontchakov et al. 2008] Roman Kontchakov, Frank Wolter, and Michael Zakharyaschev.  Can you tell the difference between DL-Lite ontologies?  In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR-08), pages 285–295, 2008.
  * [Lang et al. 2003] J. Lang, P. Liberatore, and P. Marquis.  Propositional independence : Formula-variable independence and forgetting.  Journal of Artificial Intelligence Research, 18:391–443, 2003.
  * [Lifschitz et al. 2001] V. Lifschitz, D. Pearce, and A. Valverde.  Strongly equivalent logic programs.  ACM Transactions on Computational Logic, 2(4):526–541, 2001.
  * [Lin and Reiter 1994] F. Lin and R. Reiter.  Forget it!  In AAAI Fall Symposium on Relevance, New Orleans, November 1994\.
  * [Subramanian et al. 1997] D. Subramanian, R. Greiner, and J. Pearl.  Special issue on relevance.  Artificial Intelligence, 97(1-2), 1997.
  * [Turner 2003] Hudson Turner.  Strong equivalence made easy: Nested expressions and weight constraints.  Theory and Practice of Logic Programming, 3(4):609–622, 2003.
  * [Wang et al. 2005] Kewen Wang, Abdul Sattar, and Kaile Su.  A theory of forgetting in logic programming.  In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI), pages 682–688. AAAI Press, 2005.
  * [Wang et al. 2012] Yisong Wang, Yan Zhang, Yi Zhou, and Mingyi Zhang.  Forgetting in logic programs under strong equivalence.  In Proceedings of the Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning, 2012.
  * [Wang et al. 2013] Yisong Wang, Kewen Wang, and Mingyi Zhang.  Forgetting for answer set programming revisited.  In Proceedings, The 23rd International Joint Conference on Artificial Intelligence (IJCAI), pages 1162–1168, 2013.
  * [Wong 2008] Ka-Shu Wong.  Sound and complete inference rules for SE-consequence.  Journal of Artificial Intelligence Research, 31(1):205–216, January 2008.
  * [Zhang and Foo 1997] Y. Zhang and N. Foo.  Answer sets for prioritized logic programs.  In Proceedings of the International Symposium on Logic Programming (ILPS-97), pages 69–84. MIT Press, 1997.
  * [Zhang and Foo 2006] Yan Zhang and Norman Foo.  Solving logic program conflict through strong and weak forgetting.  Artificial Intelligence, 170:739–778, 2006.
  * [Zhang and Zhou 2009] Yan Zhang and Yi Zhou.  Knowledge forgetting: Properties and applications.  Artificial Intelligence, 173(16-17):1525–1537, November 2009.
  * [Zhang et al. 2005] Yan Zhang, Norman Y. Foo, and Kewen Wang.  Solving logic program conflict through strong and weak forgettings.  In Proceedings of the International Joint Conference on Artificial Intelligence, pages 627–634, 2005.


# A note on Bishop-Phelps-Bollobás property for operators

T. Grando  Thiago Grando - DEMAT- Universidade Estadual do Centro-Oeste ,
Alameda Élio Antonio Dalla Vecchia, Vila Carli, 05508090 - Guarapuava, PR -
Brazil,email<EMAIL_ADDRESS>and  M. L. Lourenço  Mary Lilian Lourenço
- Departamento de Matemática- Instituto de Matemática e Estatística-
Universidade de São Paulo Caixa Postal 66281 - CEP : 05315-970 - São Paulo,
Brazil. e.mail<EMAIL_ADDRESS>
###### Abstract.

The main purpose of this paper is to study Bishop-Phelps-Bollobás property for
operators on $c_{0}$-sums of euclidean spaces. We show that the pair
$(c_{0}\left(\bigoplus^{\infty}_{k=1}\ell^{k}_{2}\right)),Y)$ has the Bishop-
Phelps-Bollobás property for operators (in short BPBp for operators) whenever
Y is a uniformly convex Banach space.

###### Key words and phrases:

Banach space, Bishop-Phelps-Bollobás theorem, Norm attaining operator,

###### 2010 Mathematics Subject Classification:

Primary Primary 46B04; Secondary 46B07, 46B20.

.

##  1\. Introduction

In 1961, Bishop and Phelps [4], proved that, for any Banach space, the subset
of norm attaining functionals is dense in the topological dual space. This
result is known as Bishop-Phelps theorem. These authors posed the problem of
possible extensions of such result to operators. A lot of attention has been
devoted to extending Bishop-Phelps theorem to operators and interesting
results have been obtained about this topic. In 1970, Bollobás [5], proved a
refinement of the Bishop-Phelps theorem, which states that, every norm one
functional and its almost norming points can be approximated by a norm
attaining functional and its norm attaining point. In 2008, Acosta, Aron,
Garcia and Maestre [1], defined a new notion for a pair of Banach spaces,
which is called the Bishop-Phelps-Bollobás property for operators, and
provided many notable results. Many important reference works in the field
have appeared, among others, [1], [2], [6], [7], [8], [9], [11].

In [1] they showed, that $(\ell^{n}_{\infty},Y)$ satisfies the Bishop-Phelps-
Bollobás property for operators for every $n\in\mathbb{N}$, whenever $Y$ is a
uniformly convex Banach space. They also left the open question if $(c_{0},Y)$
satisfies the BPBp for operators, whenever $Y$ is a uniformly convex Banach
space. In this sense, S. K. Kim [11], answered the question in a positive way.
More generaly, G. Choi and S. W. Kim proved, in [6], that
($c_{0}\left(\bigoplus^{\infty}_{k=1}X\right),Y)$ has BPBp for operators, if
$X$ is a uniformly convex Banach space and $Y$ is $\mathbb{C}$-uniformly
convex Banach space. Every uniformly convex complex space is
$\mathbb{C}$-uniformly convex and the converse is not true.

The purpose of this work is to show that
($c_{0}\left(\bigoplus^{\infty}_{n=1}\ell^{n}_{2}\right),Y)$ satisfies the
BPBp for operators whenever $Y$ is uniformly convex complex Banach space.
Considering the real case, when $Y$ is strictly convex, we prove that if
($c_{0}\left(\bigoplus^{\infty}_{k=1}\ell^{n}_{2}\right),Y)$ satisfies BPBp
for operators then $Y$ is uniformly convex. In this sense, this is an
improvement of the result presented in [6], since the $c_{0}$-sum is performed
with different spaces.

Notice that, the Banach space
$c_{0}\left(\bigoplus^{\infty}_{n=1}\ell^{n}_{2}\right)$, known as
$c_{0}$-sums of the Euclidean $n$-space, is not isometric to $c_{0}$. The
importance of such space is due to the fact that the result presented by C.
Stegall, in [14], where he showed that
$\ell_{\infty}\left(\bigoplus_{n=1}^{\infty}\ell_{2}^{n}\right)$ does not have
Dunford-Pettis property, but its predual,
$\ell_{1}\left(\bigoplus_{n=1}^{\infty}\ell_{2}^{n}\right),$ has it.

Each $x\in c_{0}\left(\bigoplus^{\infty}_{n=1}\ell^{n}_{2}\right)$ can be
represented by $x=\sum^{\infty}_{n=1}\sum_{k\in I(n)}x_{k}e_{k}$, where for
every $n\in\mathbb{N}$, $I(n)=\\{l\in\mathbb{N}:\,s(n-1)+1\leq l\leq s(n)\\}$
with $s:\mathbb{N}_{0}\rightarrow\mathbb{N}_{0}$ the auxiliar function defined
by $s(n)=0$ if $n=0$ and $s(n)=1+2+\ldots+n$ if $n\neq 0$, and $(e_{k})$ is
the standard basis of
$c_{0}\left(\bigoplus^{\infty}_{n=1}\ell^{n}_{2}\right)$. The norm of $x$ is
given by the formula $\left\lVert
x\right\rVert:=\sup_{n\in\mathbb{N}}\left(\sum_{k\in I(n)}\left\lvert
x_{k}\right\rvert^{2}\right)^{1/2}$.

##  2\. Results

It will be convenient to recall the following notation. Let $X$ and $Y$ be
Banach spaces. We denote by $S_{X},$ $B_{X}$, $X^{*}$, and $\mathcal{L}(X,Y)$,
the unit sphere, the closed unit ball, the topological dual space of $X$ and
the space of all bounded linear operators from $X$ into $Y$, respectively. An
operator $T\in\mathcal{L}(X,Y)$ is said to attain its norm at $x_{0}\in
S_{X},$ if $\|T\|=\|T(x_{0})\|$. We denote by $NA(X,Y)$ the subset of
$\mathcal{L}(X,Y)$ of all norm attaining operators between $X$ and $Y$. Now,
we recall a few definitions.

######  Definition 2.1.

Let $X$ and $Y$ be Banach spaces. We say that the pair $(X,Y)$ has the Bishop-
Phelps-Bollobás property for operators ( in shortly _BPBp for operators_) if
given $\varepsilon>0$, there is $\eta(\varepsilon)>0$ such that whenever $T\in
S_{\mathcal{L}(X,Y)}$ and $x_{0}\in S_{X}$ satisfy that
$\|Tx_{0}\|>1-\eta(\varepsilon)$, then there exist a point $u_{0}\in S_{X}$
and an operator $S\in S_{{\mathcal{L}(X,Y)}}$ satisfying the following
conditions

$\|Su_{0}\|=1,\quad\|u_{0}-x_{0}\|<\varepsilon,\quad\text{and}\quad\|S-T\|<\varepsilon.$

A Banach space $X$ is uniformly convex if for every $\epsilon>0$ there is a
$0<\delta<1$ such that, if $\left\lVert\frac{x+y}{2}\right\rVert>1-\delta$ for
every $x,y\in B_{X}$, then $\left\lVert x-y\right\rVert<\epsilon$. In this
case, the modulus of convexity is given by
$\delta(\epsilon)=\inf\left\\{1-\left\lVert\frac{x+y}{2}\right\rVert:\,x,y\in
B_{X},\,\left\lVert x-y\right\rVert\geq\epsilon\right\\}$. A Banach space $X$
is strictly convex if $\left\lVert\frac{x+y}{2}\right\rVert<1$ whenever
$x,y\in S_{X}$ and $x\neq y$. We remark that uniformly convexity implies
strictly convexity, but the converse is not true.

We observe that in the following results, we will use similar techniques found
in [1], [6] and [11].

######  Lemma 2.2.

Let $Y$ be a strictly convex Banach space and let
$T\in\mathcal{L}(c_{0}\left(\bigoplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y)$.
If $\|T(x)\|=\|T\|$ for some $x=\sum^{\infty}_{n=1}\sum_{k\in
I(n)}x_{k}e_{k}\in
S_{c_{0}\left(\bigoplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$, so

$\displaystyle T(e_{k})=0\quad\text{for all}\quad
k\in\left\\{j\in\mathbb{N}:\left(\sum_{i\in I(j)}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}<1\right\\}.$

###### Proof.

Let $x=\sum^{\infty}_{n=1}\sum_{k\in I(n)}x_{k}e_{k}$ be an element of
$S_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$ such that
$\|T(x)\|=\|T\|$. The set $\left\\{j\in\mathbb{N}:\left(\sum_{i\in
I(j)}\left\lvert x_{i}\right\rvert^{2}\right)^{1/2}<1\right\\}$ is nonempty,
since $\left\lVert x\right\rVert=\sup_{n\in\mathbb{N}}\left(\sum_{i\in
I(n)}\left\lvert x_{i}\right\rvert^{2}\right)^{1/2}=1$.

Now, we will show by a contradiction, and we assume that there exists
$k_{0}\in\left\\{j\in\mathbb{N}:\left(\sum_{i\in I(j)}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}<1\right\\}$ such that $T(e_{k_{0}})\neq 0$.
If we consider $I(k_{0})=\\{k,\ldots,l\\}$, where $k,\ldots,l\in\mathbb{N}$,
then the element $v:=\left(x_{k}\pm\left(1-\left(\sum_{i\in
I(k_{0})}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}\right),x_{k+1},\ldots,x_{l}\right)\in\ell^{k_{0}}_{2}$
and $\|v\|\leq 1.$ It implies that

$\displaystyle\left\lVert x\pm\left(1-\left(\sum_{i\in I(k_{0})}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}\right)e_{k}\right\rVert$ $\displaystyle=$
$\displaystyle\sup_{n\in\mathbb{N}}\left\\{\left(\sum_{i\in
I(n)\setminus\\{k_{0}\\}}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2},\left\lVert v\right\rVert_{2}\right\\}$
$\displaystyle\leq$ $\displaystyle 1.$

By assumption $\left\lVert T(x)\right\rVert=\left\lVert T\right\rVert$, we
have naturally $\left\lVert T(2x)\right\rVert=2\left\lVert T\right\rVert,$

$\displaystyle 2\|T\|$ $\displaystyle\leq$ $\displaystyle\left\lVert
T\left(x+\left(1-\left(\sum_{i\in I(k_{0})}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}\right)e_{k}\right)\right\rVert$
$\displaystyle+$ $\displaystyle\left\lVert T\left(x-\left(1-\left(\sum_{i\in
I(k_{0})}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}\right)e_{k}\right)\right\rVert$
$\displaystyle\leq$ $\displaystyle 2\left\lVert T\right\rVert.$

So, $\left\lVert T\left(x\pm\left(1-\left(\sum_{i\in I(k_{0})}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}\right)e_{k}\right)\right\rVert=\|T\|$, and
$\frac{T\left(x\pm\left(1-\left(\sum_{i\in I(k_{0})}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}\right)e_{k}\right)}{\|T\|}\in S_{Y}$.
Finally,

$\left\|\frac{\frac{T\left(x+\left(1-\left(\sum_{i\in I(k_{0})}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}\right)e_{k}\right)}{\|T\|}+\frac{T\left(x-\left(1-\left(\sum_{i\in
I(k_{0})}\left\lvert
x_{i}\right\rvert^{2}\right)^{1/2}\right)e_{k}\right)}{\|T\|}}{2}\right\|$
$=\left\|\frac{2T(x)}{2\|T\|}\right\|=1.$

Contradicting the fact that $Y$ is a strictly convex Banach space, then
$T(e_{k_{0}})=0$. ∎

As a consequence of the Lemma 2.2 we get the folowing theorem.

######  Theorem 2.3.

Let $c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)$ a real Banach space
and $Y$ a strictly convex real Banach space. If
$\left(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y\right)$ satisfies
the BPBp, then $Y$ is an uniformly convex Banach space.

###### Proof.

Suppose that $Y$ is not an uniformly convex Banach space. Then there exists
$\epsilon>0$ and sequences $(y_{k}),(z_{k})\subset S_{Y}$ such that

(1)
$\displaystyle\lim_{k\rightarrow\infty}\left\|\frac{y_{k}+z_{k}}{2}\right\|=1\quad\text{and}\quad\|y_{k}-z_{k}\|>\epsilon,\,\,\forall
k.$

For each positive integer $i\in\mathbb{N}$, we define
$T_{i}:c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)\longrightarrow Y$
by

$T_{i}(x)=\left(\frac{x_{1}+x_{2}}{2}\right)y_{i}+\left(\frac{x_{1}-x_{2}}{2}\right)z_{i},\quad
x=(x_{k})\in X.$

For each $i\in\mathbb{N}$ and each $x\in
S_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$ we have that

$\left\lVert T_{i}(x)\right\rVert\leq\frac{1}{2}\\{\left\lvert
x_{1}+x_{2}\right\rvert+\left\lvert x_{1}-x_{2}\right\rvert\\}\leq 1.$

As $\left\|T_{i}(e_{1}+e_{2})\right\|=1$, it follows that $\left\lVert
T_{i}\right\rVert=1$, for each $i\in\mathbb{N}$. We observe that, for each
$i\in\mathbb{N}$,
$\left\|T_{i}(e_{1})\right\|=\left\|\frac{y_{i}+z_{i}}{2}\right\|$, by
$\|T_{i}(e_{1})\|$ converges to $1$ when $i\to\infty.$ Then there is
$i_{0}\in\mathbb{N}$ such that
$\|T_{i_{0}}(e_{1})\|>1-\eta\left(\frac{\epsilon}{2}\right)$. As the pair
$\left(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y\right)$ has the
BPBp, there are an operator $R\in
S_{\mathcal{L}\left(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y\right)}$
and a point $u\in S_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$
such that

(2)
$\|R(u)\|=1,\,\,\|R-T_{i_{0}}\|<\frac{\epsilon}{2},\,\,\|u-e_{1}\|<\beta\left(\frac{\epsilon}{2}\right)<1.$

Then $\left(\sum_{i\in I(k)}\left\lvert u_{i}\right\rvert^{2}\right)^{1/2}<1$,
for all $k\in\mathbb{N}\setminus\\{1\\}$, and by Lemma 2.2,

$\displaystyle R(e_{k})=0,\quad\text{for all}\ \quad
k\in\mathbb{N}\setminus\\{1\\}.$

Therefore, it can be assumed that $u=e_{1},$ so
$R(e_{1})=R(e_{1}+e_{2})=R(e_{1}-e_{2})$, it implies that

$\displaystyle\|y_{i_{0}}-z_{i_{0}}\|$ $\displaystyle=$
$\displaystyle\|T_{i_{0}}(e_{1}+e_{2})-T_{i_{0}}(e_{1}-e_{2})\|$
$\displaystyle=$
$\displaystyle\|T_{i_{0}}(e_{1}+e_{2})-R(e_{1}+e_{2})+R(e_{1}-e_{2})-T_{i_{0}}(e_{1}-e_{2})\|$
$\displaystyle\leq$
$\displaystyle\|T_{i_{0}}-R\|\|e_{1}+e_{2}\|+\|R-T_{i_{0}}\|\|e_{1}-e_{2}\|$
$\displaystyle<$
$\displaystyle\frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon.$

It is a contradiction, so $Y$ is an uniformly convex Banach space.

∎

We need the next Lemma to show the main result.

######  Lemma 2.4.

Let $F\subset\mathbb{N}$ and $A=\bigcup_{i\in F}I(i)$. Suppose that
$0<\epsilon<1$ and $Y$ an uniformly convex Banach space with modulus of
convexity $\delta(\epsilon)$. If $T\in
S_{\mathcal{L}(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y)}$
satisfies that $\|TP_{A}\|>1-\delta(\epsilon)$, then
$\|T(I-P_{A})\|\leq\epsilon$.

###### Proof.

Let $0<\epsilon<1$ and $T\in
S_{\mathcal{L}(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y)}$ an
operator such that $\left\lVert TP_{A}\right\rVert>1-\delta(\epsilon)$. Then
there exists $x\in S_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}\cap
P_{A}(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right))$ such that
$\|TP_{A}(x)\|>1-\delta(\epsilon)$. Fix an element
$y=\sum^{\infty}_{n=1}\sum_{k\in I(n)}y_{k}e_{k}\in
B_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$ with
$\text{supp}\,y\subset\mathbb{N}\setminus A$, then

$\displaystyle\left\|x\pm y\right\|$ $\displaystyle=$
$\displaystyle\sup_{j\in\mathbb{N}}\left\\{\left(\sum_{i\in I(j),j\in
F}\left\lvert x_{i}\right\rvert^{2}\right)^{1/2},\left(\sum_{i\in
I(j),j\in\mathbb{N}\setminus F}\left\lvert
y_{i}\right\rvert^{2}\right)^{1/2}\right\\}$ $\displaystyle\leq$
$\displaystyle 1,$

it implies that, $\left\|T(x\pm y)\right\|\leq 1$, for every $y\in
B_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$ with
$\text{supp}\,y\subset\mathbb{N}\setminus A$. Notice that, for every $z\in
B_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$, the support of the
vector $(I-P_{A})(z)$ is a subset of $\mathbb{N}\setminus A$ and then,
$\left\|T(x)\pm T(I-P_{A})(z)\right\|\leq 1$. So

$\displaystyle\left\|\frac{T(x+(I-P_{A})(z))+T(x-(I-P_{A})(z))}{2}\right\|$
$\displaystyle=$ $\displaystyle\left\|TP_{A}(x)\right\|$ $\displaystyle>$
$\displaystyle 1-\delta(\epsilon).$

As $Y$ is an uniformly convex Banach space,it implies that

$\left\|T(x+(I-P_{A})(z))-T(x-(I-P_{A})(z))\right\|<\epsilon.$

That is, $\|T(I-P_{A})(z)\|<\frac{\epsilon}{2}<\epsilon$, whenever $z\in
B_{X}$. This shows that $\left\|T(I-P_{A})\right\|<\epsilon$. ∎

In [1] the authors proved that the pair $(X,Y)$ has the BPBp for operators
when $X$ and $Y$ are both finite-dimensional. In the next proposition, we show
that for specifically finite dimensional space $X$ and $Y$ is any uniformly
convex space. The next proposition is similar the result in the Remark 2.5 in
[6].

######  Proposition 2.5.

If $Y$ is an uniformly convex Banach space, then the pair
$\left(\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right),Y\right)$
satisfies the Bishop-Phelps-Bollobás for operators.

###### Proof.

The proof can be performed analogously to the Theorem. 2.4 in [6] with some
changes, for example we need to use the convexity modulus equal the maximal in
the convexity modulus of each space involved in the finite sum. ∎

######  Theorem 2.6.

If $Y$ is an uniformly convex Banach space, then the pair
$(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y)$ satisfies the
Bishop-Phelps-Bollobás for operators.

###### Proof.

Let $0<\epsilon<1$. As
$\left(\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right),Y\right)$ has
the BPBp for operators, ithen that there exist $0<\eta(\epsilon)<\epsilon$ and
$\beta(\epsilon)>0$, with $\lim_{\epsilon\rightarrow 0}\beta(\epsilon)=0$,
such that, for every $Q\in
S_{\mathcal{L}\left(\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right),Y\right)}$
and $z\in S_{\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right)}$ which
satisfies that $\|Q(z)\|>1-\eta(\epsilon)$ there exist $\tilde{Q}\in
S_{\mathcal{L}\left(\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right),Y\right)}$
and $z_{0}\in S_{\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right)}$
such that

(3)
$\displaystyle\|\tilde{Q}(z_{0})\|=1,\quad\|z-z_{0}\|<\beta(\epsilon),\quad\|\tilde{Q}-Q\|<\epsilon.$

Now, let $T\in
S_{\mathcal{L}\left(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y\right)}$
and $x=\sum^{\infty}_{n=1}\sum_{k\in I(n)}x_{k}e_{k}\in
S_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$ such that

$\displaystyle\|T(x)\|$ $\displaystyle>$ $\displaystyle
1-\eta(\epsilon)+\gamma(\epsilon),$

and

$\displaystyle\|T(x)\|$ $\displaystyle>$ $\displaystyle
1-\delta(\epsilon)+\gamma(\epsilon),$

where $\delta(\epsilon)>0$ is the modulus of convexity of $Y,$
$\gamma(\epsilon)>0$ and $\lim_{\epsilon\rightarrow o}\gamma(\epsilon)=0$.
Since $c_{00}$ is a dense subspace of
$c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)$, we can be choose a
vector $u\in S_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$, with
finite support, such that $\|x-u\|<\gamma(\epsilon)$. Then

(4) $\displaystyle\left\lVert T(u)\right\rVert=\left\lVert
T(x-x+u)\right\rVert$ $\displaystyle\geq$ $\displaystyle\left\lVert
T(x)\right\rVert-\left\lVert T(x-u)\right\rVert$ $\displaystyle>$
$\displaystyle 1-\eta(\epsilon).$

Similarly, $\left\lVert T(u)\right\rVert>1-\delta(\epsilon)$. Let
$n=\min\\{k\in\mathbb{N}:\text{supp}\,u\subset\bigcup^{k}_{j=1}I(j)\\}$, and
$A=\bigcup^{n}_{k=1}I(k)$. Then

$\displaystyle\|TP_{A}\|\geq\|TP_{A}(u)\|=\|T(u)\|>1-\delta(\epsilon),$

and

(5) $\displaystyle\|TP_{A}\|>1-\eta(\epsilon).$

By Lemma 2.4,

(6) $\|T(I-P_{A})\|\leq\epsilon.$

Let $J:\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right)\rightarrow
c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)$ be the map defined by

$\displaystyle J(w)=\left\\{\begin{array}[]{ll}w_{i},\,\text{se}\,i\in A\\\
0,\,\text{se}\,i\in\mathbb{N}\setminus A.\end{array}\right.$

We observe that $\left\lVert J(w)\right\rVert=\max_{1\leq j\leq
n}\left(\sum_{i\in I(j)}\left\lvert
w_{i}\right\rvert^{2}\right)^{1/2}=\left\lVert w\right\rVert$, for every
$w\in\ell_{\infty}\left(\bigoplus^{n}_{i=1}\ell^{k}_{2}\right)$. Let
$Q:\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right)\rightarrow Y$ be
the bounded linear operator defined by $Q(w)=\frac{TP_{A}J}{\left\lVert
TP_{A}J\right\rVert}(w)$ and the element
$z=(z_{i})\in\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right)$ given
by $z_{i}=u_{i}$, if $i\in A$ and $z_{i}=0$ if $i\in\mathbb{N}\setminus A$. It
is easy to check that $\left\|Q\right\|=\left\|z\right\|=1,$ and as
$\left\lVert TP_{A}J\right\rVert\leq 1$, we get

(8) $\left\lVert Q(z)\right\rVert=\left\lVert\frac{TP_{A}J}{\left\lVert
TP_{A}J\right\rVert}(z)\right\rVert\geq\left\lVert
TP_{A}(u)\right\rVert=\left\lVert T(u)\right\rVert,$

and by (4) we have that $\|Q(z)\|>1-\eta(\epsilon)$. By Proposition 2.5 the
pair
$\left(\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right),Y\right)$ has
the BPBp for operators, so there exist $\tilde{R}\in
S_{\mathcal{L}\left(\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right),Y\right)}$
and $\tilde{u}\in
S_{\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right)}$, such that

(9)
$\displaystyle\|\tilde{R}(\tilde{u})\|=1,\quad\left\|\tilde{R}-Q\right\|<\epsilon,\quad\|z-\tilde{u}\|<\beta(\epsilon).$

Now, we consider $(e_{k})$, $(f_{k})$ be the canonical basis of
$c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)$ and
$\ell_{\infty}\left(\bigoplus^{n}_{k=1}\ell^{k}_{2}\right)$, respectively, and
$R:c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)\longrightarrow Y$ be
the bounded linear operator given by

$R(y)=\sum^{\infty}_{j=1}\sum_{i\in I(j)}y_{i}R(e_{i}),$

where

$\displaystyle
R(e_{i})=\left\\{\begin{array}[]{ll}\tilde{R}(f_{i}),\,\text{if}\,i\in A\\\
0,\,\text{if}\,i\in\mathbb{N}\setminus A,\end{array}\right.$

and the vector $v=(v_{i})_{i}\in
c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)$ defined by

$\displaystyle v_{i}=\left\\{\begin{array}[]{ll}\tilde{u}_{i},\,\,i\in A\\\
x_{i},\,\,i\in\mathbb{N}\setminus A.\end{array}\right.$

So $R\in
S_{\mathcal{L}\left(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y\right)}$,
$v\in S_{c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right)}$ and
$\|R(v)\|=\|\tilde{R}(\tilde{u})\|=1.$

It follows that $R$ attain its norm in $v$. Next we will show that
$\|R-T\|<\epsilon.$

$\displaystyle\left\|R-T\right\|$ $\displaystyle\leq$
$\displaystyle\displaystyle\left\|R-\frac{TP_{A}}{\|TP_{A}\|}\right\|+\left\|\frac{TP_{A}}{\|TP_{A}\|}-TP_{A}\right\|+\left\|TP_{A}-T\right\|$
$\displaystyle=$
$\displaystyle\displaystyle\left\|\tilde{R}-\frac{TP_{A}J}{\|TP_{A}J\|}\right\|+\left\|\frac{TP_{A}}{\|TP_{A}\|}-TP_{A}\right\|+\left\|TP_{A}-T\right\|$
$\displaystyle=$
$\displaystyle\left\|\tilde{R}-\frac{TP_{A}J}{\|TP_{A}J\|}\right\|+\left\lVert
TP_{A}\right\rVert\left\lvert\frac{1}{\left\lVert
TP_{A}\right\rVert}-1\right\rvert+\left\|TP_{A}-T\right\|$ $\displaystyle=$
$\displaystyle\displaystyle\left\|\tilde{R}-Q\right\|+\left\lvert
1-\left\lVert TP_{A}\right\rVert\right\rvert+\left\|TP_{A}-T\right\|$
$\displaystyle<$
$\displaystyle\displaystyle\epsilon+1-1+\eta(\epsilon)+\epsilon<3\epsilon.$

Finally, we show that the vectors $v$ and $x$ are close,

$\displaystyle\left\|v-x\right\|=\left\|P_{A}(v-x)\right\|$ $\displaystyle=$
$\displaystyle\max_{1\leq j\leq n}\left(\sum_{i\in I(j)}\left\lvert
v_{i}-x_{i}\right\rvert^{2})\right)^{1/2}$ $\displaystyle=$
$\displaystyle\max_{1\leq j\leq n}\left(\sum_{i\in
I(j)}\left\lvert\tilde{u}_{i}-x_{i}\right\rvert^{2})\right)^{1/2}$
$\displaystyle\leq$ $\displaystyle\max_{1\leq j\leq n}\left(\sum_{i\in
I(j)}\left\lvert\tilde{u}_{i}-u_{i}\right\rvert^{2})\right)^{1/2}$
$\displaystyle+\max_{1\leq j\leq n}\left(\sum_{i\in I(j)}\left\lvert
u_{i}-x_{i}\right\rvert^{2})\right)^{1/2}$ $\displaystyle\leq$
$\displaystyle\left\lVert\tilde{u}-z\right\rVert+\left\lVert
u-x\right\rVert<\beta(\epsilon)+\gamma(\epsilon),$

where $\lim_{\epsilon\rightarrow
0}\beta(\epsilon)+\gamma(\epsilon)=0$.Therefore
$\left(c_{0}\left(\oplus^{\infty}_{k=1}\ell^{k}_{2}\right),Y\right)$ satisfies
the $BPBp$ for operators. ∎

## References

  * [1] M.D. Acosta, R.M. Aron, D. García and M. Maestre, The Bishop-Phelps-Bollobás theorem for operators, J. Funct. Anal. 254 (11) (2008), 2780–2799.
  * [2] M Acosta,J, Becerra-Guerrero,Y.S. Choi, M. Ciesielski S. K. Kim, H.. Lee, M.L. Lourenço and M. Martín  The Bishop-Phelps-Bollobás property for operators between spaces of continuous functions, Nonlinear Analysis, Theory, Methods and Applications 95(2014),323-332.
  * [3] R.M. Aron, Y.S. Choi, D. García and M. Maestre, The Bishop-Phelps-Bollobás theorem for ${\mathcal{L}}(L_{1}(\mu),L_{\infty}[0,1])$, Adv. Math. 228 (1) (2011), 617-628.
  * [4] E. Bishop and R.R. Phelps, A proof that every Banach space is subreflexive, Bull. Amer. Math. Soc. (N.S.) 67 (1961), 97-98.
  * [5] B. Bollobás, An extension to the theorem of Bishop and Phelps, Bull. London Math. Soc. 2 (1970), 181-182.
  * [6] G. Choi and S. K. Kim, The Bishop-Phelps-Bollobás property on the space of $c_{0}$-sum, Mediterr. J. Math. 19, 72(2022), 16pp.
  * [7] Y.S. Choi and S.K. Kim, The Bishop-Phelps-Bollobás theorem for operators from $L_{1}(\mu)$ to Banach spaces with the Radon-Nikodým property, J. Funct. Anal. 261(6) (2011), 1446-1456.
  * [8] Y.S. Choi and S.K. Kim, The Bishop-Phelps-Bollobás property and lush spaces,  J. Math. Anal. Appl. 390 (2012), 549-555.
  * [9] Y.S. Choi, S.K. Kim, H.J. Lee and M. Martín, The Bishop-Phelps-Bollobás theorem for operators on $L_{1}(\mu)$, J. Funct. Anal. 267(91)(2014),214-242.
  * [10] Y. S. Choi, S. K. Kim, H. J. Lee and M. Martín, On Banach spaces with the approximate hyperplane series property, Banach J. Math. Anal. 9 ( 4 )(2015), 243-258.
  * [11] S.K. Kim,  The Bishop-Phelps-Bollobás theorem for operators from $c_{0}$ to uniformly convex spaces, Israel J. Math. 197(1) (2013), 425-435.
  * [12] S.K. Kim and H.J. Lee,  Uniform convexity and Bishop-Phelps-Bollobás property, Canadian J. Math. 66(2)(2014),372-386.
  * [13] J. Lindenstrauss, On operators which attain their norm, Israel J. Math. 1 (1963), 139-148.
  * [14] C. Stegall, _Duals of certain spaces with the Dunford-Pettis property_ , Notices Amer. Math. Soc. 19 (1972), 799.