# Existence of Doubly-Weighted Pseudo Almost Periodic Solutions to Some
Classes of Nonautonomous
Differential Equations

Toka Diagana  Department of Mathematics, Howard University, 2441 6th Street
N.W., Washington, D.C. 20059, USA<EMAIL_ADDRESS>
###### Abstract.

The main objective of this paper is twofold. We first show that if the doubly-
weighted Bohr spectrum of an almost periodic function exists, then it is
either empty or coincides with the Bohr spectrum of that function. Next, we
investigate the problem which consists of the existence of doubly-weighted
pseudo-almost periodic solutions to some nonautonomous abstract differential
equations.

###### Key words and phrases:

weight, weighted pseudo-almost periodic, doubly-weighted Bohr spectrum, almost
periodic, doubly-weighted pseudo-almost periodic.

###### 2000 Mathematics Subject Classification:

primary 35B15; secondary 34D09; 58D25; 42A75; 37L05

##  1\. Introduction

Motivated by the functional structure of the so-called weighted Morrey spaces
[16], in Diagana [10], a new concept called doubly-weighted pseudo-almost
periodicity, which generalizes in a natural fashion the notion of weighted
pseudo-almost periodicity is introduced and studied. Among other things, in
[10], properties of these new functions have been studied including the
stability of the convolution operator, the translation-invariance, the
existence of a doubly-weighted mean for almost periodic functions under some
reasonable assumptions, the uniqueness of the decomposition involving these
new functions as well as some results on the composition of these new
functions have been studied.

The main objective of this paper is twofold. We first show if the doubly-
weighted Bohr spectrum of an almost periodic function exists, then it is
either empty or coincides with the Bohr spectrum of that function. Next, we
investigate the problem which consists of the existence of doubly-weighted
pseudo-almost periodic solutions to the nonautonomous abstract differential
equations

(1.1) $\displaystyle u^{\prime}(t)=A(t)u(t)+g(t,u(t)),\;\;t\in\mathbb{R},$

where $A(t)$ for $t\in\mathbb{R}$ is a family of closed linear operators on
$D(A(t))$ satisfying the well-known Acquistapace and Terreni conditions, and
$g:\mathbb{R}\times\mathbb{X}\mapsto\mathbb{X}$ is doubly weighted pseudo-
almost periodic in $t\in\mathbb{R}$ uniformly in the second variable.

It is well-known that in that case, there exists an evolution family
${\mathcal{U}}=\\{U(t,s)\\}_{t\geq s}$ associated with the family of linear
operators $A(t)$. Assuming that the evolution family
${\mathcal{U}}=\\{U(t,s)\\}_{t\geq s}$ is exponentially dichotomic and under
some additional assumptions it will be shown that Eq. (1.1) has a unique
doubly-weighted pseudo-almost periodic solution.

The existence of weighted pseudo-almost periodic, weighted pseudo-almost
automorphic, and pseudo-almost periodic solutions to differential equations
constitutes one of the most attractive topics in qualitative theory of
differential equations due to possible applications. Some contributions on
weighted pseudo-almost periodic functions, their extensions, and their
applications on differential equations have recently been made, among them are
for instance [1], [5], [7], [8], [12], [13], [14], [15], [18], [20], [21],
[28], and [29] and the references therein. However, the problem which consists
of the existence of doubly-weighted pseudo-almost periodic(mild) solutions to
evolution equations in the form Eq. (1.1) is quite new and untreated and thus
constitutes one of the main motivations of the present paper.

The paper is organized as follows: Section 2 is devoted to preliminaries
results related to the existence of an evolution family, intermediate spaces,
properties of weights, and basic definitions and results on the concept of
doubly-weighted pseudo-almost periodic functions. Section 3 is devoted to the
existence of a doubly-weighted Bohr spectral theory for almost periodic
functions while Section 4 is devoted to the existence of doubly-weighted
pseudo-almost periodic solutions to Eq. (1.1).

##  2\. Preliminaries

Let $(\mathbb{X},\|\cdot\|)$ be a Banach space. If $C$ is a linear operator on
$\mathbb{X}$, then $D(C)$, $\rho(C)$, and $\sigma(C)$ stand respectively for
the domain, resolvent, and spectrum of $C$. Similarly, one sets
$R(\lambda,C):=(\lambda I-C)^{-1}$ for all $\lambda\in\rho(C)$ where $I$ is
the identity operator for $\mathbb{X}$. Furthermore, we set $Q=I-P$ for a
projection $P$. We denote the Banach algebra of bounded linear operators on
$\mathbb{X}$ equipped with its natural norm by $B(\mathbb{X})$.

If $\mathbb{Y}$ is another Banach space, we then let
$BC(\mathbb{R},\mathbb{X})$ (respectively,
$BC(\mathbb{R}\times\mathbb{Y},\mathbb{X})$) denote the collection of all
$\mathbb{X}$-valued bounded continuous functions and equip it with the sup
norm (respectively, the space of jointly bounded continuous functions
$F:\mathbb{R}\times\mathbb{Y}\mapsto\mathbb{X}$).

The space $BC(\mathbb{R},\mathbb{X})$ equipped with the sup norm is a Banach
space. Furthermore, $C(\mathbb{R},\mathbb{Y})$ (respectively,
$C(\mathbb{R}\times\mathbb{Y},\mathbb{X})$) denotes the class of continuous
functions from $\mathbb{R}$ into $\mathbb{Y}$ (respectively, the class of
jointly continuous functions $F:\mathbb{R}\times\mathbb{Y}\mapsto\mathbb{X}$).

###  2.1. Evolution Families

The setting of this Subsection follows that of Baroun et al. [3] and Diagana
[14]. Fix once and for all a Banach space $(\mathbb{X},\|\cdot\|)$.

######  Definition 2.1.

A family of closed linear operators $A(t)$ for $t\in\mathbb{R}$ on
$\mathbb{X}$ with domain $D(A(t))$ (possibly not densely defined) satisfy the
so-called Acquistapace and Terreni conditions, if there exist constants
$\omega\in\mathbb{R}$, $\theta\in(\frac{\pi}{2},\pi)$, $L>0$ and
$\mu,\nu\in(0,1]$ with $\mu+\nu>1$ such that

(2.1)
$\Sigma_{\theta}\cup\\{0\\}\subset\rho(A(t)-\omega)\ni\lambda,\;\qquad\|R(\lambda,A(t)-\omega)\|\leq\frac{K}{1+|\lambda|}\
\ \ \mbox{for all}\ t\in\mathbb{R},$

and

(2.2)
$\|(A(t)-\omega)R(\lambda,A(t)-\omega)\,[R(\omega,A(t))-R(\omega,A(s))]\|\leq
L\,\frac{|t-s|^{\mu}}{|\lambda|^{\nu}}$

for $t,s\in\mathbb{R}$,
$\displaystyle\lambda\in\Sigma_{\theta}:=\\{\lambda\in\mathbb{C}\setminus\\{0\\}:|\arg\lambda|\leq\theta\\}$.

For a given family of linear operators $A(t)$, the existence of an evolution
family associated with it is not always guaranteed. However, if $A(t)$
satisfies Acquistapace-Terreni, then there exists a unique evolution family

${\mathcal{U}}=\\{U(t,s):t,s\in\mathbb{R}\ \ \mbox{such that}\ \ t\geq s\\}$

on $\mathbb{X}$ associated with $A(t)$ such that $U(t,s)\mathbb{X}\subseteq
D(A(t))$ for all $t,s\in\mathbb{R}$ with $t\geq s$, and

  1. (a)

$U(t,s)U(s,r)=U(t,r)$ for $t,s\in\mathbb{R}$ such that $t\geq s\geq s$;

  2. (b)

$U(t,t)=I$ for $t\in\mathbb{R}$ where $I$ is the identity operator of
$\mathbb{X}$;

  3. (c)

$(t,s)\mapsto U(t,s)\in B(\mathbb{X})$ is continuous for $t>s$;

  4. (d)

$U(\cdot,s)\in C^{1}((s,\infty),B(\mathbb{X}))$, $\displaystyle\frac{\partial
U}{\partial t}(t,s)=A(t)U(t,s)$ and

$\displaystyle\left\|A(t)^{k}U(t,s)\right\|$ $\displaystyle\leq K\,(t-s)^{-k}$

for $0<t-s\leq 1$ and $k=0,1$.

######  Definition 2.2.

An evolution family ${\mathcal{U}}=\\{U(t,s):t,s\in\mathbb{R}\ \ \mbox{such
that}\ \ t\geq s\\}$ is said to have an exponential dichotomy (or is
hyperbolic) if there are projections $P(t)$ ($t\in\mathbb{R}$) that are
uniformly bounded and strongly continuous in $t$ and constants $\delta>0$ and
$N\geq 1$ such that

  1. (e)

$U(t,s)P(s)=P(t)U(t,s)$;

  2. (f)

the restriction $U_{Q}(t,s):Q(s)\mathbb{X}\to Q(t)\mathbb{X}$ of $U(t,s)$ is
invertible (we then set $\widetilde{U}_{Q}(s,t):=U_{Q}(t,s)^{-1}$); and

  3. (g)

$\left\|U(t,s)P(s)\right\|\leq Ne^{-\delta(t-s)}$ and
$\left\|\widetilde{U}_{Q}(s,t)Q(t)\right\|\leq Ne^{-\delta(t-s)}$ for $t\geq
s$ and $t,s\in\mathbb{R}$.

This setting requires some estimates related to
${\mathcal{U}}=\\{U(t,s)\\}_{t\geq s}$. For that, we introduce the
interpolation spaces for $A(t)$.

Let $A$ be a sectorial operator on $\mathbb{X}$ (in Definition 2.1, replace
$A(t)$ with $A$) and let $\alpha\in(0,1)$. Define the real interpolation space

$\displaystyle\mathbb{X}^{A}_{\alpha}:=\Big{\\{}x\in\mathbb{X}:\|x\|^{A}_{\alpha}:=\sup\nolimits_{r>0}\|r^{\alpha}(A-\omega)R(r,A-\omega)x\|<\infty\Big{\\}},$

which, by the way, is a Banach space when endowed with the norm
$\|\cdot\|^{A}_{\alpha}$. For convenience we further write

$\mathbb{X}_{0}^{A}:=\mathbb{X},\ \|x\|_{0}^{A}:=\|x\|,\
\mathbb{X}_{1}^{A}:=D(A)$

and $\|x\|^{A}_{1}:=\|(\omega-A)x\|$. Moreover, let
$\hat{\mathbb{X}}^{A}:=\overline{D(A)}$ of $\mathbb{X}$.

######  Definition 2.3.

Given a family of linear operators $A(t)$ for $t\in\mathbb{R}$ satisfying the
Acquistapace-Terreni conditions, we set
$\mathbb{X}^{t}_{\alpha}:=\mathbb{X}_{\alpha}^{A(t)}$ and
$\hat{\mathbb{X}}^{t}:=\hat{\mathbb{X}}^{A(t)}$ for $0\leq\alpha\leq 1$ and
$t\in\mathbb{R}$, with the corresponding norms.

######  Proposition 2.4.

[3] For $x\in\mathbb{X}$, $0\leq\alpha\leq 1$ and $t>s,$ the following hold:

  1. (i)

There is a constant $c(\alpha),$ such that

(2.3) $\|U(t,s)P(s)x\|_{\alpha}^{t}\leq
c(\alpha)e^{-\frac{\delta}{2}(t-s)}(t-s)^{-\alpha}\|x\|.$

  2. (ii)

There is a constant $m(\alpha),$ such that

(2.4) $\|\widetilde{U}_{Q}(s,t)Q(t)x\|_{\alpha}^{s}\leq
m(\alpha)e^{-\delta(t-s)}\|x\|,\qquad t\leq s.$

###  2.2. Properties of Weights

This subsection is similar to the one given in Diagana [10] except that most
of all the proofs will be omitted.

Let $\mathbb{U}$ denote the collection of functions (weights)
$\rho:\mathbb{R}\mapsto(0,\infty)$, which are locally integrable over
$\mathbb{R}$ such that $\rho>0$ almost everywhere.

In the rest of the paper, if $\mu\in\mathbb{U}$, $T>0$, and $a\in\mathbb{R}$,
we then set $Q_{T}:=[-T,T]$, $Q_{T}+a:=[-T+a,T+a]$, and

$\mu(Q_{T}):=\int_{Q_{T}}\mu(x)dx.$

Here as in the particular case when $\mu(x)=1$ for each $x\in\mathbb{R}$, we
are exclusively interested in the weights $\mu$ for which,

$\displaystyle\lim_{T\to\infty}\mu(Q_{T})=\infty.$

Consequently, we define the space of weights $\mathbb{U}_{\infty}$ by

$\mathbb{U}_{\infty}:=\Bigg{\\{}\mu\in\mathbb{U}:\
\inf_{x\in\mathbb{R}}\mu(x)=\mu_{0}>0\ \ \mbox{and}\ \
\lim_{T\to\infty}\mu(Q_{T})=\infty\Bigg{\\}}.$

In addition to the above, we define the set of weights $\mathbb{U}_{B}$ by

$\displaystyle\mathbb{U}_{B}:=\Bigg{\\{}\mu\in\mathbb{U}_{\infty}:\
\sup_{x\in\mathbb{R}}\mu(x)=\mu_{1}<\infty\Bigg{\\}}.$

We also need the following set of weights, which makes the spaces of weighted
pseudo-almost periodic functions translation-invariant,

$\displaystyle\mathbb{U}_{\infty}^{\rm
Inv}:=\Bigg{\\{}\mu\in\mathbb{U}_{\infty}:\
\lim_{x\to\infty}\frac{\mu(x+\tau)}{\mu(x)}<\infty\ \ \mbox{and}\ \
\lim_{T\to\infty}\frac{\mu(Q_{T+\tau})}{\mu(Q_{T})}<\infty\ \mbox{for all}\
\tau\in\mathbb{R}\Bigg{\\}}.$

Let $\mathbb{U}_{\infty}^{c}$ denote the collection of all continuous
functions (weights) $\mu:\mathbb{R}\mapsto(0,\infty)$ such that $\mu>0$ almost
everywhere.

Define

$\displaystyle\mathbb{U}_{\infty}^{s}:=\Bigg{\\{}\mu\in\mathbb{U}_{\infty}^{c}\cap\mathbb{U}_{\infty}:\
\lim_{x\to\infty}\frac{\mu(x+\tau)}{\mu(x)}<\infty\ \ \mbox{for all}\
\tau\in\mathbb{R}\Bigg{\\}}.$

######  Lemma 2.5.

[10, Diagana] The inclusion
$\mathbb{U}_{\infty}^{s}\subset\mathbb{U}_{\infty}^{\rm Inv}$ holds.

######  Definition 2.6.

Let $\mu,\nu\in\mathbb{U}_{\infty}$. One says that $\mu$ is equivalent to
$\nu$ and denote it $\mu\prec\nu$, if
$\displaystyle\frac{\mu}{\nu}\in\mathbb{U}_{B}.$

Let $\mu,\nu,\gamma\in\mathbb{U}_{\infty}.$ It is clear that $\mu\prec\mu$
(reflexivity); if $\mu\prec\nu$, then $\nu\prec\mu$ (symmetry); and if
$\mu\prec\nu$ and $\nu\prec\gamma$, then $\mu\prec\gamma$ (transitivity).
Therefore, $\prec$ is a binary equivalence relation on $\mathbb{U}_{\infty}$.

We have

######  Proposition 2.7.

Let $\mu,\nu\in\mathbb{U}_{\infty}^{\rm Inv}$. If $\mu\prec\nu$, then
$\sigma=\mu+\nu\in\mathbb{U}_{\infty}^{\rm Inv}$.

######  Proposition 2.8.

Let $\mu,\nu\in\mathbb{U}_{\infty}^{s}$. Then their product
$\pi=\mu\nu\in\mathbb{U}_{\infty}^{s}$. Moreover, if $\mu\prec\nu$, then
$\sigma:=\mu+\nu\in\mathbb{U}_{\infty}^{s}$.

The next theorem describes all the nonconstant polynomials belonging to the
set of weights $\mathbb{U}_{\infty}$.

######  Theorem 2.9.

[10, Diagana] If $\mu\in\mathbb{U}_{\infty}$ is a nonconstant polynomial of
degree $N$, then $N$ is necessarily even ($N=2n^{\prime}$ for some nonnegative
integer $n^{\prime}$). More precisely, $\mu$ can be written in the following
form:

$\mu(x)=a\prod_{k=0}^{n}(x^{2}+a_{k}x+b_{k})^{m_{k}}$

where $a>0$ is a constant, $a_{k}$ and $b_{k}$ are some real numbers
satisfying $a_{k}^{2}-4b_{k}<0$, and $m_{k}$ are nonnegative integers for
$k=0,...,n$. Furthermore, the weight $\mu$ given above belongs to
$\mathbb{U}_{\infty}^{s}$.

###  2.3. Doubly-Weighted Pseudo-Almost Periodic Functions

######  Definition 2.10.

A function $f\in C(\mathbb{R},\mathbb{X})$ is called (Bohr) almost periodic if
for each $\varepsilon>0$ there exists $l(\varepsilon)>0$ such that every
interval of length $l(\varepsilon)$ contains a number $\tau$ with the property
that

$\|f(t+\tau)-f(t)\|<\varepsilon\ \ \mbox{for each}\ \ t\in\mathbb{R}.$

The collection of all almost periodic functions will be denoted
$AP(\mathbb{X})$.

######  Definition 2.11.

A function $F\in C(\mathbb{R}\times\mathbb{Y},\mathbb{X})$ is called (Bohr)
almost periodic in $t\in\mathbb{R}$ uniformly in $y\in\mathbb{Y}$ if for each
$\varepsilon>0$ and any compact $K\subset\mathbb{Y}$ there exists
$l(\varepsilon)$ such that every interval of length $l(\varepsilon)$ contains
a number $\tau$ with the property that

$\|F(t+\tau,y)-F(t,y)\|<\varepsilon\ \ \mbox{for each}\ \ t\in\mathbb{R},\ \
y\in K.$

The collection of those functions is denoted by $AP(\mathbb{Y},\mathbb{X})$.

If $\mu,\nu\in\mathbb{U}_{\infty}$, we then define

$PAP_{0}(\mathbb{X},\mu,\nu):=\Bigg{\\{}f\in BC(\mathbb{R},\mathbb{X}):\ \
\lim_{T\to\infty}\displaystyle{\frac{1}{\mu(Q_{T})}}\int_{Q_{T}}\left\|f(\sigma)\right\|\,\nu(\sigma)\,d\sigma=0\Bigg{\\}}.$

Similarly, we define $PAP_{0}(\mathbb{Y},\mathbb{X},\mu,\nu)$ as the
collection of jointly continuous functions
$F:\mathbb{R}\times\mathbb{Y}\mapsto\mathbb{X}$ such that $F(\cdot,y)$ is
bounded for each $y\in\mathbb{Y}$ and

$\lim_{T\to\infty}\displaystyle{\frac{1}{\mu(Q_{T})}}\left\\{\int_{Q_{T}}\|F(s,y)\|\,\nu(s)\,ds\right\\}=0$

uniformly in $y\in\mathbb{Y}$.

######  Definition 2.12.

Let $\mu,\nu\in\mathbb{U}_{\infty}$. A function $f\in
C(\mathbb{R},\mathbb{X})$ is called doubly-weighted pseudo-almost periodic if
it can be expressed as $f=g+\phi,$ where $g\in AP(\mathbb{X})$ and $\phi\in
PAP_{0}(\mathbb{X},\mu,\nu)$. The collection of such functions will be denoted
by $PAP({\mathbb{X}},\mu,\nu)$.

######  Definition 2.13.

Let $\mu,\nu\in\mathbb{U}_{\infty}$. A function $F\in
C(\mathbb{R}\times\mathbb{Y},\mathbb{X})$ is called doubly-weighted pseudo-
almost periodic if it can be expressed as $F=G+\Phi,$ where $G\in
AP(\mathbb{Y},\mathbb{X})$ and $\Phi\in
PAP_{0}(\mathbb{Y},\mathbb{X},\mu,\nu)$. The collection of such functions will
be denoted by $PAP(\mathbb{Y},{\mathbb{X}},\mu,\nu)$.

######  Proposition 2.14.

[10, Diagana] Let $\mu\in\mathbb{U}_{\infty}$ and let
$\nu\in\mathbb{U}_{\infty}^{\rm Inv}$ such that

(2.5)
$\displaystyle\displaystyle\sup_{T>0}\Bigg{[}\displaystyle{\frac{\nu(Q_{T})}{\mu(Q_{T})}}\Bigg{]}<\infty.$

Let $f\in PAP_{0}(\mathbb{R},\mu,\nu)$ and let $g\in L^{1}(\mathbb{R})$.
Suppose

(2.6)
$\displaystyle\displaystyle\lim_{T\to\infty}\Bigg{[}\displaystyle{\frac{\mu(Q_{T+|\tau|})}{\mu(Q_{T})}}\Bigg{]}<\infty\
\ \mbox{for all}\ \ \tau\in\mathbb{R}.$

Then $f\ast g$, the convolution of $f$ and $g$ on $\mathbb{R}$, belongs to
$PAP_{0}(\mathbb{R},\mu,\nu)$.

###### Proof.

It is clear that if $f\in PAP_{0}(\mathbb{R},\mu,\nu)$ and $g\in
L^{1}(\mathbb{R})$, then their convolution $f\ast g\in
BC(\mathbb{R},\mathbb{R})$. Now setting

$J(T,\mu,\nu):=\displaystyle{\frac{1}{\mu(Q_{T})}}\int_{Q_{T}}\int_{-\infty}^{+\infty}|f(t-s)|\,|g(s)|\nu(t)\,dsdt$

it follows that

$\displaystyle\displaystyle{\frac{1}{\mu(Q_{T})}}\int_{Q_{T}}|(f\ast
g)(t)|\nu(t)dt$ $\displaystyle\leq$ $\displaystyle J(T,\mu,\nu)$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{+\infty}|g(s)|\left(\displaystyle{\frac{1}{\mu(Q_{T})}}\int_{Q_{T}}|f(t-s)|\nu(t)dt\right)ds$
$\displaystyle=$ $\displaystyle\int_{-\infty}^{+\infty}|g(s)|\phi_{T}(s)ds,$

where

$\displaystyle\displaystyle\phi_{T}(s)$ $\displaystyle=$
$\displaystyle\frac{1}{\mu(Q_{T})}\int_{Q_{T}}|f(t-s)|\nu(t)dt$
$\displaystyle=$
$\displaystyle\frac{\mu(Q_{T+|s|})}{\mu(Q_{T})}\,.\,\frac{1}{\mu(Q_{T+|s|})}\int_{Q_{T}}|f(t-s)|\nu(t)dt$
$\displaystyle\leq$
$\displaystyle\frac{\mu(Q_{T+|s|})}{\mu(Q_{T})}\,.\,\frac{1}{\mu(Q_{T+|s|})}\int_{Q_{T+|s|}}|f(t)|\nu(t+s)dt.$

Using the fact that $\nu\in\mathbb{U}_{\infty}^{\rm Inv}$ and Eq. (2.6), one
can easily see that $\phi_{T}(s)\mapsto 0$ as $T\mapsto\infty$ for all
$s\in\mathbb{R}$. Next, since $\phi_{T}$ is bounded, i.e.,

$|\phi_{T}(s)|\leq\|f\|_{\infty}\,.\,\displaystyle\sup_{T>0}\displaystyle{\frac{\nu(Q_{T})}{\mu(Q_{T})}}<\infty$

and $g\in L^{1}(\mathbb{R})$, using the Lebesgue Dominated Convergence Theorem
it follows that

$\lim_{T\to\infty}\left\\{\int_{-\infty}^{+\infty}|g(s)|\phi_{T}(s)ds\right\\}=0,$

and hence $f\ast g\in PAP_{0}(\mathbb{R},\mu,\nu)$. ∎

######  Corollary 2.15.

Let $\mu\in\mathbb{U}_{\infty}$ and let $\nu\in\mathbb{U}_{\infty}^{\rm Inv}$
such that Eqs. (2.5) – (2.6) hold. If $f\in PAP(\mathbb{R},\mu,\nu)$ and $g\in
L^{1}(\mathbb{R})$, then $f\ast g$ belongs to $PAP(\mathbb{R},\mu,\nu)$.

######  Theorem 2.16.

[10, Diagana] If $\mu,\nu\in\mathbb{U}_{\infty}$ such that the space
$PAP_{0}(\mathbb{X},\mu,\nu)$ is translation-invariant and if

(2.7)
$\displaystyle\displaystyle\inf_{T>0}\Bigg{[}\displaystyle{\frac{\nu(Q_{T})}{\mu(Q_{T})}}\Bigg{]}=\delta_{0}>0,$

then the decomposition of doubly-weighted pseudo-almost periodic functions is
unique.

######  Theorem 2.17.

[10, Diagana] Let $\mu,\nu\in\mathbb{U}_{\infty}$ and let $f\in
PAP(\mathbb{Y},\mathbb{X},\mu,\nu)$ satisfying the Lipschitz condition

$\|f(t,u)-f(t,v)\|\leq L\,.\,\|u-v\|_{\mathbb{Y}}\ \ \mbox{for all}\ \
u,v\in\mathbb{Y},\ t\in\mathbb{R}.$

If $h\in PAP(\mathbb{Y},\mu,\nu)$, then $f(\cdot,h(\cdot))\in
PAP(\mathbb{X},\mu,\nu)$.

##  3\. Existence of a Doubly-Weighted Mean for Almost Periodic Functions

Let $\mu,\nu\in\mathbb{U}_{\infty}$. If $f:\mathbb{R}\mapsto\mathbb{X}$ is a
bounded continuous function, we define its doubly-weighted mean, if the limit
exists, by

${\mathcal{M}}(f,\mu,\nu):=\lim_{T\to\infty}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}f(t)\nu(t)dt.$

It is well-known that if $f\in AP(\mathbb{X})$, then its mean defined by

${\mathcal{M}}(f):=\lim_{T\to\infty}\frac{1}{2T}\int_{Q_{T}}f(t)dt$

exists [6]. Consequently, for every $\lambda\in\mathbb{R}$, the following
limit

$a(f,\lambda):=\lim_{T\to\infty}\frac{1}{2T}\int_{Q_{T}}f(t)e^{-i\lambda t}dt$

exists and is called the Bohr transform of $f$.

It is well-known that $a(f,\lambda)$ is nonzero at most at countably many
points [6]. The set defined by

$\sigma_{b}(f):=\Big{\\{}\lambda\in\mathbb{R}:a(f,\lambda)\not=0\Big{\\}}$

is called the Bohr spectrum of $f$ [19].

######  Theorem 3.1.

(Approximation Theorem) [17, 19] Let $f\in AP(\mathbb{X})$. Then for every
$\varepsilon>0$ there exists a trigonometric polynomial

$P_{\varepsilon}(t)=\sum_{k=1}^{n}a_{k}e^{i\lambda_{k}t}$

where $a_{k}\in\mathbb{X}$ and $\lambda_{k}\in\sigma_{b}(f)$ such that
$\|f(t)-P_{\varepsilon}(t)\|<\varepsilon$ for all $t\in\mathbb{R}$.

In Liang et al. [18], the original question which consists of the existence of
a weighted mean for almost periodic functions was raised. In particular, Liang
et al. have shown through an example that there exist weights for which a
weighted mean for almost periodic functions may not exist. In this section we
investigate the broader question, which consists of the existence of a doubly-
weighted mean for almost periodic functions. Namely, we give some sufficient
conditions, which do guarantee the existence of a doubly-weighted mean for
almost periodic functions. Moreover, under those conditions, it will be shown
that the doubly-weighted mean and the classical (Bohr) mean are proportional
(Theorem 3.2). Further, it will be shown that if the doubly-weighted Bohr
spectrum of an almost periodic function exists, then it is either empty or
coincides with the Bohr spectrum of that function.

We have

######  Theorem 3.2.

Let $\mu,\nu\in\mathbb{U}_{\infty}$ and suppose that
$\displaystyle\lim_{T\to\infty}\frac{\nu(Q_{T})}{\mu(Q_{T})}=\theta_{\mu\nu}$.
If $f:\mathbb{R}\mapsto\mathbb{X}$ is an almost periodic function such that

(3.1)
$\displaystyle\lim_{T\to\infty}\Bigg{|}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}e^{i\lambda
t}\nu(t)dt\Bigg{|}=0$

for all $0\not=\lambda\in\sigma_{b}(f)$, then the doubly-weighted mean of $f$,

${\mathcal{M}}(f,\mu,\nu)=\lim_{T\to\infty}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}f(t)\nu(t)dt$

exists. Furthermore,
${\mathcal{M}}(f,\mu,\nu)=\theta_{\mu\nu}{\mathcal{M}}(f)$.

###### Proof.

If $f$ is a trigonometric polynomial, say, $\displaystyle
f(t)=\sum_{k=0}^{n}a_{k}e^{i\lambda_{k}t}$ where $a_{k}\in\mathbb{X}-\\{0\\}$
and $\lambda_{k}\in\mathbb{R}$ for $k=1,2,...,n$, then
$\sigma_{b}(f)=\\{\lambda_{k}:\ k=1,2,...,n\\}$. Moreover,

$\displaystyle\frac{1}{\mu(Q_{T})}\int_{Q_{T}}f(t)\nu(t)dt$ $\displaystyle=$
$\displaystyle
a_{0}\frac{\nu(Q_{T})}{\mu(Q_{T})}+\frac{1}{\mu(Q_{T})}\int_{Q_{T}}\Big{[}\sum_{k=1}^{n}a_{k}e^{i\lambda_{k}t}\Big{]}\nu(t)dt$
$\displaystyle=$ $\displaystyle
a_{0}\frac{\nu(Q_{T})}{\mu(Q_{T})}+\sum_{k=1}^{n}a_{k}\Big{[}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}e^{i\lambda_{k}t}\nu(t)dt\Big{]}$

and hence

$\displaystyle\left\|\frac{1}{\mu(Q_{T})}\int_{Q_{T}}f(t)\nu(t)dt-
a_{0}\frac{\nu(Q_{T})}{\mu(Q_{T})}\right\|$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{n}\left\|a_{k}\right\|\Big{|}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}e^{i\lambda_{k}t}\nu(t)dt\Big{|}$

which by Eq. (3.1) yields

$\left\|\frac{1}{\mu(Q_{T})}\int_{Q_{T}}f(t)\nu(t)dt-
a_{0}\theta_{\mu\nu}\right\|\to 0\ \ \mbox{as}\ \ T\to\infty$

and therefore
${\mathcal{M}}(f,\mu,\nu)=a_{0}\theta_{\mu\nu}=\theta_{\mu\nu}M(f)$.

If in the finite sequence of $\lambda_{k}$ there exist $\lambda_{n_{k}}=0$ for
$k=1,2,...l$ with $a_{m}\in\mathbb{X}-\\{0\\}$ for all $m\not=n_{k}$
($k=1,2,...,l$), it can be easily shown that

$\displaystyle{\mathcal{M}}(f,\mu,\nu)=\theta_{\mu\nu}\sum_{k=1}^{l}a_{n_{k}}=\theta_{\mu\nu}M(f).$

Now if $f:\mathbb{R}\mapsto\mathbb{X}$ is an arbitrary almost periodic
function, then for every $\varepsilon>0$ there exists a trigonometric
polynomial (Theorem 3.1) $P_{\varepsilon}$ defined by

$P_{\varepsilon}(t)=\sum_{k=1}^{n}a_{k}e^{i\lambda_{k}t}$

where $a_{k}\in\mathbb{X}$ and $\lambda_{k}\in\sigma_{b}(f)$ such that

(3.2) $\displaystyle\left\|f(t)-P_{\varepsilon}(t)\right\|<\varepsilon$

for all $t\in\mathbb{R}$.

Proceeding as in Bohr [6] it follows that there exists $T_{0}$ such that for
all $T_{1},T_{2}>T_{0}$,

$\displaystyle\Big{\|}\frac{1}{\mu(Q_{T_{1}})}\int_{Q_{T_{1}}}P_{\varepsilon}(t)\nu(t)dt-\frac{1}{\mu(Q_{T_{2}})}\int_{Q_{T_{2}}}P_{\varepsilon}(t)\nu(t)dt\Big{\|}=\theta_{\mu\nu}\Big{\|}M(P_{\varepsilon})-M(P_{\varepsilon})\Big{\|}=0<\varepsilon.$

In view of the above it follows that for all $T_{1},T_{2}>T_{0}$,

$\displaystyle\noindent\Big{\|}\frac{1}{\mu(Q_{T_{1}})}\int_{Q_{T_{1}}}f(t)\nu(t)dt-\frac{1}{\mu(Q_{T_{2}})}\int_{Q_{T_{2}}}f(t)\nu(t)dt\Big{\|}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\mu(Q_{T_{1}})}\int_{Q_{T_{1}}}\|f(t)-P_{\varepsilon}(t)\|\nu(t)dt$
$\displaystyle+\Big{\|}\frac{1}{\mu(Q_{T_{1}})}\int_{Q_{T_{1}}}P_{\varepsilon}(t)\nu(t)dt-\frac{1}{\mu(Q_{T_{2}})}\int_{Q_{T_{2}}}P_{\varepsilon}(t)\nu(t)dt\Big{\|}$
$\displaystyle+\frac{1}{\mu(Q_{T_{2}})}\int_{Q_{T_{2}}}\|f(t)-P_{\varepsilon}(t)\|\nu(t)dt<3\varepsilon.$

∎

######  Example 3.3.

Fix a natural number $N>1$. Let $\mu(t)=e^{|t|}$ and $\nu(t)=(1+|t|)^{N}$ for
all $t\in\mathbb{R}$, which yields $\theta_{\mu\nu}=0$. If
$\varphi:\mathbb{R}\mapsto\mathbb{X}$ is a (nonconstant) almost periodic
function, then according to the previous theorem, its doubly-weighted mean
${\mathcal{M}}(\varphi,\mu,\nu)$ exists. Moreover,

$\lim_{T\to\infty}\frac{1}{2(e^{T}-1)}\int_{Q_{T}}f(t)(1+|t|)^{N}dt=0.\lim_{T\to\infty}\frac{1}{2T}\int_{Q_{T}}f(t)dt=0.$

Consider the set of weights $\mathbb{U}_{\infty}^{0}$ defined by

$\mathbb{U}_{\infty}^{0}=\Bigg{\\{}\mu\in\mathbb{U}_{\infty}:D_{\tau}:=\lim_{|t|\to\infty}\frac{\mu(Q_{t+\tau})}{\mu(Q_{t})}<\infty\
\ \mbox{for all}\ \ \tau\in\mathbb{R}\Bigg{\\}}.$

Setting, $\displaystyle
C_{\tau}=\lim_{|t|\to\infty}\frac{\mu(Q_{t}+\tau)}{\mu(Q_{t})}$, one can
easily see that $C_{\tau}\leq D_{\tau}<\infty$ for all $\tau\in\mathbb{R}$.

######  Corollary 3.4.

Fix $\mu,\nu\in\mathbb{U}_{\infty}^{0}$ and suppose that
$\displaystyle\lim_{T\to\infty}\frac{\nu(Q_{T})}{\mu(Q_{T})}=\theta_{\mu\nu}$.
If $f:\mathbb{R}\mapsto\mathbb{X}$ is an almost periodic function such that
Eq. (3.1) holds, then

(3.3)
$\displaystyle{\mathcal{M}}(f_{a},\mu,\nu_{a})=C_{-a}\theta_{\mu\nu}{\mathcal{M}}(f)=C_{-a}{\mathcal{M}}(f,\mu,\nu)$

uniformly in $a\in\mathbb{R}$, where

${\mathcal{M}}(f_{b},\mu,\nu_{b})=\lim_{T\to\infty}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}f_{b}(t)\nu_{b}(t)dt=\lim_{T\to\infty}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}f(t+b)\nu(t+b)dt$

for each $b\in\mathbb{R}$.

###### Proof.

Clearly, the existence of ${\mathcal{M}}(f,\mu,\nu)$ is guaranteed by Theorem
3.2. Without lost of generality, suppose $a>0$. Now since $f\in
AP(\mathbb{X})$ it follows that $f_{a}:t\mapsto f(t+a)$ belongs to
$AP(\mathbb{X})$. Moreover, the weight $\nu_{a}$ defined by
$\nu_{a}(t)=\nu(t+a)$ for all $t\in\mathbb{R}$ belongs to
$\mathbb{U}_{\infty}^{0}$.

Now

$\Big{|}\int_{Q_{T}}e^{i\lambda
t}\nu_{a}(t)dt\Big{|}=\Big{|}\int_{Q_{T}-a}e^{i\lambda(t-a)}\nu(t)dt\Big{|}=\Big{|}\int_{Q_{T}-a}e^{i\lambda
t}\nu(t)dt\Big{|}\leq\Big{|}\int_{Q_{T+a}}e^{i\lambda t}\nu(t)dt\Big{|}$

and hence

$\displaystyle\lim_{T\to\infty}\Big{|}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}e^{i\lambda
t}\nu_{a}(t)dt\Big{|}$ $\displaystyle=$
$\displaystyle\lim_{T\to\infty}\Big{|}\frac{1}{\mu(Q_{T})}\int_{Q_{T}-a}e^{i\lambda
t}\nu(t)dt\Big{|}$ $\displaystyle\leq$
$\displaystyle\lim_{T\to\infty}\Big{|}\frac{1}{\mu(Q_{T})}\int_{Q_{T+a}}e^{i\lambda
t}\nu(t)dt\Big{|}$ $\displaystyle=$
$\displaystyle\lim_{T\to\infty}\Big{|}\frac{\mu(Q_{T+a})}{\mu(Q_{T})}\frac{1}{\mu(Q_{T+a})}\int_{Q_{T+a}}e^{i\lambda
t}\nu(t)dt\Big{|}$ $\displaystyle=$ $\displaystyle
D_{a}\lim_{T\to\infty}\Big{|}\frac{1}{\mu(Q_{T+a})}\int_{Q_{T+a}}e^{i\lambda
t}\nu(t)dt\Big{|}$ $\displaystyle=$ $\displaystyle 0.$

Now

$\displaystyle\lim_{T\to\infty}\frac{\nu_{a}(Q_{T})}{\mu(Q_{T})}=C_{-a}\theta_{\mu\nu}.$

Using Theorem 3.2 it follows that for every $\varphi\in AP(\mathbb{X})$,

${\mathcal{M}}(\varphi_{a},\mu,\nu_{a})=\lim_{T\to\infty}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}\varphi_{a}(t)\nu_{a}(t)dt$

exists. Furthermore,
${\mathcal{M}}(\varphi_{a},\mu,\nu_{a})=C_{-a}\theta_{\mu\nu}{\mathcal{M}}(\varphi_{a})$
for all $a\in\mathbb{R}$. In particular,
${\mathcal{M}}(f_{a},\mu,\nu_{a})=C_{-a}\theta_{\mu\nu}{\mathcal{M}}(f_{a})$
uniformly in $a\in\mathbb{R}$. Now from Bohr [6],
${\mathcal{M}}(f_{a})={\mathcal{M}}(f)$ uniformly in $a\in\mathbb{R}$, which
completes the proof.

∎

######  Definition 3.5.

Fix $\mu,\nu\in\mathbb{U}_{\infty}$ and suppose that
$\displaystyle\lim_{T\to\infty}\frac{\nu(Q_{T})}{\mu(Q_{T})}=\theta_{\mu\nu}$.
If $f:\mathbb{R}\mapsto\mathbb{X}$ is an almost periodic function such that
Eq. (3.1) holds, we then define its doubly-weighted Bohr transform as

$\widehat{a}_{\mu\nu}(f)(\lambda):=\lim_{T\to\infty}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}f(t)e^{-i\lambda
t}\nu(t)dt\ \ \mbox{for all}\ \ \lambda\in\mathbb{R}.$

Now since $t\mapsto g_{\lambda}(t):=f(t)e^{-i\lambda t}\in AP(\mathbb{X})$ it
follows that

$\widehat{a}_{\mu\nu}(f)(\lambda)=\theta_{\mu\nu}{\mathcal{M}}(f(\cdot)e^{-i\lambda\cdot})=\theta_{\mu\nu}a(f,\lambda).$

That is, under Eq. (3.1),

$\widehat{a}_{\mu\nu}(f)(\lambda):=\lim_{T\to\infty}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}f(t)e^{-i\lambda
t}\nu(t)dt=\theta_{\mu\nu}\lim_{T\to\infty}\frac{1}{2T}\int_{Q_{T}}f(t)e^{-i\omega
t}dt=\theta_{\mu\nu}a(f,\lambda)$

for all $\lambda\in\mathbb{R}.$

In summary, there are two possibilities for the doubly-weighted Bohr spectrum
of an almost periodic function. Indeed,

1) If
$\displaystyle\lim_{T\to\infty}\frac{\nu(Q_{T})}{\mu(Q_{T})}=\theta_{\mu\nu}=0$,
then $\widehat{a}_{\mu\nu}(f)(\lambda)=\theta_{\mu\nu}a(f,\lambda)=0$ for all
$\lambda\in\mathbb{R}$. In that event, the doubly-weighted Bohr spectrum of
$f$ is

$\sigma_{b}^{\mu\nu}(f):=\Big{\\{}\lambda\in\mathbb{R}:\widehat{a}_{\mu\nu}(f)(\lambda)\not=0\Big{\\}}=\emptyset.$

2) If
$\displaystyle\lim_{T\to\infty}\frac{\nu(Q_{T})}{\mu(Q_{T})}=\theta_{\mu\nu}\not=0$,
then $\widehat{a}_{\mu\nu}(f)(\lambda)=\theta_{\mu\nu}a(f,\lambda)$ exists for
all $\lambda\in\mathbb{R}$ and is nonzero at most at countably many points. In
that event, the doubly-weighted Bohr spectrum of $f$ is

$\sigma_{b}^{\mu\nu}(f):=\Big{\\{}\lambda\in\mathbb{R}:\widehat{a}_{\mu\nu}(f)(\lambda)\not=0\Big{\\}}=\Big{\\{}\lambda\in\mathbb{R}:a(f,\lambda)\not=0\Big{\\}},$

that is, $\sigma_{b}^{\mu\nu}(f)=\sigma_{b}(f).$ In particular,
$\sigma_{b}^{\mu\mu}(f)=\sigma_{b}(f).$

##  4\. Existence of Doubly-Weighted Pseudo-Almost Periodic Solutions to Some
Differential Equations

In this Section, we fix two weights $\mu,\nu\in\mathbb{U}_{\infty}$ such that
$PAP(\mathbb{X},\mu,\nu)$ is translation-invariant and Eq. (2.7) holds. Under
these assumptions, it can be easily shown that $PAP(\mathbb{X},\mu,\nu)$ is a
Banach space when equipped with the sup norm.

In what follows, we denote by $\Gamma_{1}$ and $\Gamma_{2}$, the nonlinear
integral operators defined by

$(\Gamma_{1}u)(t):=\int_{-\infty}^{t}U(t,s)P(s)g(s,u(s))ds,\ \mbox{and}$

and

$(\Gamma_{2}u)(t):=\int_{t}^{\infty}U_{Q}(t,s)Q(s)g(s,u(s))ds.$

To study the existence of doubly-weighted pseudo-almost periodic solutions to
Eq. (1.1) we will assume that the following assumptions hold:

  1. (H.1)

The family of closed linear operators $A(t)$ for $t\in\mathbb{R}$ on
$\mathbb{X}$ with domain $D(A(t))$ (possibly not densely defined) satisfy
Acquistapace and Terreni conditions, that is, there exist constants
$\omega\in\mathbb{R}$, $\theta\in\Big{(}\frac{\pi}{2},\pi\Big{)}$, $L>0$ and
$\mu,\nu\in(0,1]$ with $\mu+\nu>1$ such that

$\Sigma_{\theta}\cup\Big{\\{}0\Big{\\}}\subset\rho\Big{(}A(t)-\omega\Big{)}\ni\lambda,\;\qquad\\\
\|R(\lambda,A(t)-\omega)\|\leq\frac{K}{1+|\lambda|}\ \ \ \mbox{for all}\
t\in\mathbb{R},$

and

$\|(A(t)-\omega)R(\lambda,A(t)-\omega)\,[R(\omega,A(t))-R(\omega,A(s))]\|\leq
L\,\frac{|t-s|^{\mu}}{|\lambda|^{\nu}}$

for $t,s\in\mathbb{R}$,
$\displaystyle\lambda\in\Sigma_{\theta}:=\\{\lambda\in\mathbb{C}\setminus\\{0\\}:|\arg\lambda|\leq\theta\\}$.

  2. (H.2)

The evolution family ${\mathcal{U}}=\\{U(t,s)\\}_{t\geq s}$ generated by
$A(\cdot)$ has an exponential dichotomy with constants $N,\delta>0$ and
dichotomy projections $P(t)$ for $t\in\mathbb{R}$.

  3. (H.3)

There exists $0\leq\alpha<1$ such that

$\mathbb{X}_{\alpha}^{t}=\mathbb{X}_{\alpha}$

for all $t\in\mathbb{R},$ with uniform equivalent norms.

  4. (H.4)

$R(\omega,A(\cdot))\in AP(B(\mathbb{X}_{\alpha}))$.

  5. (H.5)

The function $g:\mathbb{R}\times\mathbb{X}\mapsto\mathbb{X}$ belongs to
$PAP(\mathbb{X},\mathbb{X},\mu,\nu)$. Moreover, the functions $g$ are
uniformly Lipschitz with respect to the second argument in the following
sense: there exists $K>0$ such that

$\|g(t,u)-g(t,v)\|\leq K\|u-v\|$

for all $u,v\in\mathbb{X}$ and $t\in\mathbb{R}$.

If $0<\alpha<1$, then the nonnegative constant $k$ will denote the bounds of
the embedding $\mathbb{X}_{\alpha}\hookrightarrow\mathbb{X}$, that is,

$\|x\|\leq k\|x\|_{\alpha}$

for all $x\in\mathbb{X}_{\alpha}$.

To study the existence and uniqueness of doubly-weighted pseudo-almost
periodic solutions to Eq. (1.1) we first introduce the notion of mild
solution.

######  Definition 4.1.

A continuous function $u:\mathbb{R}\mapsto\mathbb{X}_{\alpha}$ is said to be a
mild solution to Eq. (1.1) if

$\displaystyle
u(t)=U(t,s)u(s)+\int_{s}^{t}U(t,s)P(s)g(s,u(s))ds-\int_{t}^{s}U(t,s)Q(s)g(s,u(s))ds$

for $t\geq s$ and for all $t,s\in\mathbb{R}$.

Under previous assumptions (H.1)-(H.5), it can be easily shown Eq. (1.1) has a
unique mild solution given by

$\displaystyle
u(t)=\int_{-\infty}^{t}U(t,s)P(s)g(s,u(s))ds-\int_{t}^{\infty}U_{Q}(t,s)Q(s)g(s,u(s))ds$

for each $t\in\mathbb{R}$.

######  Lemma 4.2.

Under assumptions (H.1)—(H.5), the integral operators $\Gamma_{1}$ and
$\Gamma_{2}$ defined above map $PAP(\mathbb{X}_{\alpha},\mu,\nu)$ into itself.

###### Proof.

Let $u\in PAP(\mathbb{X}_{\alpha},\mu,\nu)$. Setting $h(t)=g(t,u(t))$ and
using the theorem of composition of doubly-weighted pseudo-almost periodic
functions (Theorem 2.17) it follows that $h\in PAP(\mathbb{X},\mu,\nu)$. Now
write $h=\phi+\zeta$ where $\phi\in AP(\mathbb{X})$ and $\zeta\in
PAP_{0}(\mathbb{X},\mu,\nu)$. The nonlinear integral operator $\Gamma_{1}u$
can be rewritten as

$\displaystyle(\Gamma_{1}u)(t)$ $\displaystyle=$
$\displaystyle\int_{-\infty}^{t}U(t,s)P(s)\phi(s)ds+\int_{-\infty}^{t}U(t,s)P(s)\zeta(s)ds.$

Set

$\displaystyle\Phi(t)=\int_{-\infty}^{t}U(t,s)P(s)\phi(s)ds$

and

$\displaystyle\Psi(t)=\int_{-\infty}^{t}U(t,s)P(s)\zeta(s)ds$

for each $t\in\mathbb{R}$.

The next step consists of showing that $\Phi\in AP(\mathbb{X}_{\alpha})$ and
$\Psi\in PAP_{0}(\mathbb{X}_{\alpha},\mu,\nu)$. Obviously, $\Phi\in
AP(\mathbb{X}_{\alpha})$. Indeed, since $\phi\in AP(\mathbb{X})$, for every
$\varepsilon>0$ there exists $l(\varepsilon)>0$ such that for every interval
of length $l(\varepsilon)$ contains a $\tau$ with the property

$\|\phi(t+\tau)-\phi(t)\|<\varepsilon C\ \ \mbox{for each}\ t\in\mathbb{R},$

where $\displaystyle
C=\frac{\delta^{1-\alpha}}{c(\alpha)2^{1-\alpha}\Gamma(1-\alpha)}$ with
$\Gamma$ being the classical $\Gamma$ function.

Now

$\displaystyle\Phi(t+\tau)-\Phi(t)$ $\displaystyle=$
$\displaystyle\int_{-\infty}^{t+\tau}U(t+\tau,s)P(s)\phi(s)ds-\int_{-\infty}^{t}U(t,s)P(s)\phi(s)ds$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{t}U(t+\tau,s+\tau)P(s+\tau)\phi(s+\tau)ds-\int_{-\infty}^{t}U(t,s)P(s)\phi(s)ds$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{t}U(t+\tau,s+\tau)P(s+\tau)\phi(s+\tau)ds$
$\displaystyle-$
$\displaystyle\int_{-\infty}^{t}U(t+\tau,s+\tau)P(s+\tau)\phi(s)ds$
$\displaystyle+$
$\displaystyle\int_{-\infty}^{t}U(t+\tau,s+\tau)P(s+\tau)\phi(s)ds-\int_{-\infty}^{t}U(t,s)P(s)\phi(s)ds$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{t}U(t+\tau,s+\tau)P(s+\tau)\Big{(}\phi(s+\tau)-\phi(s)\Big{)}ds$
$\displaystyle+$
$\displaystyle\int_{-\infty}^{t}\Big{(}U(t+\tau,s+\tau)P(s+\tau)-U(t,s)P(s)\Big{)}\phi(s)ds.$

Using [4, 22] it follows that

$\left\|\int_{-\infty}^{t}\Big{[}U(t+\tau,s+\tau)P(s+\tau)-U(t,s)P(s)\Big{]}\phi(s)ds\right\|_{\alpha}\leq\frac{2\|\phi\|_{\infty}}{\delta}\varepsilon.$

Similarly, using (2.3), it follows that

$\left\|\int_{-\infty}^{t}U(t+\tau,s+\tau)P(s+\tau)(\phi(s+\tau)-\phi(s))ds\right\|_{\alpha}\leq\varepsilon.$

Therefore,

$\|\Phi(t+\tau)-\Phi(t)\|_{\alpha}<\Big{(}1+\frac{2\|\phi\|_{\infty}}{\delta}\Big{)}\varepsilon\
\ \mbox{for each}\ t\in\mathbb{R},$

and hence, $\Phi\in AP(\mathbb{X}_{\alpha})$.

To complete the proof for $\Gamma_{1}$, we have to show that $\Psi\in
PAP_{0}(\mathbb{X}_{\alpha},\mu,\nu)$. First, note that $s\mapsto\Psi(s)$ is a
bounded continuous function. It remains to show that

$\lim_{T\to\infty}\displaystyle{\frac{1}{\mu(Q_{T})}}\
\int_{Q_{T}}\|\Psi(t)\|_{\alpha}\nu(t)dt=0.$

Again using Eq. (2.3) it follows that

$\displaystyle\displaystyle\lim_{T\to\infty}\displaystyle{\frac{1}{\mu(Q_{T})}}\
\int_{Q_{T}}\|\Psi(t)\|_{\alpha}\nu(t)dt$ $\displaystyle\leq$
$\displaystyle\lim_{T\to\infty}\displaystyle{\frac{c(\alpha)}{\mu(Q_{T})}}\
\int_{Q_{T}}\int_{0}^{+\infty}s^{-\alpha}e^{-\frac{\delta}{2}s}\|\zeta(t-s)\|\nu(t)dsdt$
$\displaystyle\leq$ $\displaystyle\lim_{T\to\infty}\displaystyle
c(\alpha)\int_{0}^{+\infty}s^{-\alpha}e^{-\frac{\delta}{2}s}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}\|\zeta(t-s)\|\nu(t)dtds.$

Set

$\displaystyle\Gamma_{s}(T)=\frac{1}{\mu(Q_{T})}\int_{Q_{T}}\|\zeta(t-s)\|\nu(t)dt.$

Since $PAP_{0}(\mathbb{X},\mu,\nu)$ is assumed to be translation invariant and
that Eq. (2.7) holds, it follows that $t\mapsto\zeta(t-s)$ belongs to
$PAP_{0}(\mathbb{X},\mu,\nu)$ for each $s\in\mathbb{R}$, and hence

$\lim_{T\mapsto\infty}\frac{1}{\mu(Q_{T})}\int_{Q_{T}}\|\zeta(t-s)\|\nu(t)dt=0$

for each $s\in\mathbb{R}$.

One completes the proof by using the well-known Lebesgue Dominated Convergence
Theorem and the fact $\Gamma_{s}(T)\mapsto 0$ as $T\to\infty$ for each
$s\in\mathbb{R}$.

The proof for $\Gamma_{2}u(\cdot)$ is similar to that of $\Gamma_{1}u(\cdot)$.
However one makes use of Eq. (2.4) rather than Eq. (2.3). ∎

######  Theorem 4.3.

Under assumptions (H.1)—(H.5), then Eq. (1.1) has a unique doubly-weighted
pseudo-almost periodic mild solution whenever $K$ is small enough.

###### Proof.

Consider the nonlinear operator ${\mathbb{M}}$ defined on
$PAP(\mathbb{X}_{\alpha},\mu,\nu)$ by

$\displaystyle{\mathbb{M}}u(t)=\int_{-\infty}^{t}U(t,s)P(s)g(s,u(s))ds-\int_{t}^{\infty}U_{Q}(t,s)Q(s)g(s,u(s))ds$

for each $t\in\mathbb{R}$.

In view of Lemma 4.2, it follows that ${\mathbb{M}}$ maps
$PAP(\mathbb{X}_{\alpha},\mu,\nu)$ into itself. To complete the proof one has
to show that ${\mathbb{M}}$ has a unique fixed-point.

If $v,w\in PAP(\mathbb{X}_{\alpha},\mu,\nu)$, then

$\displaystyle\|\Gamma_{1}(v)(t)-\Gamma_{1}(w)(t)\|_{\alpha}$
$\displaystyle\leq$
$\displaystyle\int_{-\infty}^{t}\|U(t,s)P(s)\left[g(s,v(s))-g(s,w(s))\right]\|_{\alpha}ds$
$\displaystyle\leq$
$\displaystyle\int_{-\infty}^{t}c(\alpha)(t-s)^{-\alpha}e^{-\frac{\delta}{2}(t-s)}\|g(s,v(s))-g(s,w(s))\|ds$
$\displaystyle\leq$ $\displaystyle
Kc(\alpha)\int_{-\infty}^{t}(t-s)^{-\alpha}e^{-\frac{\delta}{2}(t-s)}\|v(s)-w(s)\|ds$
$\displaystyle\leq$ $\displaystyle
kKc(\alpha)\int_{-\infty}^{t}(t-s)^{-\alpha}e^{-\frac{\delta}{2}(t-s)}\|v(s)-w(s)\|_{\alpha}ds$
$\displaystyle\leq$ $\displaystyle
kKc(\alpha)2^{1-\alpha}\,\Gamma(1-\alpha)\delta^{\alpha-1}\|v-w\|_{\alpha,\infty},$

and

$\displaystyle\|\Gamma_{2}(v)(t)-\Gamma_{2}(w)(t)\|_{\alpha}$
$\displaystyle\leq$
$\displaystyle\int_{t}^{\infty}\|U_{Q}(t,s)Q(s)\left[g(s,v(s))-g(s,w(s))\right]\|_{\alpha}ds$
$\displaystyle\leq$
$\displaystyle\int_{t}^{\infty}m(\alpha)e^{\delta(t-s)}\|g(s,v(s))-g(s,w(s))\|ds$
$\displaystyle\leq$
$\displaystyle\int_{t}^{\infty}m(\alpha)Ke^{\delta(t-s)}\|v(s)-w(s)\|ds$
$\displaystyle\leq$ $\displaystyle
km(\alpha)K\int_{t}^{\infty}e^{\delta(t-s)}\|v(s)-w(s)\|_{\alpha}ds$
$\displaystyle\leq$ $\displaystyle
Kkm(\alpha)\|v-w\|_{\alpha,\infty}\int_{t}^{+\infty}e^{\delta(t-s)}ds$
$\displaystyle=$ $\displaystyle
Kkm(\alpha)\delta^{-1}\|v-w\|_{\alpha,\infty},$

where
$\displaystyle\left\|u\right\|_{\alpha,\infty}:=\sup_{t\in\mathbb{R}}\left\|u(t)\right\|_{\alpha}.$

Combining previous approximations it follows that

$\|\mathbb{M}v-\mathbb{M}w\|_{\infty,\alpha}\leq
KC(\alpha,\delta)\,.\,\|v-w\|_{\alpha,\infty},$

where
$C(\alpha,\delta)=km(\alpha)\delta^{-1}+kc(\alpha)2^{1-\alpha}\,\Gamma(1-\alpha)\delta^{\alpha-1}>0$
is a constant, and hence if the Lipschitz $K$ is small enough, then Eq. (1.1)
has a unique solution, which obviously is its only doubly-weighted pseudo-
almost periodic mild solution. ∎

## References

  * [1] R. P. Agarwal, B. de Andrade, and C. Cuevas, Weighted pseudo-almost periodic solutions of a class of semilinear fractional differential equations. Nonlinear Anal. (RWA) 11 (2010), no. 5, 3532–3554.
  * [2] B. Amir and L. Maniar, Composition of pseudo-almost periodic functions and Cauchy problems with operator of nondense domain. Ann. Math. Blaise Pascal 6 (1999), no. 1, 1–11.
  * [3] M. Baroun, S. Boulite, T. Diagana, and L. Maniar, Almost periodic solutions to some semilinear non-autonomous thermoelastic plate equations. J. Math. Anal. Appl. 349(2009), no. 1, 74–84.
  * [4] M. Baroun, S. Boulite, G. M. N’Guérékata, and L. Maniar, Almost automorphy of semilinear parabolic evolution equations. Electron. J. Differential Equations. 2008 (2008), no. 60, 1–9.
  * [5] J. Blot, G. M. Mophou, G. M. N’Guérékata, and D. Pennequin, Weighted pseudo-almost automorphic functions and applications to abstract differential equations. Nonlinear Anal. 71(2009), nos. 3–4, 903–909.
  * [6] H. Bohr, Almost periodic functions. Chelsea Publishing Company, New York, 1947.
  * [7] N. Boukli-Hacenea and K. Ezzinbi, Weighted pseudo-almost periodic solutions for some partial functional differential equations. Nonlinear Anal. 71 (2009), no. 9, 3612–3621.
  * [8] N. Boukli-Hacenea and K. Ezzinbi, Weighted pseudo-almost automorphic solutions for some partial functional differential equations. Nonlinear Anal. (RWA) 12 (2011), no. 1, 562–570.
  * [9] D. Bugajewski and T. Diagana, Almost automorphy of the convolution operator and applications to differential and functional differential equations, Nonlinear Stud. 13 (2006), no. 2, 129–140.
  * [10] T. Diagana, Doubly-weighted pseudo almost periodic functions. Preprint. 2010.
  * [11] T. Diagana, Weighted pseudo-almost periodic functions and applications. C. R. Acad. Sci. Paris, Ser I 343 (2006), no. 10, 643–646.
  * [12] T. Diagana, G. M. Mophou, and G. M. N’Guérékata, Existence of weighted pseudo-almost periodic solutions to some classes of differential equations with $\mathbb{S}^{p}$-weighted pseudo-almost periodic coefficients. Nonlinear Anal. 72 (2010), no. 1, 430–438.
  * [13] T. Diagana, Existence of weighted pseudo-almost periodic solutions to some classes of hyperbolic evolution equations. J. Math. Anal. Appl. 350 (2009), no. 1, 18–28.
  * [14] T. Diagana, Weighted pseudo-almost periodic solutions to a neutral delay integral equation of advanced type. Nonlinear Anal. 70 (2009), no. 1, 298–304.
  * [15] T. Diagana, Existence of weighted pseudo-almost periodic solutions to some non-autonomous differential equations. Int. J. Evol. Equ. 2 (2008), no. 4, 397–410.
  * [16] Y. Komori and S. Shirai, Weighted Morrey spaces and a singular integral operator. Math. Nachr. 282 (2009), no. 2, 219 -231.
  * [17] B. M. Levitan and V. V. Zhikov, Almost periodic functions and differential equations. Moscow Univ. Publ. House 1978. English Translation by Cambridge University Press, 1982.
  * [18] J. Liang, T.-J. Xiao, and J. Zhang, Decomposition of weighted pseudo-almost periodic functions. Nonlinear Anal. 73 (2010), no. 10, 3456–3461.
  * [19] J. H. Liu, G. M. N’Guérékata, and N. V. Minh, Topics on stability and periodicity in abstract differential equations. Series on Concrete and Applicable Mathematics, Vol. 6, World Scientific, 2008.
  * [20] J. H. Liu, X. Q. Song, and P. L. Zhang, Weighted pseudo-almost periodic mild solutions of semilinear evolution equations with nonlocal conditions. Appl. Math. Comput. Vol. 215 (2009), no. 5, 1647–1652.
  * [21] J. H. Liu and X. Q. Song, Almost automorphic and weighted pseudo-almost automorphic solutions of semilinear evolution equations. J. Funct. Anal. 258 (2010), no. 1, 196–207.
  * [22] L. Maniar and R. Schnaubelt, Almost periodicity of inhomogeneous parabolic evolution equations, Lecture Notes in Pure and Appl. Math. 234 (2003), Dekker, New York, 299- 318.
  * [23] T-J. Xiao, J. Liang, and J. Zhang, Pseudo-almost automorphic solutions to semilinear differential equations in Banach spaces. Semigroup Forum 76 (2008), no. 3, 518–524.
  * [24] T. J. Xiao, X-X. Zhu, and J. Liang, Pseudo-almost automorphic mild solutions to nonautonomous differential equations and applications. Nonlinear Anal. 70 (2009), no. 11, 4079–4085.
  * [25] C. Y. Zhang, Pseudo-almost periodic solutions of some differential equations. J. Math. Anal. Appl 181 (1994), no. 1, 62–76.
  * [26] C. Y. Zhang, Pseudo-almost periodic solutions of some differential equations. II. J. Math. Anal. Appl 192 (1995), no. 2, 543–561.
  * [27] C. Y. Zhang, Integration of vector-valued pseudo-almost periodic functions, Proc. Amer. Math. Soc 121 (1994), no. 1, pp. 167–174.
  * [28] L. Zhang and Y. Xu, Weighted pseudo-almost periodic solutions of a class of abstract differential equations. Nonlinear Anal. 71 (2009), no. 9, 3705–3714.
  * [29] L. L. Zhang and H. X. Li, Weighted pseudo-almost periodic solutions for some abstract differential equations with uniform continuity. Bull. Aust. Math. Soc. 82 (2010), 424–436.


University of Zagreb, Croatia and PUC Chile and IMFD,
<EMAIL_ADDRESS>– Millennium Science Initiative Program
– Code ICN17_002 Domagoj Vrgoč [500]Information systems Query languages
https://arxiv.org/abs/2204.11137

# Evaluating regular path queries under the all-shortest paths semantics

Domagoj Vrgoč

###### Abstract

The purpose of this paper is to explain how the textbook breadth-first search
algorithm (BFS) can be modified in order to also create a compact
representation of all shortest paths connecting a single source node to all
the nodes reachable from it. From this representation, all these paths can
also be efficiently enumerated. We then apply this algorithm to solve a
similar problem in edge labelled graphs, where paths also have an additional
restriction that their edge labels form a word belonging to a regular
language. Namely, we solve the problem of evaluating regular path queries
(RPQs) under the all-shortest paths semantics.

###### keywords:

graph databases, query languages, query evaluation

###### category:

##  1 Introduction

Graph databases [AnglesABBFGLPPS18] have gained significant popularity in
recent years, with multiple vendors offering graph database products
[Webber12, TigerGraph, Stardog, AmazonNeptune, JenaTDB], several efforts for
defining the standard for graph data being under way [GQL, HarrisS13], and the
subject receiving substantial coverage in the research literature
[MendelzonW89, Baeza13, HoganBC2020]. Some of the more popular graph formats
in use today are edge-labelled graphs, which are the basis of the RDF standard
[world2014rdf], and property graphs [FrancisGGLLMPRS18], which extend edge-
labelled graphs by also allowing external annotations on nodes and edges.
Graphs offer simple conceptualization of the application domain, modelling
entities as nodes, and their relations as edges, with edge label indicating
the connection type. Typical applications of graph database include crime
detection network, transport networks, genealogy, etc.

In terms of querying, graph databases offer some interesting challenges.
Following [AnglesABHRV17], one could roughly divide graph queries into two
main classes: (i) graph pattern; and (ii) path queries. Graph patterns look to
match a smaller graph-shaped pattern into a graph database, while path queries
allow exploring paths whose length is not known in advance, and thus require a
limited form of recursion. A well studied class of path queries are regular
path queries, or RPQs for short [Baeza13]. An RPQ specifies a regular
language, and the query simply retrieves all pairs of nodes connected by a
path whose edge labels form a word belonging to this language. RPQs are widely
adopted in practice, forming part of the SPARQL standard for querying RDF data
[HarrisS13], and being supported in many popular graph engines [Webber12,
TigerGraph, JenaTDB].

An interesting feature of RPQs is that their semantics, as usually defined in
the research literature [Baeza13], or in the SPARQL standard [HarrisS13], only
requires returning endpoints connected by a path satisfying a given regular
expression, and not the path (or paths) witnessing this connection. However,
in practice, returning paths can be a useful feature, which resulted in
several engines supporting this option [Webber12, TigerGraph, Stardog,
MillDB], and the upcoming ISO standard for graph querying [GQL] specifying
different options for returning paths. When returning paths, some of the
available options would be to return: a single path, all paths, all simple
paths, all shortest paths, all trails, etc. The traditional approach in
research is to consider all paths (also termed all _walks_ in Graph Theory).
However, in the presence of cycles, this can lead to an infinite amount of
matching paths [MendelzonW89], which is undesirable in practice. For this
reason, trails, or shortest paths, are favored by practical systems
[FrancisGGLLMPRS18, Stardog, MillDB].

In this paper, we will focus on solving the problem of evaluating RPQs in such
a way that, in conjunction with all endpoint pairs connected by a path
satisfying a given regular expression, we also return all shortest paths
linking them. That is, we will evaluate RPQs under the all-shortest paths
semantics. This feature is currently supported in some graph engines
[FrancisGGLLMPRS18, Stardog, MillDB], and is also being adopted by the graph
standardization efforts [GQL], so understanding how to solve this problem
algorithmically seems rather relevant for practice.

### Contributions

In this paper we provide a simple algorithm for evaluating regular path
queries under the all-shortest paths semantics, assuming that at least one of
the query endpoints is known. We will write $q=(v,regex,?y)$ for such a query,
signalling that the starting node of the path is fixed to $v$111Notice that
this is done in order to anchor the search algorithm, and is adopted by some
graph engines [Erling12].. For this solution, we modify the standard breadth-
first graph traversal, in order to be able to store all shortest paths as
well. In essence, we are using breadth-first search in order to create a
directed unlabelled graph which can compactly encode all of these paths, and
allows them to be enumerated efficiently. This approach is often used in
enumeration algorithms in databases and information extraction
[FlorenzanoRUVV20, GrezRU19]. We start by explaining how to obtain all
shortest paths in an (unlabelled) graph, reachable from some fixed node. We
then extend this algorithm in order to evaluate RPQs under the all-shortest
paths semantics.

### Organization

The paper is structured as follows:

  * •

In Section 2 we define graphs, graph databases, RPQs, and recall the BFS
algorithm.

  * •

In Section 3, we show how to extend the textbook BFS algorithm so that,
starting from a fixed node $v$, we can return all $v^{\prime}$ reachable from
$v$, along with the list of all shortest paths connecting them.

  * •

In Section LABEL:sec:algo, we then apply this extension in order to enumerate
all-shortest paths that witness an answer to an RPQ which has at least one
endpoint fixed.

  * •

We conclude in Section LABEL:sec:concl.

### Proviso

The purpose of this paper is to solve a single database problem that occurs in
practice. It is therefore short and to the point. It provides a theoretical
algorithm for this problem and nothing else. In terms of novelty, we believe
that the algorithm presented in Section 3 is folklore, and has been considered
before. However, we could not locate a reference to the specific problem we
are solving, so we include it here for completeness. To the best of our
knowledge, using this algorithm to evaluate RPQs under the all-shortest paths
semantics (Section LABEL:ss:contrib) is a new application not explored
previously, at least not with its links to enumeration algorithms.

##  2 Preliminaries

In this section we recall basic notions about graphs, graph databases, regular
path queries. and the breadth-first graph traversals. We also make precise the
notion of delay used in our enumeration algorithms.

### Graphs

A _graph_ $G$ is a pair $(V,E)$, where $V$ is a finite set of nodes, and
$E\subseteq V\times V$ is a set of edges. A path in $G$ is simply a sequence
$n_{1}\ldots n_{k}$ of nodes, such that $(n_{i},n_{i+1})\in E$, for $i=1\ldots
k-1$.

### Graph databases

Following database theory literature [AnglesABHRV17, Baeza13, MendelzonW89],
and the RDF specification [world2014rdf], for a labelling alphabet $\Sigma$,
we define edge-labelled graphs as follows:

######  Definition 2.1.

An _edge-labelled graph_ $G$ is a tuple $(V,E)$, where:

  * •

$V$ is a finite set of nodes.

  * •

$E\subseteq V\times\Sigma\times V$ is a finite set of $\Sigma$-labelled edges.

When talking about edge-labelled graphs, we will often refer to them as _graph
databases_. A _path_ in a graph database is a sequence
$\pi=n_{1}a_{1}n_{2}a_{2}\ldots a_{k}n_{k+1}$, where $n_{i}\in V$, and
$a_{i}\in\Sigma$, such that $(n_{i},a_{i},n_{i+1})\in E$, for $i=1\ldots k$.
We define the label of a path $\pi$, denoted $\lambda(\pi)$ as the word
$a_{1}\cdots a_{k}$, formed by concatenating the labels of the edges on this
path.

### Querying graph databases

One of the most common class of queries over graph databases are regular path
queries, or RPQs, which are well studied in the research literature [Baeza13,
MendelzonW89], and are supported by the SPARQL standard [HarrisS13], as well
as many other graph query languages such as, for instance, Cypher
[FrancisGGLLMPRS18] or GQL [GQL]. For us, a _regular path query_ over a graph
database $G$, will be an expression of the form $(v,regex,?x)$, where $v$ is a
node in $G$, and $regex$ is a regular expression over $\Sigma$, the edge
labelling alphabet of $G$222We will restrict the search to the single starting
node. RPQs generally can also have a free variable in the place of $v$.. Given
an RPQ $q=(v,regex,?x)$ over a graph database $G$, its semantics is defined as
the set of all nodes $v^{\prime}$ in $G$, that are reachable from $v$ by a
path $\pi$ such that $\lambda(\pi)$ is a word in the language of the regular
expression $regex$. We denote the set of all answers for $q$ over $G$ with
$\llbracket q\rrbracket_{G}$.

While this version of RPQ semantics only asks for nodes reachable from $v$,
one will often be also interested in retrieving the paths which witness this
connection. In this regards, we will study two versions of evaluating RPQs:
(i) the one which, for each node $v^{\prime}\in\llbracket q\rrbracket_{G}$,
also returns a single shortest path witnessing this connection; and (ii) the
one which, in addition to $v^{\prime}$ returns all shortest paths linking $v$
and $v^{\prime}$. We remark that the basic version of the semantics, returning
only the reachable nodes, is the W3C standard for SPARQL property paths
[HarrisS13]. Version (i) above would be a reasonable addition to the SPARQL
standard, while the version (ii) is supported by the upcoming GQL standard
[GQL] and Cypher [FrancisGGLLMPRS18].

### Breadth-first search (BFS)

Given a (unlabelled) graph $G$, and a node $v$ in $G$, all nodes reachable
from $v$, and a shortest path connecting them, can be obtained by the textbook
BFS algorithm [cormen2022introduction]. We include the code of this version of
BFS in Algorithm 1.

Algorithm 1 All nodes in $G$ reachable from $v$, plus a shortest path

1:function Search($G,v$)

2: $Open.init()$ $\triangleright$ Empty queue(BFS)

3: $Visited.init()$ $\triangleright$ Empty set of visited nodes.

4: $start\leftarrow(v,\bot)$

5: $Open.push(start)$

6: $Visited.push(start)$

7: while !Open.isEmpty() do

8: current=Open.pop() $\triangleright$ $current=(n,prev)$

9: $solutions.add(n)$ $\triangleright$ This is one of the reachable nodes

10: $ReconstructPath(current)$

11: for $n^{\prime}$ s.t. $(n,n^{\prime})\in E$ do $\triangleright$ Neighbours
of $n$

12: if $!(n^{\prime}\in Visited)$ then $\triangleright$ Ignore $prev$

13: $next=(n^{\prime},n)$

14: Open.push(next)

15: Visited.push(next)

Basically, Algorithm 1, keeps track of pairs $(n^{\prime},n)$, where
$n^{\prime}$ is a newly found node on some shortest path from $v$, and $n$ is
its immediate predecessor on this shortest path. When searching whether
$n^{\prime}\in Visited$ (line 12), we only compare equality by first component
of the pair stored in $Visited$. The function $ReconstrucPath(current)$ (line
10), for $current=(n,prev)$, reconstructs the shortest path from $v$ to $n$ by
following $prev$ pointers in $Visited$. Namely, it starts in $n$, and then
searches $Visited$ with $prev$, and so on, until reaching $\bot$. This is well
defined since for $(n,prev)$ to be in $Visited$, there also must exist a pair
$(prev,prev^{\prime})$ in $Visited$.

### Output linear delay

Since we will deal with queries that can potentially have a large number of
outputs, we will use the paradigm of _enumeration algorithms_ [bagan2006mso,
Segoufin13, FlorenzanoRUVV20, GrezRU19] to measure the efficiency of our
solutions. Enumeration algorithms work in two phases: first, a _pre-processing
phase_ is permitted in order to construct some data structures. Following
this, the _enumeration phase_ uses these data structures to enumerate the
solutions, one by one, and without repetitions. The efficiency of an
enumeration algorithm is measured by determining both the complexity of the
preprocessing phase, and the delay between any two elements produced during
the enumeration phase. The ideal case, when the delay does not depend on the
input, is called _constant delay_. Unfortunately, when outputting paths, the
length of the path itself can depend on the input (the graph), so constant
delay seems unachievable. Instead, we will aim to have _output-linear delay_ ,
where the delay is linear in the size of each output element. For instance,
when outputting paths, this means that the time needed to output a single path
is linear in its length (i.e. the number of nodes in the path), and the delay
before starting to write down the next path is constant. This, in a sense, is
optimal, since we have to at least write down each element in the path.

##  3 Enumerating all shortest paths from a single source

In this section we assume that $G$ is an (unlabelled) graph. That is,
$G=(V,E)$, with $E\subseteq V\times V$. The problem we will solve is as
follows:

Problem: |
---|---
Input: | A graph $G=(V,E)$, and a node $v\in V$.
Output: | For each node $v^{\prime}$ reachable from $v$ in $G$, the list of all shortest paths
| connecting them.

In order to solve

######  Problem 2.

, we will modify the standard breadth-first search algorithm
[cormen2022introduction], which, by default, also returns a single shortest
path for each reachable node. The code of algorithm for