text:
\section{Introduction}
{\em Longest common subsequence} (LCS) is one of the most basic
measures of similarity between strings, and there is a vast amount of literature concerning its efficient computation.
An LCS of two strings $A$ and $B$ of lengths $M$ and $N$, respectively, is a longest string that is a subsequence of both $A$ and $B$.
There is a well known $O(MN)$ time and space dynamic programming (DP) algorithm~\cite{DBLP:journals/jacm/WagnerF74} to compute
an LCS between two strings.
LCS has applications in bioinformatics~\cite{korkin02:_multip,wang11}, file comparisons~\cite{hunt76:_algor_differ_file_compar,heckel78}, pattern recognition~\cite{stern13:_most}, etc.

Recently, several variants of the problem
which try to find a longest common subsequence that satisfy some constraints have
been considered.
In 2003, Tsai~\cite{DBLP:journals/ipl/Tsai03} proposed the constrained LCS (CLCS) problem,
where, given strings $A,B$ with respective lengths $M,N$, and a constraint string $C$ of length $K$, the problem is to find a longest string that contains $C$ as a subsequence
and is also a common subsequence of $A$ and $B$.
Tsai gave an $O(M^2N^2K)$ time solution, which was improved in 2004 by Chin et al. to $O(MNK)$ time~\cite{DBLP:journals/ipl/ChinSFHK04}.
Variants of the constrained LCS problem called
SEQ-IC-LCS, SEQ-EC-LCS, STR-IC-LCS, and STR-EC-LCS,
were considered by Chen and Chao in 2011~\cite{DBLP:journals/jco/ChenC11}.
Each problem considers as input, three strings $A,B$ and $C$,
and the problem is to find a longest string that includes (IC) or excludes (EC)
$C$ as a subsequence (SEQ) or substring (STR) and is a common subsequence of $A$ and $B$
(i.e., CLCS is equivalent to the SEQ-IC-LCS problem).
The best solution for each of the problems is shown in Table~\ref{tbl:timecomplexityGCLCS}.

\begin{table}[htbp]
  \begin{center}
    \caption{Time complexities of best known solutions to various constrained LCS problems.}
    \label{tbl:timecomplexityGCLCS}
    \begin{tabular}{ccc} \hline
      Problem & DP solution & DP solution using RLE \\ \hline
      SEQ-IC-LCS & $O(MNK)$~\cite{DBLP:journals/ipl/ChinSFHK04}
      & $O(M+N+K\min\{mN, nM\})$~\cite{DBLP:journals/cj/LiuWC15} \\
      SEQ-EC-LCS & $O(MNK)$~\cite{DBLP:journals/jco/ChenC11} & - \\
      STR-IC-LCS & $O(MN)$~\cite{DBLP:journals/ipl/Deorowicz12} & $O(mN+nM)$ [this work] \\
      STR-EC-LCS & $O(MNK)$~\cite{DBLP:journals/ipl/WangWWZ13} & - \\ \hline
    \end{tabular}
  \end{center}
\end{table}

In order to speed up the LCS computation, one direction of research that has received much attention is
to apply compression, namely, run-length encoding (RLE) of strings.
Bunke and Csirik~\cite{DBLP:journals/ipl/BunkeC95} were one of the first to consider such a scenario, and
proposed an $O(mN+nM)$ time algorithm. Here, $m,n$ are the sizes of the RLE of the input strings of lengths $M$ and $N$, respectively.
Notice that since RLE can be computed in linear time, and $m \leq M$ and $n \leq N$, the algorithm is always asymptotically faster than
the standard $O(NM)$ time dynamic programming algorithm, especially when the strings are compressible by RLE.
Furthermore, Ahsan et al. proposed an algorithm which runs in $O((m+n)+R\log\log(mn)+R\log\log(M+N))$ time~\cite{DBLP:journals/jcp/AhsanAR14},
where $R$ is the total number of pairs of runs of the same character in the two RLE strings, i.e. $R \in O(mn)$,
and the algorithm can be much faster when the strings are compressible by RLE.

For the constrained LCS problems, RLE based solutions for only the SEQ-IC-LCS problem have been proposed.
In 2012, an $O(K(mN+nM))$ time algorithm was proposed by Ann et al.~\cite{DBLP:journals/tcs/AnnYTH12}.
Later, in 2015, Liu et al. proposed a faster $O(M+N+K\min\{mN,nM\})$ time algorithm~\cite{DBLP:journals/cj/LiuWC15}.

In this paper, we present the first RLE based solution for the STR-IC-LCS problem that runs in $O(mN+nM)$ time.
Again, since RLE can be computed in linear time, and $m \leq M$ and $n \leq N$, the proposed algorithm is always asymptotically faster than
the best known solution for the STR-IC-LCS problem by Deorowicz~\cite{DBLP:journals/ipl/Deorowicz12}, which runs in $O(MN)$ time.

A common criticism against RLE based solutions is a claim that, although they are theoretically interesting,
since most strings ``in the real world'' are not compressible by RLE, their applicability is limited and they are only useful in extreme artificial cases.
We believe that this is not entirely true.
There can be cases where RLE is a natural encoding of the data, for example, in music, a melody
can be expressed as a string of pitches and their duration.
Furthermore, in the data mining community, there exist popular preprocessing schemes for analyzing various types of
time series data, which convert the time series to strings over a fairly small alphabet as an approximation of the original data,
after which various analyses are conducted (e.g. SAX (Symbolic Aggregate approXimation)~\cite{lin07:_exper_sax},
{\em clipped} bit representation~\cite{bagnall06:_bit_level_repres_time_series}, etc.).
These conversions are likely to produce strings which are compressible by RLE
(and in fact, shown to be effective in~\cite{bagnall06:_bit_level_repres_time_series}),
indicating that RLE based solutions may have a wider range of application than commonly perceived.

\section{Preliminaries}
Let $\Sigma$ be the finite set of characters, and $\Sigma ^\ast$ be the set of strings.
For any string $A$, let $|A|$ be the length of $A$.
For any $1 \leq i \leq i' \leq |A|$, let $A[i]$ be the $i$th character of $A$ and let $A[i..i'] = A[i] \cdots A[i']$ denote a substring of $A$.
Especially, $A[1..i']$ denotes a {\em prefix} of $A$, and $A[i..|A|]$ denotes a {\em suffix} of $A$.
A string $Z$ is a {\em subsequence} of $A$ if $Z$ can be obtained from $A$ by removing zero or more characters.
For two string $A$ and $B$, a string $Z$ is a {\em longest common subsequence} (LCS) of $A,B$,
if $Z$ is a longest string that is a subsequence of both $A$ and $B$.
For any $1 \leq i \leq |A|$ and $1 \leq j \leq |B|$, let $L^{pref}(i,j)$ denote the length of an LCS of $A[1..i]$, $B[1..j]$, and let $L^{suf}(i,j)$ denote the length of an LCS of $A[i..|A|]$, $B[j..|B|]$.
The LCS problem is to compute the length of an LCS of given two strings $A$ and $B$.
A well known solution is dynamic programming,
which computes in $O(MN)$ time, a table (which we will call {\em DP table}) of size $O(MN)$ that stores values of $L^{pref}(i,j)$ for all $1 \leq i \leq M$, $1 \leq j\leq N$.
The DP table for $L^{suf}(i,j)$ can be computed similarly.

For two strings $A,B$ and a constraint string $C$, a string $Z$ is an STR-IC-LCS of $A,B,C$,
if $Z$ is a longest string that includes $C$ as a substring
and also is a subsequence of both $A$ and $B$.
The STR-IC-LCS problem is to compute the length of an STR-IC-LCS of any given three strings $A$, $B$ and $C$.
For example, if $A=\mathtt{abacab}$, $B=\mathtt{babcaba}$, $C=\mathtt{bb}$, then $\mathtt{abcab}$ and $\mathtt{bacab}$ are LCSs of $A,B$,
and $\mathtt{abb}$ is an STR-IC-LCS of $A,B,C$.

The run-length encoding (RLE) of a string $A$ is a kind of compressed representation of $A$ where each maximal run of the same character is represented by a pair of the character and the length of the run.
Let $\mathit{RLE}(A)$ denote the RLE of a string $A$. The {\em size} of $\mathit{RLE}(A)$ is the number of the runs in $A$, and is denoted by $|\mathit{RLE}(A)|$.
By definition, $|\mathit{RLE}(A)|$ is always less than or equal to $|A|$.

In the next section, we consider the STR-IC-LCS problem of strings $A$, $B$ and constraint string $C$.
Let $|A|=M$, $|B|=N$, $|C|=K$, $|\mathit{RLE}(A)|=m$ and $|\mathit{RLE}(B)|=n$.
We assume that $K \leq \min(M, N)$ and $|\mathit{RLE}(C)| \leq \min(m,n)$, since in such case there can be no solution.
We also assume that $K > 0$, because in that case the problem becomes
the normal LCS problem of $A,B$.

\section{Algorithm}
In this section, we will first introduce a slightly modified version of
Deorowicz's $O(MN)$-time algorithm for the STR-IC-LCS
problem~\cite{DBLP:journals/ipl/Deorowicz12}, and then
propose our $O(mN + nM)$-time algorithm which is
based on his dynamic programming approach but uses RLE.

\subsection{Deorowicz's $O(MN)$ Algorithm}\label{ssec:DeorowiczAlgo}
We first define the notion of minimal $C$-intervals of a string.
\begin{definition}\label{def:mincinterval}
  For any strings $A$ and $C$, an interval $[s, f]$ is a {\em minimal $C$-interval of $A$} if
  \begin{itemize}
    \item $C$ is a subsequence of $A[s..f]$, and
    \item $C$ is not a subsequence of $A[s+1..f]$ or $A[s..f-1]$.
  \end{itemize}
\end{definition}

Deorowicz's algorithm is based on Lemma~\ref{lem:CharacteristicSTR-IC-LCS}, which is used implicitly in~\cite{DBLP:journals/ipl/Deorowicz12}.
\begin{lemma}[implicit in~\cite{DBLP:journals/ipl/Deorowicz12}]\label{lem:CharacteristicSTR-IC-LCS}
  If $Z$ is an STR-IC-LCS of $A, B, C$, then
  there exist minimal $C$-intervals $[s, f], [s', f']$
  $(1 \leq s \leq f \leq M$, $1 \leq s' \leq f' \leq N)$ respectively of $A$ and $B$,
  such that $Z = XCY$, where
  $X$ is an LCS of $A[1..s-1]$ and $B[1..s'-1]$ and
  $Y$ is an LCS of $A[f+1..M]$ and $B[f'+1..N]$.
\end{lemma}

\begin{proof}
  From the definition of STR-IC-LCS, $C$ is a substring of $Z$, and therefore,
  there exist (possibly empty) strings $X,Y$ such that $Z = XCY$.
  Also, since $Z$ is a common subsequence of $A$ and $B$, there exist
  monotonically increasing sequences $i_1, \ldots, i_{|Z|}$ and $j_1, \ldots, j_{|Z|}$
  such that
  $Z = A[i_1] \cdots A[i_{|Z|}]$ $= B[j_1] \cdots B[j_{|Z|}]$, and
  $C = A[i_{|X|+1}] \cdots A[i_{|X|+K}]$ $= B[j_{|X|+1}] \cdots B[j_{|X|+K}]$.

  Now, since $C$ is a subsequence of
  $A[i_{|X|+1}..i_{|X|+K}]$ and $B[j_{|X|+1}..j_{|X|+K}]$ there exist
  minimal $C$-intervals $[s, f]$, $[s', f']$ respectively of $A$ and $B$ that satisfy
  $i_{|X|+1} \leq s \leq f \leq i_{|X|+K}$ and
  $j_{|X|+1} \leq s' \leq f' \leq j_{|X|+K}$.
  Let $X'$ be an LCS of $A[1..s-1]$ and $B[1..s'-1]$,
  and $Y'$ an LCS of $A[f+1..M]$ and $B[f'+1..N]$.
  Since $X$ must be a common subsequence of $A[1..s-1]$ and $B[1..s'-1]$,
  and $Y$ a common subsequence of $A[f+1..M]$ and $B[f'+1..N]$,
  we have $|X'| \geq |X|$ and $|Y'| \geq |Y|$.
  However, we cannot have that $|X'| > |X|$ or $|Y'| > |Y|$
  since otherwise, $X'CY'$ would be a string longer than $Z$ that contains $C$ as a substring,
  and is a common subsequence of $A,B$, contradicting that
  $Z$ is an STR-IC-LCS of $A,B,C$.
  Thus, $|X|=|X'|$ and $|Y|=|Y'|$ implying that $X$ is also an LCS of $A[1..s-1], B[1..s'-1]$,
  and $Y$ is also an LCS of $A[f+1..M], B[f'+1..N]$, proving the lemma.
\end{proof}
The algorithm consists of the following two steps, whose correctness follows from Lemma \ref{lem:CharacteristicSTR-IC-LCS}.
\begin{description}
  \item[Step 1] Compute all minimal $C$-intervals of $A$ and $B$.
  \item[Step 2] For all pairs of a minimal $C$-interval $[s,f]$ of $A$
    and a minimal $C$-interval $[s',f']$ of $B$,
    compute
    the length of an LCS of the corresponding prefixes of $A$ and $B$ (i.e., $L^{pref}(s-1,s'-1)$)
    and that of the corresponding suffixes of $A$ and $B$ (i.e., $L^{suf}(f+1,f'+1)$).
    The largest sum of LCS lengths plus $|C|$ (i.e., $L^{pref}(s-1,s'-1) + L^{suf}(f+1,f'+1) +|C|$) is the length of an STR-IC-LCS.
\end{description}

The steps can be executed in the following running times.
For Step 1,
there are respectively at most $M$ and $N$ minimal $C$-intervals of $A$ and $B$,
which can be enumerated in $O(MK)$ and $O(NK)$ time.
For Step 2, we precompute, in $O(MN)$ time,
two dynamic programming tables which respectively contain the values of $L^{pref}(i,j)$ and $L^{suf}(i,j)$ for each $1\leq i \leq M$ and $1 \leq j \leq N$.
Using these tables, the value $L^{pref}(s-1,s'-1) + L^{suf}(f+1,f'+1) +|C|$ can be computed in constant time for any $[s,f]$ and $[s',f']$.
There are $O(MN)$ possible pairs of minimal $C$-intervals, so Step 2 can be done in $O(MN)$ time.
In total, since $K \leq M, K \leq N$, the STR-IC-LCS problem can be solved in $O(MN)$ time.

We note that in the original presentation of Deorowicz's algorithm,
{\em right}-minimal $C$-intervals, that is, intervals $[s,f]$ where $C$ is a subsequence of $A[s..f]$ but not of $A[s..f-1]$
are computed,
instead of minimal $C$-intervals as defined in Definition~\ref{def:mincinterval}.
Although the number of considered intervals changes, this does not influence the asymptotic complexities in the non-RLE case.
However, as we will see in Lemma~\ref{lem:MinInterval k>1} of Section~\ref{ssec:OurAlgo}, this is an essential difference for the RLE case, since, when $|\mathit{RLE}(C)|>1$,
the number of minimal $C$-intervals of $A$ and $B$ can be bounded by $O(m)$ and $O(n)$, but
the number of right-minimal $C$-intervals of $A$ and $B$ cannot, and are only bounded by $O(M)$ and $O(N)$.

\subsection{Our Algorithm via RLE}\label{ssec:OurAlgo}
In this subsection, we propose an efficient algorithm based on Deorowicz's algorithm explained in
Subsection~\ref{ssec:DeorowiczAlgo}, extended to strings expressed in RLE.
There are two main cases to consider:
when $|\mathit{RLE}(C)| = 1$, i.e., when $C$ consists of only one type of character,
and when $|\mathit{RLE}(C)| > 1$, i.e., when $C$ contains at least two different characters.

\subsubsection{Case $|\mathit{RLE}(C)| > 1$}

\begin{theorem}\label{thm:TimeComplexity k>1}
  Let $A,B,C$ be any strings and let $|A|=M$, $|B|=N$, $|\mathit{RLE}(A)|=m$ and $|\mathit{RLE}(B)|=n$.
  If $|\mathit{RLE}(C)|>1$, we can compute the length of an STR-IC-LCS of $A,B,C$ in $O(mN + nM)$ time.
\end{theorem}

For Step 1, we execute the following procedure to enumerate all minimal $C$-intervals of $A$ and $B$.
Let $s_0 = 0$.
First, find the right minimal $C$-interval starting at $s_0+1$, i.e., the smallest position $f_1$ such that $C$ is a subsequence of $A[s_0+1..f_1]$.
Next, starting from position $f_1$ of $A$, search backwards to find the left minimal $C$-interval ending at $f_1$, i.e.,
the largest position $s_1$ such that $C$ is a subsequence of $A[s_1..f_1]$.
The process is then repeated, i.e., find the smallest position $f_2$ such that $C$ is a subsequence of $A[s_1+1..f_2]$,
and then search backwards to find the largest position $s_2$ such that $C$ is a subsequence of $A[s_2..f_2]$, and so on.
It is easy to see that the intervals
$[s_1, f_1], [s_2, f_2], \ldots$
obtained by repeating this procedure until reaching the end of $A$ are all the
minimal $C$-intervals of $A$,
since each interval that is found is distinct, and there cannot exist another minimal $C$-interval between those found by the procedure.
The same is done for $B$.
For non-RLE strings, this takes $O((M+N)K)$ time.
The Lemma below shows that the procedure can be implemented more efficiently using RLE.

\begin{lemma}\label{lem:MinInterval k>1}
  Let $A$ and $C$ be strings where $|A| = M$, $|\mathit{RLE}(A)| = m$ and $|C| = K$.
  If $|\mathit{RLE}(C)| > 1$,
  the number of minimal $C$-intervals of $A$ is $O(m)$ and can be enumerated in $O(M+mK)$ time.
\end{lemma}

\begin{proof}
  Because $|\mathit{RLE}(C)|>1$, it is easy to see from the backward search in the procedure described above,
  that for any minimal $C$-interval of $A$,
  there is a unique run of $A$ such that the last character of the first run of $C$ corresponds to the last character of that run.
  Therefore, the number of minimal $C$-intervals of $A$ is $O(m)$.

  We can compute $\mathit{RLE}(A) = a_1^{M_1} \cdots a_m^{M_m}$ and $\mathit{RLE}(C)=c_1^{K_1} \cdots c_k^{K_k}$ in $O(M+K)$ time.
  What remains is to show that the forward/backward search procedure described
  above to compute all minimal $C$-intervals of $A$ can be implemented in $O(mK)$ time.
  The pseudo-code of the algorithm described is shown in Algorithm~\ref{alg:minCinterval}.

  In the forward search, we scan $\mathit{RLE}(A)$ to find a right minimal $C$-interval by greedily matching the runs of $\mathit{RLE}(C)$ to $\mathit{RLE}(A)$.
  We maintain the character $c_q$ and exponent $\mathit{rest}$ of the first run $c_q^{\mathit{rest}}$ of $\mathit{RLE}(C')$, where $C'$ is the suffix of $C$ that is not yet matched.
  When comparing a run $a_p^{M_p}$ of $\mathit{RLE}(A)$ and $c_q^{\mathit{rest}}$,
  if the characters are different (i.e., $a_p \neq c_q$), we know that the entire run $a_p^{M_p}$ will not match
  and thus we can consider the next run of $A$.
  Suppose the characters are the same. Then, if $M_p < \mathit{rest}$, the entire run $a_p^{M_p}$ of $A$ is matched, and we can consider the next run $a_{p+1}^{M_{p+1}}$ of $A$.
  Also, $\mathit{rest}$ can be updated accordingly in constant time by simple arithmetic. Furthermore, since $c_q = a_p \neq a_{p+1}$, we can in fact skip to the next run
  $a_{p+2}^{M_{p+2}}$.
  If $M_p \geq \mathit{rest}$, the entire run $c_q^{\mathit{rest}}$ is matched, and we consider the next run $c_{q+1}^{K_{q+1}}$ in $C$.
  Also, since $a_p = c_q \neq c_{q+1}$, we can skip the rest of $a_p^{M_p}$ and consider the next run $a_{p+1}^{M_{p+1}}$ of $A$.
  Thus, we spend only constant time for each run of $A$ that is scanned in the forward search. The same holds for the backward search.

  To finish the proof, we show that the total number of times that each run of $A$ is scanned in the procedure is bounded by $O(K)$, i.e.,
  the number of minimal $C$-intervals of $A$ that intersects with a given run $a_p^{M_p}$ of $A$ is $O(K)$.
  Since $|\mathit{RLE}(C)| > 1$, a minimal $C$-interval cannot be contained in $a_p^{M_p}$.
  Thus, for a minimal $C$-interval to intersect with the run $a_p^{M_p}$, it must cross either the left boundary of the run, or the right boundary of the run.
  For a minimal $C$-interval to cross the left boundary of the run, it must be that for some non-empty strings $u,v$ such that $C = uv$,
  $u$ occurs as a subsequence in $a_1^{M_1} \cdots a_{p-1}^{M_{p-1}}$ and
  $v$ occurs as a subsequence in $a_p^{M_p} \cdots a_{m}^{M_{m}}$.
  The minimal $C$-interval corresponds to the union of the left minimal $u$-interval ending at the
  left boundary of the run and the right minimal $v$-interval starting at the left boundary of the run and is thus unique for $u,v$.
  Similar arguments also hold for minimal $C$-intervals that cross the right boundary of $a_p^{M_p}$.
   Since there are only $K-1$ choices for $u,v$, the claim holds, thus proving the Lemma.
\end{proof}

\begin{algorithm2e}
  \caption{computing all minimal $C$-intervals of $A$}
  \label{alg:minCinterval}
  \KwIn{strings $A$ and $C$}
  \KwOut{all minimal $C$-intervals $[s_1, f_1], \ldots, [s_l, f_l]$ of $A$}
  \tcp{$\mathit{RLE}(A) = a_1^{M_1} \cdots a_m^{M_m}$,
    $\mathit{RLE}(C) = c_1^{K_1} \cdots c_k^{K_k}$}
  \tcp{$M_{1..p} = M_1 + \cdots + M_p$}
  \tcp{$p,q$ : index of run in $A,C$ respectively}
  \tcp{$rest$ : number of rest of searching characters of $c_q^{K_q}$}
  \tcp{$l$ : number of minimal $C$-intervals in $A$}

  $p \gets 1$;
  $q \gets 1$;
  $rest \gets K_1$;
  $l \gets 0$\;

  \While{true}{
    \While(// forward search){$p \leq m$ and $q \leq k$}{ \label{algln:fsearch_begin}
      \lIf{$a_p \neq c_q$}{$p \gets p+1$\;} \label{algln:ap!=cq}
      \Else{
        \uIf{$M_p \geq rest$}{ \label{algln:ap=cq&Mp>=rest_begin}
          $q \gets q+1$\;
          \lIf{$q > k$}{$l \gets l+1$; $f_l \gets M_{1..p-1} + rest$\;}
          \lElse{$p \gets p+1$; $rest \gets K_q$\;} \label{algln:ap=cq&Mp>=rest_end}
        }
        \lElse{$rest \gets rest - M_p$; $p \gets p+2$\;} \label{algln:fsearch_end}
      }
    }
    \lIf{$p > m$}{{\bf break}\;} \label{algln:algoend}

    $p \gets p-1$\;
    \lIf{$rest = K_k$}{$q \gets q-1$; $rest \gets K_{k-1}$\;}
    \lElse{$q \gets k$; $rest \gets K_k - rest$\;}

    \While(// backward search){$q \geq 1$}{ \label{algln:bsearch_begin}
      \lIf{$a_p \neq c_q$}{$p \gets p-1$\;}
      \Else{
        \uIf{$M_p \geq rest$}{
          $q \gets q+1$\;
          \lIf{$q < 1$}{$s_l \gets M_{1..p} - rest + 1$\;}
          \lElse{$p \gets p-1$; $rest \gets K_q$\;}
        }
        \lElse{$rest \gets rest - M_p$; $p \gets p-2$\;} \label{algln:bsearch_end}
      }
    }

    $p \gets p+1$;
    $q \gets 1$;
    $rest \gets K_1 - rest + 1$\;
  }
  \Return{$[s_1, f_1], \ldots, [s_l, f_l]$}\;
\end{algorithm2e}

In Deorowicz's algorithm, two DP tables were computed for Step 2, which took $O(MN)$ time.
For our algorithm, we use a compressed representation of the DP table for $A$ and $B$,
proposed by Bunke and Csirik~\cite{DBLP:journals/ipl/BunkeC95}, instead of the normal DP table.
We note that Bunke and Csirik actually solved the edit distance problem
when the cost is $1$ for insertion and deletion, and $2$ for substitution,
but this easily translates to LCS: $L^{pref}(i,j) = (i+j-\mathit{ED}^{pref}(i,j))/2$, where
$\mathit{ED}^{pref}(i,j)$ denotes the edit distance with such costs, between $A[1..i]$ and $B[1..j]$.

\begin{definition}[\cite{DBLP:journals/ipl/BunkeC95}]\label{def:compressedDPtable}
  Let $A$, $B$ be strings of length $M$, $N$ respectively, where $\mathit{RLE}(A) = a_1^{M_1} \cdots a_m^{M_m}$ and $\mathit{RLE}(B) = b_1^{N_1} \cdots b_n^{N_n}$.
  The {\em compressed DP table (cDP table) of $A, B$} is an $O(mN+nM)$-space compressed representation of the DP table of $A,B$
  which holds only the values of the DP table for $(M_{1..p},j)$ and $(i,N_{1..q})$,
  where, $1 \leq i \leq M$, $1 \leq j \leq N$, $1 \leq p \leq m$, $1 \leq q \leq n$, $M_{1..p} = M_1 + \cdots + M_p$, $N_{1..q} = N_1 + \cdots + N_q$.
\end{definition}

\begin{figure}[htbp]
  \begin{center}
    \begin{tabular}{|c|c|cccc|ccc|cc|} \hline
      \multicolumn{2}{|c|}{} & \multicolumn{9}{c|}{$B$} \\ \cline{3-11}
      \multicolumn{2}{|c|}{} & \tt{a} & \tt{a} & \tt{a} & \tt{a} & \tt{b} & \tt{b} & \tt{b} & \tt{a} & \tt{a} \\ \hline
        & \tt{b} &   &   &   & 0 &   &   & 1 &   & 1 \\
        & \tt{b} &   &   &   & 0 &   &   & 2 &   & 2 \\
        & \tt{b} & 0 & 0 & 0 & 0 & 1 & 2 & 3 & 3 & 3 \\ \cline{2-11}
    $A$ & \tt{a} &   &   &   & 1 &   &   & 3 &   & 4 \\
        & \tt{a} &   &   &   & 2 &   &   & 3 &   & 5 \\
        & \tt{a} &   &   &   & 3 &   &   & 3 &   & 5 \\
        & \tt{a} & 1 & 2 & 3 & 4 & 4 & 4 & 4 & 4 & 5 \\ \hline
    \end{tabular}
  \end{center}
  \caption{An example of a compressed $L^{pref}$ DP table for strings $A=\mathtt{bbbaaaa}$ and $B=\mathtt{aaaabbbaa}$.}
  \label{tbl:compressedDPtable}
\end{figure}

Figure~\ref{tbl:compressedDPtable} illustrates the values stored in the cDP table for strings
$A=\mathtt{bbbaaaa}$, $B=\mathtt{aaaabbbaa}$.
Note that although the figure depicts a sparsely filled table of size $M\times N$,
the values are actually stored in two (completely filled) tables:
one of size $m\times N$, holding the values of $(M_{1..p},j)$, and another of size $M\times n$,
holding the values of $(i, N_{1..q})$, for a total of $O(mN+nM)$ space.
Below are results adapted from~\cite{DBLP:journals/ipl/BunkeC95} we will use.

\begin{lemma}[{\cite[Theorem 7]{DBLP:journals/ipl/BunkeC95}}]
  \label{lem:CDPtable}
  Let $A$ and $B$ be any strings where $|A| = M$, $|B| = N$, $|\mathit{RLE}(A)| = m$ and $|\mathit{RLE}(B)| = n$.
  The compressed DP table of $A$ and $B$ can be computed in $O(mN + nM)$ time and space.
\end{lemma}

\begin{lemma}[{\cite[Lemma 3]{DBLP:journals/ipl/BunkeC95}}]
  \label{lem:LCScalculation1}
  Let $\alpha \in \Sigma$ and
  let $A$ and $B$ be any strings where $|A| = M$ and $|B| = N$.
  For any integer $d \geq 1$,
  if $A[M-d+1..M] = B[N-d+1..N] = \alpha^d$,
  then $L^{pref}(M,N) = L^{pref}(M-d,N-d) + d$.
\end{lemma}

\begin{lemma}[{\cite[Lemma 5]{DBLP:journals/ipl/BunkeC95}}]
  \label{lem:LCScalculation2}
  Let $\alpha, \beta \in \Sigma$, $\alpha \neq \beta$ and
  let $A$ and $B$ be any strings where $|A| = M$ and $|B| = N$.
  For any integers $d \geq 1$ and $d' \geq 1$,
  if $A[M-d+1..M] = \alpha^d$ and $B[N-d'+1..N] = \beta^{d'}$
  then $L^{pref}(M,N) = \max\{L^{pref}(M-d,N), L^{pref}(M,N-d')\}$.
\end{lemma}

From Lemmas~\ref{lem:LCScalculation1} and~\ref{lem:LCScalculation2},
we easily obtain the following Lemma~\ref{lem:DPandCDPtable}.

\begin{lemma}\label{lem:DPandCDPtable}
  Let $A$ and $B$ be any strings.
  Any entry of the DP table of $A$ and $B$ can be retrieved in $O(1)$ time
  by using the compressed DP table of $A$ and $B$.
\end{lemma}

From Lemma~\ref{lem:CDPtable}, we can compute in $O(mN+nM)$ time,
two cDP tables of $A,B$ which respectively hold the values of
$L^{pref}(M_{1..p},j)$, $L^{pref}(i,N_{1..q})$
and
$L^{suf}(M_{1..p},j)$, $L^{suf}(i,N_{1..q})$,
each of them taking $O(mN+nM)$ space.
From Lemma~\ref{lem:DPandCDPtable},
we can obtain $L^{pref}(i,j)$, $L^{suf}(i,j)$ for any $i$ and $j$ in $O(1)$ time.
Actually, to make Lemma~\ref{lem:DPandCDPtable} work, we also need to be able to convert the indexes
between DP and cDP in constant time, i.e.,
for any $1 \leq p \leq m$, $1 \leq q \leq n$, the values $M_{1..p}$ and $N_{1..q}$, and
for any $1 \leq i \leq M$, $1 \leq j \leq N$, the largest $p,q$ such that $M_{1..p} \leq i$, $N_{1..q} \leq j$.
This is easy to do by preparing some arrays in $O(M+N)$ time and space.

Now we are ready to show the running time of our algorithm for the case $|\mathit{RLE}(C)|>1$.
We can compute $\mathit{RLE}(A)$,$\mathit{RLE}(B)$,$\mathit{RLE}(C)$ from $A,B,C$ in $O(M+N+K)$ time.
In Step 1, we have from Lemma~\ref{lem:MinInterval k>1}, that the number of all
minimal $C$-intervals of $A,B$ are respectively $O(m)$ and $O(n)$, and can be computed in
$O(M + N + mK + nK)$ time.
For the preprocessing of Step 2, we build the cDP tables holding the values of
$L^{pref}(i,j)$, $L^{suf}(i,j)$ for $1 \leq i \leq M$, $1 \leq j \leq N$,
which can be computed in $O(mN+nM)$ time and space from Lemma~\ref{lem:CDPtable}.
With these tables, we can obtain for any
$i,j$, the values $L^{pref}(i,j)$, $L^{suf}(i,j)$ in constant time from Lemma~\ref{lem:DPandCDPtable}.
Since there are $O(mn)$ pairs of a minimal $C$-interval of $A$ and a minimal $C$-interval of $B$,
the total time for Step 2, i.e. computing $L^{pref}$ and $L^{suf}$ for each of the pairs, is $O(mn)$.
Since $n\leq N, m\leq M$, and we can assume that $K \leq M, N$, the total time is $O(mN+nM)$.
Thus Theorem~\ref{thm:TimeComplexity k>1} holds.

\subsubsection{Case $|\mathit{RLE}(C)| = 1$}

Next, we consider the case where $|\mathit{RLE}(C)| = 1$, and $C$ consists of only one run.

\begin{theorem}\label{thm:TimeComplexity k=1}
  Let $A,B,C$ be any strings and let $|A|=M$, $|B|=N$, $|\mathit{RLE}(A)|=m$ and $|\mathit{RLE}(B)|=n$.
  If $|\mathit{RLE}(C)|=1$, we can compute the length of an STR-IC-LCS of $A,B,C$ in $O(mN + nM)$ time.
\end{theorem}

For Step 1, we compute all minimal $C$-intervals of $A$ and $B$ by
Lemma~\ref{lem:MinInterval k=1}. Note the difference from Lemma~\ref{lem:MinInterval k>1}
in the case of $|\mathit{RLE}(C)|>1$.

\begin{lemma}\label{lem:MinInterval k=1}
  If $|\mathit{RLE}(C)|=1$,
  the number of minimal $C$-intervals of $A$ and $B$
  are $O(M)$ and $O(N)$, respectively,
  and these can be enumerated in $O(M)$ and $O(N)$ time, respectively.
\end{lemma}

\begin{proof}
  Let $\alpha \in \Sigma$, $C=\alpha^K$, and let $M_\alpha$ be the number of times that $\alpha$ occurs in $A$.
  Then the number of minimal $C$-intervals of $A$ is $M_\alpha-K+1 \in O(M)$.
  The minimal $C$-intervals can be enumerated in $O(M)$ time by checking all positions of $\alpha$ in $A$.
  The same applies to $B$.
\end{proof}

From Lemma~\ref{lem:MinInterval k=1}, we can see that the number of pairs
of minimal $C$-intervals of $A$ and $B$ can be $\Theta(MN)$, and we cannot
afford to consider all of those pairs for Step 2.
We overcome this problem as follows.
Let
$U = \{[s_1, f_1], \ldots, [s_l, f_l]\}$ be the
set of all minimal $C$-intervals of $A$.
Consider the partition $G(1), \ldots, G(g)$ of $U$
which are the equivalence classes induced by the following equivalence relation on $U$:
For any $1 \leq p \leq q \leq m$ and $[s_x, f_x], [s_y, f_y] \in U$,
\begin{eqnarray}
[s_x,f_x] \equiv [s_y,f_y] \iff
M_{1..p-1} < s_x ,s_y \leq M_{1..p} \mbox{ and }
M_{1..q-1} < f_x , f_y \leq M_{1..q},\label{eqn:equivalence}
\end{eqnarray}
where, $M_{1..0} = 0$. In other words, $[s_x,f_x]$ and $[s_y,f_y]$ are in the same equivalence class
if they start in the same run, and end in the same run.
Noticing that minimal $C$-intervals cannot be completely contained in another,
we can assume that for $1\leq h < h'\leq g$, $[s_x, f_x] \in G(h)$ and $[s_y, f_y] \in G(h')$,
we have $s_x < s_y$ and $f_x < f_y$.

\begin{lemma}\label{lem:numofG}
  Let $G(1), \ldots, G(g)$ be the partition of the set $U$ of all minimal $C$-intervals of $A$
  induced by the equivalence relation~(\ref{eqn:equivalence}).
  Then, $g \in O(m)$.
\end{lemma}

\begin{proof}
  Let $1 \leq x < y \leq l$ and $2 \leq h \leq g$.
  For any $[s_x, f_x] \in G(h-1)$ and $[s_y, f_y] \in G(h)$,
  let $1 \leq p \leq q \leq m$ satisfy
  $M_{1..p-1} < s_x \leq M_{1..p}$, $M_{1..q-1} < f_x \leq M_{1..q}$.
  Since the intervals are not equivalent, either $M_{1..p} < s_y$ or $M_{1..q} < f_y$ must hold.
  Thus, $g \in O(m)$.
\end{proof}

Equivalently for $B$, we consider the set $U' = \{[s'_1, f'_1], \ldots, [s'_{l'}, f'_{l'}]\}$
of all minimal $C$-intervals of $B$, and the partition $G'(1), \ldots, G'(g')$ of $U'$
based on the analogous equivalence relation, where $g' \in O(n)$.

For some $h$, let $[s_x, f_x]$, $[s_y, f_y]$ be the minimal $C$-intervals in $G(h)$ with the smallest and largest start positions.
Since by definition, $A[s_x] = \cdots = A[s_y] = A[f_x] = \cdots = A[f_y]$,
we have $G(h) = \{[s_x+i, f_x+i], [s_x+1, f_x+1], \ldots, [s_y, f_y]\}$.
The same can be said for $G'(h')$ of $B$.
From this observation, we can show the following Lemma~\ref{lem:calcLCSinG}.

\begin{lemma}\label{lem:calcLCSinG}
  For any $1 \leq h \leq g$ and $1 \leq h' \leq g'$, let
  $[s, f]$, $[s+d, f+d] \in G(h)$ and
  $[s', f']$, $[s'+d, f'+d] \in G'(h')$,
   for some positive integer $d$.
  Then,
  \[L^{pref}(s-1, s'-1) + L^{suf}(f+1, f'+1) = L^{pref}(s+d-1, s'+d-1) + L^{suf}(f+d+1, f'+d+1).\]
\end{lemma}

\begin{proof}
  Since $A[s..s+d] = A[f..f+d] = B[s'..s'+d] = B[f'..f'+d] = C[1]^d$,
  we have from Lemma~\ref{lem:LCScalculation1},
  $L^{pref}(s+d-1, s'+d-1) = L^{pref}(s-1, s'-1) + d$,
  and
  $L^{suf}(f+1, f'+1) = L^{suf}(f+d+1, f'+d+1) + d$.
\end{proof}

From Lemma~\ref{lem:calcLCSinG}, we can see that for any
$G(h), G'(h')$ $(1 \leq h \leq g$, $1 \leq h' \leq g')$,
we do not need to compute $L^{pref}(s-1, s'-1) + L^{suf}(f+1, f'+1)$ for all pairs of
$[s, f] \in G(h)$ and $[s', f'] \in G'(h')$.
Let $G_{\min}(h)$ and $G_{\min}'(h')$ be the minimal $C$-intervals respectively in $G(h)$ and $G'(h')$ with the smallest starting position.
Then, we only need to consider the combination of $G_{\min}(h)$ with each of $[s', f'] \in G'(h')$,
and the combination of each of $[s, f] \in G(h)$ with $G_{\min}'(h')$.
Therefore, of all combinations of minimal $C$-intervals in $U$ and $U'$,
we only need to consider for all $1 \leq h \leq g$ and $1 \leq h' \leq g'$,
the combination of $G_{\min}(h)$ with each of $U'$, and
each of $U$ with $G_{\min}'(h')$.
The number of such combinations is clearly $O(mN + nM)$.

For example, consider
$\mathit{RLE}(A) = \mathtt{a}^5\mathtt{b}^3\mathtt{a}^4\mathtt{b}^2\mathtt{a}^1$,
$\mathit{RLE}(B) = \mathtt{a}^1\mathtt{b}^3\mathtt{a}^7\mathtt{b}^3$,
$\mathit{RLE}(C) = \mathtt{a}^5$.
For the minimal $C$-intervals of $A$, we have
$G(1) = \{[1,5]\}$,
$G(2) = \{[2,9],[3,10],[4,11],[5,12]\}$,
$G(3) = \{[9,15]\}$.
For the minimal $C$-intervals of $B$, we have
$G'(1) = \{[1,8]\}$,
$G'(2) = \{[5,9],[6,10],[7,11]\}$.
Also, $G_{\min}(2) = [2,9]$, $G_{\min}'(2) = [5,9]$.
Figure~\ref{tbl:LCS k=1} shows the lengths of the LCS of prefixes and suffixes for each combination between
minimal $C$-intervals in $G(2)$ and $G'(2)$.
The gray part is the values that are referred to.
The values denoted inside parentheses are not stored in the cDP table, but each of them can be
computed in $O(1)$ time from Lemma~\ref{lem:DPandCDPtable}.
Figure~\ref{tbl:LCSsum k=1} shows the sum of the LCS of prefixes and suffixes corresponding to the gray part.
Due to Lemma~\ref{lem:calcLCSinG}, the values along the diagonal are equal.
Thus, for the combinations of minimal $C$-intervals in $G(2)$, $G'(2)$, we only need to consider
the six combinations: $([2,9],[5,9])$,$([2,9],[6,10])$,$([2,9],[7,11])$,$([3,10],[5,9])$,$([4,11],[5,9])$,$([5,12],[5,9])$.

\begin{figure}[htbp]
  \begin{center}
    \caption{An example depicting the LCSs of corresponding prefixes (left) and suffixes (right) of all combinations of $G(2)$ and $G'(2)$ for strings $\mathit{RLE}(A) = \mathtt{a}^5\mathtt{b}^3\mathtt{a}^4\mathtt{b}^2\mathtt{a}^1$,
$\mathit{RLE}(B) = \mathtt{a}^1\mathtt{b}^3\mathtt{a}^7\mathtt{b}^3$, and
$\mathit{RLE}(C) = \mathtt{a}^5$. The values denoted inside parentheses are not stored in the cDP table, but each of them can be
computed in $O(1)$ time.}
    \label{tbl:LCS k=1}
    \begin{tabular}{cc}
      \begin{minipage}{0.5\hsize}
        \begin{center}
          \begin{tabular}{|c|c|c|ccc|cccc|} \hline
            \multicolumn{2}{|c|}{} & \multicolumn{8}{c|}{$B$} \\ \cline{3-10}
            \multicolumn{2}{|c|}{} & \tt{a} & \tt{b} & \tt{b} & \tt{b} & \tt{a} & \tt{a} & \tt{a} & $\cdots$ \\ \hline
                & \tt{a} & 1 &   &   & \tgray1 & \cellcolor[gray]{0.85}(1) & \cellcolor[gray]{0.85}(1) &   & \\
                & \tt{a} & 1 &   &   & \tgray1 & \cellcolor[gray]{0.85}(2) & \cellcolor[gray]{0.85}(2) &   & \\
                & \tt{a} & 1 &   &   & \tgray1 & \cellcolor[gray]{0.85}(2) & \cellcolor[gray]{0.85}(3) &   & \\
            $A$ & \tt{a} & 1 &   &   & \tgray1 & \cellcolor[gray]{0.85}(2) & \cellcolor[gray]{0.85}(3) &   & \\
                & \tt{a} & 1 & 1 & 1 & 1 & 2 & 3 & 4 & $\cdots$ \\ \cline{2-10}
                & \tt{b} & 1 &   &   & 2 &   &   &   & \\
                & $\vdots$ & $\vdots$ &   &   & $\vdots$ &   &   &   & \\ \hline
          \end{tabular}
        \end{center}
      \end{minipage}
      \begin{minipage}{0.5\hsize}
        \begin{center}
          \begin{tabular}{|c|c|cccc|ccc|} \hline
            \multicolumn{2}{|c|}{} & \multicolumn{7}{c|}{$B$} \\ \cline{3-9}
            \multicolumn{2}{|c|}{} & $\cdots$ & \tt{a} & \tt{a} & \tt{a} & \tt{b} & \tt{b} & \tt{b} \\ \hline
                & $\vdots$ &   &   &   &   & $\vdots$ &   & \\
                & \tt{a} &   &   & \cellcolor[gray]{0.85}(4) & \cellcolor[gray]{0.85}(3) & \tgray2 &   & \\
                & \tt{a} &   &   & \cellcolor[gray]{0.85}(4) & \cellcolor[gray]{0.85}(3) & \tgray2 &   & \\
            $A$ & \tt{a} &   &   & \cellcolor[gray]{0.85}(3) & \cellcolor[gray]{0.85}(3) & \tgray2 &   & \\ \cline{2-9}
                & \tt{b} & $\cdots$ & 2 & \tgray2 & \tgray2 & \tgray2 & 2 & 1 \\
                & \tt{b} &   &   &   &   & 1 &   & \\ \cline{2-9}
                & \tt{a} & $\cdots$ & 1 & 1 & 1 & 0 & 0 & 0 \\ \hline
          \end{tabular}
        \end{center}
      \end{minipage}
    \end{tabular}
  \end{center}
\end{figure}

\begin{figure}[htbp]
  \begin{center}
    \caption{Sum of the lengths of LCSs of corresponding prefixes and suffixes shown in Figure~\ref{tbl:LCS k=1}.
      Values along the diagonal are equal (each value is equal to the value to its upper left/lower right).}
    \label{tbl:LCSsum k=1}
    \begin{tabular}{ccc}
      \rowcolor[gray]{0.85} 5 & 4 & 3 \\
      \rowcolor[gray]{0.85} 5 & 5 & 4 \\
      \rowcolor[gray]{0.85} 4 & 5 & 5 \\
      \rowcolor[gray]{0.85} 3 & 4 & 5 \\
    \end{tabular}
  \end{center}
\end{figure}

Now, we are ready to show the running time of our algorithm for the case $|\mathit{RLE}(C)|=1$.
We can compute $\mathit{RLE}(A)$, $\mathit{RLE}(B)$, $\mathit{RLE}(C)$ from $A,B,C$ in $O(M+N+K)$ time.
There are respectively $O(M)$ and $O(N)$ minimal $C$-intervals of $A$ and $B$, and
each of them can be assigned to one of the $O(m)$ and $O(n)$ equivalence classes
$G, G'$, in total of $O(M+N)$ time.
The preprocessing for the cDP table is the same as for the case of $|\mathit{RLE}(C)|>1$,
which can be done in $O(mN + nM)$ time.
By Lemma~\ref{lem:calcLCSinG}, we can reduce the number of combinations of
minimal $C$-intervals to consider to $O(mN + nM)$.
Finally, from Lemma~\ref{lem:DPandCDPtable}, the LCS lengths for each combination can be
computed in $O(1)$ using the cDP table.
Therefore, the total running time is $O(mN + nM)$,
proving Theorem~\ref{thm:TimeComplexity k=1}.

From Theorems~\ref{thm:TimeComplexity k>1} and~\ref{thm:TimeComplexity k=1}, the following Theorem~\ref{thm:TimeComplexity} holds.
The pseudo-code for our proposed algorithm is shown in Algorithm~\ref{alg:STR-IC-LCS} (written in Appendix).

\begin{theorem}\label{thm:TimeComplexity}
  Let $A,B,C$ be any strings and let $|A|=M$, $|B|=N$, $|\mathit{RLE}(A)|=m$ and $|\mathit{RLE}(B)|=n$.
  We can compute the length of an STR-IC-LCS of $A,B,C$ in $O(mN + nM)$ time.
\end{theorem}

Although we only showed how to compute the length of an STR-IC-LCS, we note that
the algorithm can be modified so as to obtain a RLE of an STR-IC-LCS in $O(m+n)$ time,
provided that $\mathit{RLE}(C)$ is precomputed, simply by
storing the minimal $C$-intervals $[s,f]$, $[s',f']$, respectively of $A$ and $B$,
that maximizes $L^{pref}(s-1,s'-1) + L^{suf}(f+1,f'+1) + |C|$.
From Lemmas~\ref{lem:LCScalculation1} and~\ref{lem:LCScalculation2},
we can
simulate a standard back-tracking of the DP table for obtaining LCSs
with the cDP table to obtain RLE of the LCSs in $O(m+n)$ time.
Finally an RLE of STR-IC-LCS can be obtained by combining the three RLE strings (the two LCSs with $\mathit{RLE}(C)$ in the middle),
appropriately merging the boundary runs if necessary.

\section{Conclusion}
In this work, we proposed a new algorithm to solve the STR-IC-LCS problem using RLE representation.
We can compute the length of an STR-IC-LCS of strings $A,B,C$ in $O(mN+nM)$ time and space using this algorithm, where $|A| = M$, $|B| = N$, $|RLE(A)| = m$ and $|RLE(B)| = n$.
This result is better than Deorowicz's $O(MN)$ time and space~\cite{DBLP:journals/ipl/Deorowicz12}, which doesn't use RLE.
If we want to know not only the length but also an STR-IC-LCS of $A,B,C$, we can retrieve it in $O(m+n)$ time.

\section{Appendix}
Here, we show the pseudo-code for our proposed algorithm.

\begin{algorithm2e}
  \caption{Proposed $O(mN+Mn)$ time algorithm for STR-IC-LCS}
  \label{alg:STR-IC-LCS}
  \KwIn{strings $A$, $B$ and $C$}
  \KwOut{length of an STR-IC-LCS of $A,B,C$}

  \tcp{$[s_x,f_x]$ : a minimal $C$-interval in $A$}
  \tcp{$[s'_y,f'_y]$ : a minimal $C$-interval in $B$}
  \tcp{$l,l'$ : number of minimal $C$-intervals in $A,B$ respectively}
  \tcp{$G_{\min}(h),G_{\min}'(h')$ : minimum element in $G(h),G'(h')$ respectively}
  \tcp{$g,g'$ : number of sets $G,G'$ respectively}

  Make compressed DP tables of $A$ and $B$.\;

  \uIf{$|\mathit{RLE}(C)| > 1$}{
    Compute all minimal $C$-intervals $[s_1,f_1], \ldots, [s_l,f_l]$ of $A$
    and $[s'_1,f'_1], \ldots, [s'_{l'},f'_{l'}]$ of $B$.
    (use Algorithm~\ref{alg:minCinterval})\;

    $L_{\max} \gets 0$\;
    \For{$x=1$ {\bf to} $l$}{
      \For{$y=1$ {\bf to} $l'$}{
        $L_{\mathrm{sum}} \gets L^{pref}(s_x-1,s'_y-1) + L^{suf}(f_x+1,f'_y+1)$\;
        \lIf{$L_{\max} < L_{\mathrm{sum}}$}{
            $L_{\max} \gets L_{\mathrm{sum}}$\;
        }
      }
    }
  }
  \Else{
    $l \gets 1-K$;
    $g \gets 1$;
    $G_{\min}(1) \gets 1$\;
    \For{$p=1$ {\bf to} $m$}{
      \If{$a_p = C[1]$}{
        \For{$p'=1$ {\bf to} $M_p$}{
          $l \gets l+1$;
          $s_{l+K} \gets M_{1..p}+p'$\;
          \lIf{$l \geq 1$}{
            $f_l \gets M_{1..p}+p'$\;
          }
          \If{$l \geq 2$}{
            \lIf{$s_{l-1}+1 \neq s_l$ or $f_{l-1}+1 \neq f_l$}{
              $g \gets g+1$;
              $G_{\min}(g) \gets l$\;
            }
          }
        }
      }
    }

    $l' \gets 1-K$;
    $g' \gets 1$;
    $G_{\min}'(1) \gets 1$\;
    \For{$q=1$ {\bf to} $n$}{
      \If{$b_q = C[1]$}{
        \For{$q'=1$ {\bf to} $N_q$}{
          $l' \gets l'+1$;
          $s'_{l'+K} \gets N_{1..q}+q'$\;
          \lIf{$l' \geq 1$}{
            $f'_{l'} \gets N_{1..q}+q'$\;
          }
          \If{$l' \geq 2$}{
            \lIf{$s'_{l'-1}+1 \neq s'_{l'}$ or $f'_{l'-1}+1 \neq f'_{l'}$}{
              $g' \gets g'+1$;
              $G_{\min}'(g') \gets l'$\;
            }
          }
        }
      }
    }
    $G_{\min}(g+1) \gets l+1$;
    $G_{\min}'(g'+1) \gets l'+1$\;

    $L_{\max} \gets 0$\;
    \For{$h=1$ {\bf to} $g$}{
      \For{$h'=1$ {\bf to} $g'$}{
        \For{$x=G_{\min}(h)$ {\bf to} $G_{\min}(h+1)-1$}{
          $L_{\mathrm{sum}} \gets L^{pref}(s_x-1,s'_{G_{\min}'(h')}-1) + L^{suf}(f_x+1,f'_{G_{\min}'(h')}+1)$\;
          \lIf{$L_{\max} < L_{\mathrm{sum}}$}{
            $L_{\max} \gets L_{\mathrm{sum}}$\;
          }
        }
        \For{$y=G_{\min}'(h')$ {\bf to} $G_{\min}'(h'+1)-1$}{
          $L_{\mathrm{sum}} \gets L^{pref}(s_{G_{\min}(h)}-1,s'_y-1) + L^{suf}(f_{G_{\min}(h)}+1,f'_y+1)$\;
          \lIf{$L_{\max} < L_{\mathrm{sum}}$}{
            $L_{\max} \gets L_{\mathrm{sum}}$\;
          }
        }
      }
    }
  }
  \Return{$L_{\max} + K$}\;
\end{algorithm2e}

redpajama_set_name: RedPajamaArXiv


text:
package org.tud.reneviz.data;

/**
 * This class is used to store constants of Reneviz in one place.
 *
 */
public final class Constants {
	/**
	 * the maximum number of results (graph edges) to be returned in a query.
	 */
	public static final int MAX_RESULT_LIST_SIZE = 20;

	public static final String SPARQL_IP = "localhost";
	public static final String SPARQL_PORT = "3131";
	public static final String SPARQL_DATASET_PATH = "/cornell";

	public static final int FOCUS_NEIGHBORHOOD = 2;

	public static String getSparqlService() {
		return "http://"
				+ SPARQL_IP
				+ ":"
				+ SPARQL_PORT
				+ SPARQL_DATASET_PATH
				+ "/query";
	}

	public static String getSparqlData() {
		return "http://"
				+ SPARQL_IP
				+ ":"
				+ SPARQL_PORT
				+ SPARQL_DATASET_PATH
				+ "/data?default";
	}

	/**
	 * private constructor: This class should not be instantiated.
	 */
	private Constants() {
		// intentionally empty
	}
}

redpajama_set_name: RedPajamaGithub


text:
'I Don't Care': Trump Responds To Intel That Russia Is Working To Get Him Elected Again
Mary Papenfuss
President Donald Trump shrugged off the latest intelligence warning Friday that Russia is "denigrating" presumptive Democratic presidential candidate Joe Biden to get Trump elected again.
"I don't care what anybody says," Trump responded to the new information.
The Kremlin is using a "range of measures" to "denigrate" and "undermine" Biden as Russian officials maneuver again to interfere in the U.S. presidential election, William Evanina, director of the National Counterintelligence and Security Center, said in a statement released Friday. "Kremlin-linked actors are also seeking to boost President Trump's candidacy on social media and Russian television," the statement added.
Evanina also warned that pro-Russia Ukrainian parliamentarian Andriy Derkach , the son of a former KGB officer, "is spreading claims about corruption — including through publicizing leaked phone calls — to undermine ... Biden's candidacy and the Democratic Party." Derkach has met with Trump's personal attorney Rudy Giuliani, and the two speak often. Derkach has also reportedly fed suspect information to Sen. Chuck Grassley (R-Iowa) and Sen. Ron Johnson (R-Wis.).
When asked by a reporter about Evanina's statement at his Bedminster golf resort in New Jersey, Trump responded: "I think that the last person Russia wants to see in office is Donald Trump, because nobody's been tougher on Russia — ever."
"I don't care what anybody says," he added. "Nobody with any common sense would say ... look at what we're doing with our military ... look at all of the things we've done with NATO, where I've raised $130 billion a year from countries that were delinquent and now they're paying all of this money ... that's all money to protect against Russia."
Trump hasn't "raised" any money at NATO. Countries in NATO also aren't "delinquent" — nations are encouraged to contribute 2% of their GDP.
"I don't care what anybody says" -- Trump dismisses the intelligence community's announcement today that Russia is once again helping him pic.twitter.com/dCHTbJctN6
— Aaron Rupar (@atrupar) August 8, 2020
Trump's refusal to complain to or punish Russia for anti-American actions continues to confound observers. Trump has said he believes Russian President Vladimir Putin's denials that Russia interfered in the 2016 presidential election, even though the U.S. intelligence community has concluded that it did so in a "sweeping and systematic fashion" to sway the vote in Trump's favor.
The president has also recently failed to take any action to punish Russia following revelations that the country was paying bounties to Taliban-linked militia members to kill American soldiers in Afghanistan. He failed to even raise the issue in a recent conversation with Putin.
Evanina's statement Friday also noted that China does not want "unpredictable" Trump reelected. But actions Evanina cited concerning China regarded officials "harshly" criticizing the president's statements on TikTok and Hong Kong, and didn't mention any subterfuge.
U.S. officials more thoroughly briefed on the intelligence were told that Russia is a far graver threat to the election, The New York Times reported. China seeks to gain influence in American politics but has yet to take more decisive action.
As part of the Russian campaign to aid Trump, snippets of leaked Biden phone calls are being characterized by Derkach as as an attempt by the former vice president to block investigations into corruption at a Ukrainian energy company, where his son held a board position. In fact, they appear to be part of Biden's efforts as vice president to force a corrupt Ukrainian prosecutor from office for failing to investigate criminal activity, The Washington Post has reported.
Also on HuffPost
Love HuffPost? Become a founding member of HuffPost Plus today.
This article originally appeared on HuffPost and has been updated.
Twitter locks account of China's U.S. embassy over its defence of Xinjiang policy
Twitter has locked the account of China's U.S. embassy for a tweet that defended China's policy towards Muslim Uighurs in Xinjiang, which the U.S. social media platform said violated its stand against "dehumanizing" people. China's Foreign Ministry said on Thursday that it was confused by the move and that it was the embassy's responsibility to call out disinformation and clarify the truth. The Chinese Embassy account, @ChineseEmbinUS, posted a tweet this month that said that Uighur women had been emancipated and were no longer "baby-making machines", citing a study reported by state-backed newspaper China Daily.
Pelosi, McCarthy respond to questions about House members' role in the Capitol assault
At separate press conferences on Thursday, House Speaker Nancy Pelosi and House Minority Leader Kevin McCarthy responded to reporters' questions about the role members of Congress may have played in the Capitol attack on Jan. 6.
Four shipwrecks, including one dating back to Roman times, have been discovered by marine archeologists off the Greek island of Kasos in the Aegean. Lying between Rhodes and Crete, the Dodecanese island was on a crucial trade route in antiquity. Inside the Roman-era shipwreck, divers found amphorae which originated from Spain and what is now Tunisia, the Greek culture ministry said. They would have been used to transport wine, olive oil and possibly garum – a pungent fish sauce that was much prized by the Romans. The ship has been lying on the seabed for nearly 2,000 years - it is believed to date back to the 2nd or 3rd century AD.
Supreme Court justices lean toward FCC bid to loosen media ownership rules
Conservative U.S. Supreme Court justices signaled sympathy on Tuesday toward a bid by President Donald Trump's administration, backed by broadcast companies, to loosen regulations that critics have said promote a diversity of views in local broadcast media and ownership by racial minorities and women. During arguments by teleconference in the case, conservative justices asked questions that appeared to indicate they believe the Federal Communications Commission did not overstep its authority in repealing certain media ownership regulations in 2017. The justices were considering appeals by the FCC, companies including News Corp, Fox Corp and Sinclair Broadcast Group Inc and the National Association of Broadcasters of a lower court ruling that blocked the rule changes for failing to consider the effects on ownership diversity.
A powerful earthquake shook parts of the southern Philippines on Thursday night, but authorities said it was too deep to cause major damage and no tsunami warning was issued. The quake measured magnitude 7.0 and was located 95.8 kilometers (60 miles) below the sea and about 210 kilometers (130 miles) southeast of Pondaguitan in Davao Occidental province, the U.S. Geological Survey said. In Davao city, President Rodrigo Duterte's hometown, some residents ran out of their houses as the ground shook and power cables and business signs swayed, but there were no reports of damage or injuries.
THEN AND NOW: The cast of the 'High School Musical' movies 15 years later
Harris Faulkner on Inauguration Day protests: How will Biden take action?

redpajama_set_name: RedPajamaCommonCrawl


The computational linguistics olympiad is a contest in which high-school students solve linguistic puzzles. In solving the problems, students learn about the diversity and consistency of language, while exercising logic skills. No prior knowledge of linguistics or second languages is necessary. Professionals in linguistics, computational linguistics and language technologies use dozens of the world's languages to create engaging problems that represent cutting edge issues in their fields. The competition has attracted top students to study and work in those same fields. This is truly an opportunity for young people to experience a taste of natural-language processing in the 21st century.
Brandeis Lab for Linguistics and Computation (BLLC) has been hosting the Greater Boston Area competition for three years at Brandeis University. This year the contest will be held in the Levin Ballroom in Usdan Center.
January 24, 2019, 10:00 am - 1:00 pm.
March 7, 2019, 9:00-3:00 pm.


text:
Guardsman, civilians, and agencies fighting wildfires across western U.S.
● ehill	●	August 20, 2018	● IA News	●	No Comments
The 2018 wildfire season has consumed more than two million acres of land, with more than 100 fires burning as of earlier this month. This comes after another two million acres of land burned in 2017.
Over 30,000 personnel – including firefighters from the U.S., Australia, and New Zealand as well as soldiers and airmen of the National Guard – are battling the flames. Said one California guardsman, "We live and serve in the communities that have been devastated by these fires. We train year-round to come to the aid of our neighbors when tragedy strikes."
In response to the devastating wildfires, the U.S. Forest Service has put forth a plan that calls for increased wildfire mitigation efforts, to include road maintenance, increased logging, and the removal of dead plants.
According to a Forest Service report, "catastrophic wildfires and the corresponding loss of lives, homes and natural resources have continued to grow, partly because our treatments have been uncoordinated and not at the right scale." The report goes on to stress the importance of "shared responsibility" for managing fire risks.
For more information about the firefighting efforts, please follow the links below.
Thousands of Guardsmen Battle Western U.S. Wildfires, Department of Defense
More than 100 large wildfires in U.S. as new blazes erupt, Reuters
Forest Service to Work More Closely With States to Battle Wildfires, Route Fifty
National Fire News, National Interagency Fire Center
GET SIMONS CENTER EMAIL ALERTS
Get Simons Center News & Information Delivered to Your Inbox
Department of Defense (DoD) National Guard National Interagency Fire Center natural disaster wildfire
Featured Article: The Challenges in JIATF operations in a Predatory State
Featured Article: Bureaucracy in Service of a Madman
IA Blog
IA Events
IA News
InterAgency Essays (IAE)
InterAgency Journal (IAJ)
InterAgency Papers (IAP)
InterAgency Reports
InterAgency Study
Simons Center Awards
Simons Center News & Announcements
Web-Exclusive


text:
In algorithmic game theory, a branch of both computer science and economics, a demand oracle is a function that, given a price-vector, returns the demand of an agent. It is used by many algorithms related to pricing and optimization in online market. It is usually contrasted with a value oracle, which is a function that, given a set of items, returns the value assigned to them by an agent.

Demand
The demand of an agent is the bundle of items that the agent most prefers, given some fixed prices of the items. As an example, consider a market with three objects and one agent, with the following values and prices.

Suppose the agent's utility function is additive (= the value of a bundle is the sum of values of the items in the bundle), and quasilinear (= the utility of a bundle is the value of the bundle minus its price). Then, the demand of the agent, given the prices, is the set {Banana, Cherry}, which gives a utility of (4+6)-(3+1) = 6. Every other set gives the agent a smaller utility. For example, the empty set gives utility 0, while the set of all items gives utility (2+4+6)-(5+3+1)=3.

Oracle
With additive valuations, the demand function is easy to compute - there is no need for an "oracle". However, in general, agents may have combinatorial valuations. This means that, for each combination of items, they may have a different value, which is not necessarily a sum of their values for the individual items. Describing such a function on m items might require up to 2m numbers - a number for each subset. This may be infeasible when m is large. Therefore, many algorithms for markets use two kinds of oracles:

 A value oracle can answer value queries: given a bundle, it returns its value.
 A demand oracle can answer demand queries: given a price-vector, it returns a bundle that maximizes the quasilinear utility (value minus price).

Applications
Some examples of algorithms using demand oracles are:

 Welfare maximization: there are n agents and m items. Each agent is represented by a value-oracle and a demand-oracle. It is required to allocate the items among the agents such that the sum of values is maximized. In general the problem is NP-hard, but approximations are known for special cases, such as submodular valuations (this is called the "submodular welfare problem"). Some algorithms use only a value oracle; other algorithms use also a demand oracle.
Envy-free pricing: there are n agents and m items. Each agent is represented by a value-oracle and a demand-oracle. It is required to find a price-vector and an allocation of the items, such that no agent is envious, and subject to that, the seller's revenue is maximized.
Market equilibrium computation.
Learning strong-substitutes demand.

See also

 Oracle machine
 Demand curve
 Robertson-Webb query model - a similar query model in the domain of cake-cutting.

References

Computational economics

redpajama_set_name: RedPajamaWikipedia


text:
<?php

namespace ZfcRbac\View\Helper;

use Zend\View\Helper\AbstractHelper;
use ZfcRbac\Service\RoleService;

/**
 * View helper that allows to test a role in a view
 *
 * @author  JM Leroux <jmleroux.pro@gmail.com>
 * @licence MIT
 */
class HasRole extends AbstractHelper
{
    /**
     * @var RoleService
     */
    private $roleService;

    /**
     * Constructor
     *
     * @param RoleService $roleService
     */
    public function __construct(RoleService $roleService)
    {
        $this->roleService = $roleService;
    }

    /**
     * @param string|string[] $roleOrRoles
     * @return bool
     */
    public function __invoke($roleOrRoles)
    {
        return $this->roleService->matchIdentityRoles((array)$roleOrRoles);
    }
}


"Mark's classic 'Shooting Stars' was originally released on the late great 'Offshoot' label in 1998 and became an underground hit, seeing support from a variety of DJ's including Derrick May, Cajmere and of course, Ben Sims. Fast forward 15 years and this uncompromising tough edged disco workout still gets dropped and is highly sought after on the second hand vinyl market, so we thought it was time for a respectful remix package. First up is a brand new firing makeover from the man himself that jacks in all the right places while staying true to original groove, then label head honcho Ben Sims who drops an intense Lil Louis inspired reworking. Uk hero Aubrey gets Dark on us with an intricate and menacing remix while newly formed Fokus Group (aka Paul Mac & Ben Sims) pull no punches with a relentless and harsh interpretation."


Pete's Pest Control was founded out of necessity from our fearless leader Pete Weikel. Reeling from the economic collapse from 2008, Pete moved to Kansas City from the Seattle-area. He was trying to get his life back in order and went back to what he knew best, Pest Control which he had done for a decade in Seattle. In 2010, working out of a used-up Ford Taurus Pete went to work. He earned the reputation of the subject matter expert who would do superior work at an unbeatable price.
In the years that followed, the company grew steadily into new facilities, a fleet of vehicles, and now an entire support, sales, and marketing staff. We service a wide swath of the Metro, and with the steady hands of our founder Pete The Bug Guy and the diligent guidance of our brilliant General Manager Cat Heisler we have become one of the largest pest control companies in the region. We have joined numerous Chambers of Commerce, and are active in the communities we serve. We had the honor in 2017 of being named the best Pest Control company by Lee's Summit Lifestyle magazine and we we also won the 2017 Top Service Award from Angie's List.
We will always remain the best pest control company because we're a family run local business who is set to look after our clients families and home. We are tasked with keeping potentially dangerous pests at bay and exterminate them as needed. Which is how the phrase "bringing joy and happiness by bringing death and destruction" came about. Have bugs inside the house can be a scary ordeal and with our year around service, we aim to eliminate that risk.
We are licensed to kill in two states and service the whole Kansas City Metro area, but specifically we work in Olathe, Overland Park, Lenexa, Leawood, Prairie Village, Wyandotte, Kansas City Kansas and Kansas City Missouri, Lee's Summit, Independence, Gladstone, Parkville, Loch Lloyd, Gardner, Spring Hill, Bucyrus, Stilwell, Bonner Springs, Piper, Parkville, Platte Woods, Ferrelview, Liberty, River Bend, North Kansas City, Shawnee, Mission, Belton, Raymore, Unity Village, Raytown, Blue Springs.
Pete's Pest Control, LLC is licensed in Kansas and Missouri. We focus on providing the Kansas City Metropolitan area homes and businesses with a full range of pest control services at rates that will exterminate the bugs, not your bank account.


text:
European E. Coli Outbreak Could Happen Here
By Helena Bottemiller
Food Safety, Nutrition, Pesticides
Posted on: June 8, 2011 | 1 Comment
The source of the deadly E. coli O104 outbreak remains a mystery. Officials in Germany are scrambling for answers–and because highly perishable produce is the prime suspect, they might never get them. Amidst the uncertainty, one thing seems clear: this could happen in the U.S.
Food safety and infectious disease experts on both continents are cautioning lawmakers, consumers, and industry that a similar scenario could unfold anywhere.
"Could this happen here? You bet," said Food Politics author and New York University professor Marion Nestle, on her Web site Food Politics Monday.
David Acheson, former associate commissioner of foods at the U.S. Food and Drug Administration, now a consultant to the food industry, agrees. He says the devastation in Europe "serves as a strong reminder to those of us in the United States that we are always one step away from a major food safety crisis."
"As we look on from the outside at the outbreak in the European Union (EU), it is natural to wonder if this could happen in the United States," Acheson wrote in a blog post for Leavitt Partners, a consulting firm founded by Mike Leavitt, who served as Secretary of Health and Human Services under the Bush administration. "I have very little doubt that it could, and so we should not lose this opportunity to learn more lessons about food safety."
"The most important lesson is to focus on building systems that prevent such a situation occurring here in the U.S," explains Acheson. He believes broad mitigation strategies to prevent all forms of E. coli from contaminating food products are the most critical.
"One one has to look for a multifaceted approach that includes controls throughout the supply chain from farms, during processing (of meat, fresh produce or other higher risk items like raw milk) and during handling of food at home," he adds.
Both Acheson and Nestle stressed budgetary concerns as Food and Drug Administration (FDA) moves to implement the most ambitious update to the food regulatory system since the early 20th century.
"If ever there was a time to give the FDA more resources, now is it," added Nestle in her post, which was also published on The Atlantic online. "The FDA now has the authority to impose standard food safety procedures on food producers and to require safety measures for the foods we import. But Congress wants to cut the agency's budget, and badly."
The House Appropriations Committee recently advanced an appropriations bill that would give the agency $87 million less food safety in Fiscal Year 2012 than FY 2011.
"In the current climate of reduced federal funding, it should be made very clear to Congress that our food safety system in the US cannot afford to be undermined through lack of resources," said Acheson. "A request to Congress is not to cut funding, but rather to ensure efficient use of current and future much needed funding."
A version of this story first appeared on Food Safety News
It is neecessary and fundamental that the US implements or complete the regulations in this topic. I think that this unfortunate event has left new experience in the normative lows and the goverment has to be more active to protec and provide the consumers.


text:
Mind Over Matter®
Brain BuzzTM
Stand Ahead®
Stand Ahead
Should Scores on Mild Cognitive Impairment Tests be Adjusted for Sex?
by American Academy of Neurology:
Study Finds More Women, Fewer Men Diagnosed when Sex-specific Scoring Used
Using sex-specific scores on memory tests may change who gets diagnosed with mild cognitive impairment (MCI) by 20 percent, with possibly more women and fewer men being diagnosed, according to a study published in the October 9, 2019, online issue of Neurology®, the medical journal of the American Academy of Neurology. Mild cognitive impairment, a precursor to dementia, is when people have problems with memory and thinking skills.
Because women typically score higher than men on tests of verbal memory, they may not be diagnosed with mild cognitive impairment as early as men are, even when they have the same levels of Alzheimer's disease-related brain changes, such as the amount of amyloid plaque deposits in the brain or the amount of shrinkage in the hippocampus area of the brain.
In the new study, researchers used memory test scores based on sex instead of averages for both men and women. Using the sex-specific scores, researchers found that 10 percent more women were diagnosed with MCI and 10 percent fewer men were diagnosed with MCI than when the averages were used.
"If these results are confirmed, they have vital implications," said study author Erin E. Sundermann, PhD, of the University of California, San Diego. "If women are inaccurately identified as having no problems with memory and thinking skills when they actually have mild cognitive impairment, then treatments are not being started and they and their families are not planning ahead for their care or their financial or legal situations. And for men who are inaccurately diagnosed with mild cognitive impairment, they can be exposed to unneeded medications along with undue stress for them and their families."
The study involved 985 people from the Alzheimer's Disease Neuroimaging Initiative. All of the participants took a verbal memory test that involves learning a list of 15 unrelated words and recalling as many as possible in five immediate tests, where scores range from zero to 75, and also after learning another list and then a 30 minute delay, where scores range from zero to 15.
In a separate group of older adults from the Mayo Clinic Study of Aging, the researchers calculated the typical set of scores that indicate memory impairment based on the average and range of test scores across men and women, and then another set of scores that were specific to each sex and took into account women's typically higher scores on the tests. These two sets of scores were then used to determine who had MCI and who did not among the first group of study participants, The difference in the scores for men and women was an average of six points on the test within a score range of zero to 75 and an average of two points on the test taken after a delay within a score range of zero to 15.
Using the typical scores based on averages across men and women, 120 women, or 26 percent of the women, were diagnosed with MCI. With the sex-specific scores, 165 women, or 36 percent, were diagnosed with the condition. For men, 239 men, or 45 percent, were considered to have MCI when typical scores were used. When using the sex-specific scores, 184 men, or 35 percent, were diagnosed with the condition.
Additionally, when the researchers compared markers of brain changes that occur in the precursor stages of Alzheimer's disease, such as amyloid plaque deposits, they found that the brain changes were more advanced than normal in the women whose diagnosis changed from normal to MCI when using the sex-specific scores. In the men whose diagnosis changed from MCI to normal when using the sex-specific scores, their brain changes closely resembled healthy older adults. These findings support the idea that the use of sex-specific scores on tests determining MCI and Alzheimer's disease improves diagnostic accuracy.
Sundermann said the results also have implications for research, if they are confirmed. "When the typical average cut-off scores are used for diagnosis, women might respond less to treatments in a clinical trial than men because they are at a more advanced stage of the disease, while men might not respond because some of them do not actually have MCI," she said. "These combined factors would result in research that reduces the estimate of how well treatments work for both men and women."
Limitations of the study include that participants were mostly well-educated compared to the general population, so the results may not apply to all groups.
Brain Buzz – Celebrate the Little Things
Although it's great to celebrate the big achievements, it's also important to celebrate the small wins.
On My Nerves – Cognitive Consequences of Midlife Stress
Women are affected by Alzheimer's disease and other forms of dementia in much larger numbers than men. Approximately two-thirds of Canadians and Americans living with dementia are women. Why are women disproportionately affected? Partly, it...
Your brain is affected by what you eat! Join us Thurs. Jan. 21st for an engaging culinary virtual event. Featuring Special Guest MARK McEWAN Celebrity Chef and Restauranteur With...
Everyday InformationFind tips, information and recipes related to brain health.
Scientific InformationRead about the research, news and articles from the medical community.
Caregiver InformationFind helpful advice on taking care of yourself while you care for others.
Brain Buzz
most recent information
most popular information
The material presented through the Think Tank feature on this website is in no way intended to replace professional medical care or attention by a qualified practitioner. WBHI strongly advises all questioners and viewers using this feature with health problems to consult a qualified physician, especially before starting any treatment. The materials provided on this website cannot and should not be used as a basis for diagnosis or choice of treatment. The materials are not exhaustive and cannot always respect all the most recent research in all areas of medicine.
info@womensbrainhealth.org
30 St. Clair Ave W, Suite 900
Toronto, ON M4V 3A1
3800 Oaks Clubhouse Dr., Suite 507
Pompano Beach, Florida
Charitable No.:
80099 3206 RR0001 | 501(c)(3)
Tax-Exempt Organization
Donations are deductible in accordance with U.S. and
Canadian tax law.
Privacy Statement Disclaimer
Donate to WBHI
Our Grey Matter Matters®. Donate to Women's Brain Health Initiative.