text:
\section{Introduction}

A binary word is called {\em \pword{1}} if no factor (substring) has more $1$s than the prefix of the same length.
For example, $11010$ is \pword{1}, but $10110$ is not. Similarly, a binary word is called {\em \pword{0}} if no factor has more $0$s than the prefix of the same length. When not further specified, by {\em prefix normal} we mean \pword{1}. In~\cite{pn1}, we gave an algorithm for generating all prefix normal words of fixed length $n$. As we will see later, to each binary word, a \pword{1} word and a \pword{0} word can be associated in a unique way, which we will call its {\em prefix normal forms}.

\medskip

The {\em Parikh vector} of a binary word $u$ is the pair $(x,y)$, where $x$ is the number of $1$s in $u$, and $y$ is the number of $0$s in $u$. The set of Parikh vectors of factors of a word $w$ is called the \emph{Parikh set} of $w$. For binary words, the problem of deciding whether a particular pair $(x,y)$ lies in the Parikh set of a word $w$ is known as {\em Binary Jumbled Pattern Matching} (BJPM). There has been much interest recently in the indexed version of this problem (IBJPM), where an index for the Parikh set is created in a preprocessing step, which can then be used to answer queries fast. The Parikh set can be represented in linear space due to the following {\em interval property} of binary strings: If $w$ has $k$-length substrings with $x_1$ resp.\ $x_2$ occurrences of $1$, where $x_1< x_2$, then it also has a $k$-length substring with $y$ occurrences of $1$, for every $x_1\leq y \leq x_2$. Thus the Parikh set can be represented by storing, for every $1\leq k \leq |w|$,  the minimum and maximum number of $1$s in a substring of length $k$. Much recent research has focused on how to compute these numbers efficiently~\cite{CFL09,MR10,MR12,CLWY12,BFKL13,GG13,GHLW13}. The problem has also been extended to graphs and trees~\cite{GHLW13,CGGLLRT13}, to the streaming model~\cite{LLZ12}, and to approximate indexes~\cite{CLWY12}. There is also interest in the non-binary variant~\cite{ELP04,CieliebakELSW04,BEL04,CFL09,BCFL12_IJFCS,BCFL12_TOCS,KRR13}, as well as in reconstruction from the Parikh multi-set of a string~\cite{ADMOP10}.
Applications in computational biology include SNP discovery, alignment, gene clusters, pattern discovery, and mass spectrometry data interpretation~\cite{Boecker07,Benson03,BoeckerJMS08,DuhrkopLMB13,Parida06}.

The current best construction algorithm for the linear size index for IBJPM runs in $O(n^{1.864})$ time~\cite{CL15}, for a word of length $n$. As we will see later, computing the prefix normal forms of a word $w$ is equivalent to creating an index for the Parikh set of $w$. Currently, we know no faster computation algorithms for the prefix normal forms than already exist for the linear-size index. However, should better algorithms be discovered, these would immediately carry over to the problem of IBJPM.

\medskip

It is worthwhile noting that some relevant sequences have made it into the
On-Line Encyclopedia of Integer Sequences (OEIS~\cite{sloane}):
A194850 is the number of prefix normal words of length $n$,
A238109 is a list of prefix normal words (over the alphabet $\{1,2\}$), and
A238110 is the maximum size of a class of binary words of length $n$ having the same prefix normal form.

\medskip

The paper is organized as follows: Section 2 contains basic definitions and results
about prefix normal words; in particular that there are unique \pword{0} and \pword{1} words
associated with every word, and thus the set of words can be partitioned according
to this association.  In Section 3 we consider the set of prefix normal words, giving several properties and
characterizations and showing that their language is not context free.  One of these properties
is then used in Section 4, which is concerned with counting the number of prefix normal words of
a given length.  Finally, the paper concludes with some open problems in Section 5.

\section{Basics}\label{sec:pnf}

A {\em binary word} (or {\em string}) $w=w_1\cdots w_n$ over $\Sigma=\{0,1\}$ is a finite sequence of elements $w_i \in  \Sigma,$ for $i=1,\ldots,n$. Its length $n$ is denoted by $|w|$. We denote by $\Sigma^n$ the set of words over $\Sigma$ of length $n$, by $\Sigma^{*} = \cup_{n\geq 0} \Sigma^n$ the set of finite words  over $\Sigma$, and
the empty word by $\epsilon$.
Let $w\in \Sigma^{*}$. If $w=uv$ for some $u,v\in\Sigma^{*}$, we say that $u$ is a \emph{prefix} of $w$ and $v$ is a \emph{suffix} of $w$.  A \emph{factor} or \emph{substring} of $w$ is a prefix of a suffix of $w$.  We denote the set of factors of $w$ by $\textit{Fact}(w)$.  Let $w=w_1\cdots w_n\in \Sigma^*$, then the word $\tilde{w}=w_{n}w_{n-1}\cdots w_{1}$ is called the {\em reversal} of $w$. A word $w$ s.t.\ $w = \tilde{w}$ is called a {\em palindrome}.
A {\em binary language} is any subset $\cal L$ of $\Sigma^*$.

We denote by $|w|_{1}$ the number of $1$s in the word $w$; similarly, $|w|_0$ is the number of $0$s in $w$. The {\em Parikh vector} of a word $w$ over $\Sigma$ is defined as $p(w)=(|w|_{0},|w|_{1})$. The {\em Parikh set} of $w$ is $\Pi(w)=\{p(v) \mid  v\in \textit{Fact}(w)\}$, the set of Parikh vectors of the factors of $w$.
For example $p(011) = p(101) = (1,2)$ and $\Pi(011) = \{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)\} = \Pi(101) \cup \{(0,2)\}$.

Given a binary word $w$, we denote by $P_1(w,i)$ the number of $1$s in the prefix of length $i$ and by $\mathit{pos}_1(w,i)$ the position of the $i$th $1$ in the word $w$, i.e.\ $P_{1}(w,i) = |w_1\cdots w_i|_1$ and $\mathit{pos}_1(w,i) = \min\{ k : |w_1\cdots w_k|_1 = i\}$.  The functions $P_0$ and $\mathit{pos}_0$ are defined similarly.  Note that in the context of succint indexing, these functions are frequently called ${\textit{rank}}$ and ${\textit{select}}$, cf.~\cite{NavMaek07}: We have, for $x=0,1$, $ P_x(w,i) = {\textit{rank}}_x(w,i)$ and $ \mathit{pos}_x(w,i) = {\textit{select}}_x(w,i)$.

\subsection{Prefix normal words}

\begin{definition}[Maximum-ones and maximum-zeros functions]
Let $w\in \Sigma^*$. We define, for each $0\leq k\leq |w|$:
\begin{eqnarray*}
F_1(w,k) =  \max\{|v|_1 \mid v\in \textit{Fact}(w)\cap \Sigma^k\},
\end{eqnarray*}

\noindent the maximum number of $1$s in a factor of $w$ of length $k$.
When no confusion can arise, we also write $F_1(k)$ for $F_1(w,k)$.
The function $F_0(w,k)$ is defined analogously by taking $0$ in place of $1$.
\end{definition}

For a word $w$, we denote by $F_1(w)$ the function $k\mapsto F_1(w,
k)$ (and similarly with other functions taking arguments $w$ and $k$).

\begin{example}\label{ex:1}
 Take $w = 1010011011000111001011$. In Table~\ref{table:val}, we give the values of $F_{1}$ and $F_{0}$ for $w$.

\begin{table}
\centering
\begin{small}
\begin{raggedright}
\begin{tabular}{r || c *{29}{@{\hspace{2.1mm}}l}}
 $k$  &  0\hspace{1ex}  & 1\hspace{1ex} & 2\hspace{1ex} & 3\hspace{1ex} & 4\hspace{1ex} & 5\hspace{1ex} & 6\hspace{1ex} & 7\hspace{1ex} &
8\hspace{1ex} & 9\hspace{1ex} & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 &21 &22\\
\hline \rule[-6pt]{0pt}{22pt}
$ F_{1}$ &  0    & 1& 2& 3& 3& 4& 4& 4& 5& 6& 6& 7& 7& 7& 8& 8& 9& 10& 10& 10& 11& 11& 12  \\
$ F_{0}$ &  0    & 1& 2& 3& 3& 3& 4& 4& 5& 5& 6& 6& 7& 7& 7& 8& 8& 9& 9& 10& 10& 10& 10\\
\hline
\end{tabular}
\end{raggedright}\caption{\label{table:val}The sequences $ F_{1}$ and $ F_{0}$ for the word $w = 1010011011000111001011$.}
\end{small}
\end{table}
\end{example}

\begin{definition}[Prefix normal words]
A word $w\in \{0,1\}^*$ is called {\em \pword{1}} if $P_1(w) = F_1(w)$.
It is called {\em \pword{0}} if $P_0(w) = F_0(w)$.
In other words, $w$ is \pword{1} (\pword{0}) if and only if it does not have any factors with more $1$s (more $0$s) than the prefix of the same length. When not specified, then by \emph{prefix normal} we mean {\em \pword{1}}.
\end{definition}

\begin{example}  The word $w = 1100110$ is \pword{1}, but the word $w1 = 11001101$ is not \pword{1} because the factor $1101$ has three $1$s,
while the prefix of length $4$ has only two.   Also, $w$ is not \pword{0} since every \pword{0} word, except those of the form $1^*$,  must start with a 0.
\end{example}

We will soon see that it is possible to find, for every word $w$, a \pword{1} word which has the same maximum-ones function $F_1$ as $w$; and analogously for $0$. These will be called the prefix normal forms of $w$. To this end, we define the following equivalence; we will then see that equivalent words have the same prefix normal form.

\begin{definition}[Prefix equivalence]
Two words $v,w\in \Sigma^*$ are called \emph{\peq{1}} if $F_1(v) = F_1(w)$.
They are called \emph{\peq{0}} if $F_0(v) = F_0(w)$.
\end{definition}

\begin{example}
The words $11010, 10110, 01101, 01011$ are all \peq{1}, but not \peq{0}. When considering $0$, we have that $\{01011$, $11010$, $10101\}$ constitute one equivalence class,
and $\{01101, 10110\}$ another one (note that in the first class, there is an additional word not present in the 1-prefix equivalence class).
\end{example}

Next we will show that every equivalence class contains exactly one \normal{} word (Theorem \ref{thm:pnf}), which can thus be used as its representative.
This will allow us to associate two prefix normal words to every word $w$ (Definition \ref{def:pnf}). First we need the following lemma.

\begin{lemma}\label{lemma:Fa}
Let $w\in \Sigma^*$. Then, for all $0\leq i \leq j \leq |w|$:
$F_1(j) - F_1(i) \leq F_1(j-i)$.
\end{lemma}

\begin{proof}
Observe that if $v = yz$, then $|v|_1 \le F_1(|y|) + F_1(|z|)$.  Thus if $v$ is a length $j$ word such that $|v|_1 = F_1(j)$ and
$|y| = i$, then $F_1(j) \le F_1(i) + F_1(j-i)$. \qed
\end{proof}

\begin{theorem}\label{thm:pnf}
For every $w\in \Sigma^*$ there is a unique \pword{1} word $w'$ such that $F_1(w') = F_1(w)$;
similarly, there is a unique \pword{0} word $w''$ such that $F_0(w'') = F_0(w)$.
\end{theorem}

\begin{proof} We only give the proof for $w'$. The construction of $w''$ is analogous.

First note that if the \pword{1} words $u$ and $v$ are \peq{1}, then necessarily $u=v$. This holds because the prefix function $P_1$ determines the word, i.e.\ $P_1(u) = P_1(v)$ implies $u=v$ for {\em any} $u,v$. But since $u$ and $v$ are \pword{1} words, their prefix and maximum-ones functions coincide, and since they
are \peq{1}, we have $P_1(u) = F_1(u) = F_1(v) = P_1(v)$. This proves uniqueness.

Next, we will construct $w'$, given $w$. It is easy to see that for $1\le k\le |w|$, one has either $ F_1(w,k)= F_1(w,k-1)$ or $ F_1(w,k)=1+ F_1(w,k-1)$.
Now define the word $w'$ by

 $$w'_k = \begin{cases}
1 & \quad \text{if $ F_1(w,k)=1+ F_1(w,k-1)$}\\
0 & \quad \text{if $ F_1(w,k)= F_1(w,k-1)$}
\end{cases}$$
for every $1\le k\le |w|$.

By construction, we have $P_{1}(w',k) = F_{1}(w,k)$ for every $1\le k\le |w|$. We still need to show that $P_1(w',k) = F_1(w',k)$ for all $k$. This will prove that $w'$ is \pword{1}, as well as that it is \peq{1} to $w$.

By definition, $P_1(w',k) \leq F_1(w',k)$ for all $k$. Now let $v\in Fact(w')$, $|v|=k$, and $v = w_{i+1}\cdots w_j$. Then $|v|_1 = P_1(w',j) - P_1(w',i) = F_1(w,j) - F_1(w,i) \leq F_1(w,j-i) = P_1(w',j-i) = P_1(w',k)$, where the inequality holds by Lemma~\ref{lemma:Fa}.
We have thus proved that $ F_1(w',k) \leq P_1(w',k)$, and hence $w'$ is \pword{1}.
\qed
\end{proof}

\subsection{Normal forms and Parikh sets}

\begin{definition}[(Prefix) normal forms]\label{def:pnf}
Let $w\in \Sigma^*$. Then we denote by $\mathrm{PNF}_1(w)$ the unique \pword{1} word which is \peq{1} to $w$, and by $\mathrm{PNF}_0(w)$ the unique \pword{0} word which is \peq{0} to $w$. We refer to $\mathrm{PNF}_1(w)$ and $\mathrm{PNF}_0(w)$ as the {\em prefix normal form w.r.t.\ $1$ (resp.\ w.r.t.\ $0$)} or just {\em normal form w.r.t.\ $1$ (resp.\ w.r.t.\ $0$)} of $w$.
\end{definition}

\begin{example}
 Let  $w = 1010011011000111001011$.  The normal forms of $w$ are the words $$\mathrm{PNF}_{1}(w)=1110100110100101100101,$$  $$\mathrm{PNF}_{0}(w)=0001101010101101010111.$$

 \noindent Refer to Example~\ref{ex:1} for the values of the two functions $F_1(w)$ and $F_0(w)$.
 \end{example}

\medskip

The operators $\mathrm{PNF}_1$ and $\mathrm{PNF}_0$ are idempotent operators; i.e., if $u = \mathrm{PNF}_x(w)$ then $\mathrm{PNF}_x(u) = u$, for $x=0,1$.
This gives us an equivalent definition of prefix normality: a word $w$ is \pword{x} if $\mathrm{PNF}_x(w) = w$.  Also, for any $w\in \Sigma^{*}$ and $x\in \Sigma$, it holds that $\mathrm{PNF}_{x}(w)=\mathrm{PNF}_{x}(\tilde{w})$. Note further that if the equivalence class of $w$ contains only one element, then $w$ is necessarily prefix normal and a palindrome. In Table~\ref{table:classes4} we list all eight 1-prefix equivalence classes for words of length $4$.

\begin{table}[ht]
\begin{center}
\begin{small}
\begin{raggedright}
\begin{tabular}{l *{3}{@{\hspace{6mm}}c}}
$\mathrm{PNF}_{1}$   & Class  & Cardinality\\
\hline \rule[-2pt]{0pt}{3pt}\\
$1111$ & \{$1111$\} & 1\\
$1110$ & \{$1110$, $0111$\}& 2\\
$1101$ & \{$1101$, $1011$\}& 2\\
$1100$ & \{$1100$, $0110$, $0011$\}& 3\\
$1010$ & \{$1010$, $0101$\}& 2\\
$1001$ & \{$1001$\}& 1\\
$1000$ & \{$1000$, $0100$, $0010$, $0001$\}& 4\\
$0000$ & \{$0000$\}& 1\\
\hline \vspace{4mm}
\end{tabular}
\end{raggedright}
\caption{The sets of \peq{1} words of length $4$.\label{table:classes4}}
\end{small}
\end{center}
\end{table}

\medskip

The normal forms of a word allow us to determine the Parikh vectors of the factors of the word, as we will show in Theorem \ref{thm:charparset}. We first recall the following lemma from~\cite{CFL09} (which also appears to be folklore). We say that a Parikh vector $q$ {\em occurs} in a word $w$ if $w$ has a factor $v$ with $p(v) = q$.

\begin{lemma}[Interval Lemma~\cite{CFL09}]
\label{lemma:interval}
Let $w\in \Sigma^*$. Fix $1\leq k\leq |w|$.
If the Parikh vectors $(x_1,k-x_1)$ and $(x_2,k-x_2)$ both occur in $w$, then so does $(y,k-y)$ for any $x_1\leq y \leq x_2$.
\end{lemma}

The lemma can be proved with a simple sliding window argument, exploiting the fact that when a fixed size window is shifted by one, then the number of $1$s in the window changes by at most one.

\begin{theorem}\label{thm:charparset}
Let $w,w'$ be words over $\Sigma$. Then $\Pi(w) = \Pi(w')$ if and only if $\mathrm{PNF}_1(w) = \mathrm{PNF}_1(w')$ and $\mathrm{PNF}_0(w) = \mathrm{PNF}_0(w')$.
\end{theorem}

\begin{proof}
Let $f_1(w,k)$ denote the minimum number of $1$s in a factor of $w$ of
length $k$.
As a direct consequence of Lemma~\ref{lemma:interval}, we have that
for a Parikh vector $q=(x,y)$, $q\in \Pi(w)$ if and only if
$f_1(w,x+y) \leq x \leq F_1(w,x+y)$. Thus  for two words
$w,w'$, we have $\Pi(w) = \Pi(w')$ if and only if $F_1(w) =
F_1(w')$ and $f_1(w) = f_1(w')$.  It is easy to see that
for all $k$, $f_1(w,k) = k - F_0(w,k)$, thus the last
statement is equivalent to $F_1(w) = F_1(w')$ and $F_0(w)
= F_0(w')$. This holds if and only if $\mathrm{PNF}_1(w) = \mathrm{PNF}_1(w')$ and
$\mathrm{PNF}_0(w) = \mathrm{PNF}_0(w')$, and the claim is proved. \qed
\end{proof}

Define $I(w) = \{ (P_0(w,k),P_1(w,k)) \mid 0 \le k \le |w| \}$, the set of Parikh vectors
of all prefixes of $w$.  The following lemma is immediate.

\begin{lemma}
For all $w \in \Sigma^*$,
\[
\Pi(w) = \bigcup_{i=1}^{n} I(w_i \cdots w_n).
\]
\label{lemma:suffix}
\end{lemma}

There is an interesting geometrical way to view Lemma \ref{lemma:suffix} which we describe now.
Imagine each Parikh pair as the coordinates of a point in the Euclidean plane that has been rotated clockwise $\pi/4$ radians.
Each word $w$ can be interpreted as a polygonal path in this plane going up and to the right for each 1 ($\nearrow$) or
down and to the right for each 0 ($\searrow$), for each successive bit of $w$.  To obtain $\Pi(w)$ imagine grabbing
the polygonal path for $w$ and pulling it one step at a time through the origin, keeping track of the integer lattice
points that are hit after each pull (and ignoring the stuff to the left of the origin).
The normal forms $\mathrm{PNF}_{1}(w)$ and $\mathrm{PNF}_{0}(w)$ are obtained by forming polygonal paths starting at the origin, and
connecting the uppermost and the lowermost points of the region, respectively.

\vspace{-.2cm}
\begin{figure}[h]
\begin{center}
  \includegraphics[height=45mm]{esempio3bis.pdf}
  \caption{The word $w=1010011011000111001011$ (dark line), its normal forms $\mathrm{PNF}_{1}(w)=1110100110100101100101$ and $\mathrm{PNF}_{0}(w)=0001101010101101010111$ (lighter lines); the region between the two is the Parikh set of $w$; e.g.\  $w$ has a substring containing $5$ ones and $6$ zeros (black dot). Note that the axes giving the number of $0$s and $1$s are rotated by 45 degrees clockwise.}\label{fig:esempio}
\end{center}
\end{figure}

\subsection{Indexing for binary jumbled pattern matching}

Theorem~\ref{thm:charparset} is relevant for the problem known as Indexed Binary Jumbled Pattern Matching, which has attracted much interest recently. Recall that a Parikh vector over $\{0,1\}$ is a multiplicity vector of a string, i.e.\ it has non-negative integer entries.

\begin{quote}{\sc Indexed Binary Jumbled Pattern Matching (IBJPM)}\\
Given a  string $w$ of length $n$ over $\{0,1\}$, create an index which allows fast answers to queries of the following form: \\
\textbf{Input:} a Parikh vector $q$, \\
\textbf{Output:} return {\bf yes} if $q$ occurs in $\Pi(w)$, and {\bf no} otherwise.
\end{quote}

For $1\leq k\leq n$, let $f_1(w,k)$ be the minimum number of $1$s in a factor of length $k$, and $F_1(w,k)$, as before, the maximum number of $1$s in a factor of length $k$. It follows from Lemma~\ref{lemma:interval} that the answer for query $q=(x,y)$ is {\bf yes} if and only if $F_1(w,x+y) \geq x \geq f_1(w,x+y)$. Therefore, it suffices to store, for every $1\leq k \leq n$, the two numbers $F_1(w,k)$ and $f_1(w,k)$, and queries can be answered in constant time. The size of this data structure is $O(n)$.

All current solutions for IBJPM are based on this observation. The crux is how to construct this linear size data structure. The construction time of the index has steadily decreased since its first introduction: from $O(n^2)$~\cite{CFL09} to $O(n^2/\log n)$~\cite{BCFL10,MR10}, to $O(n^2/\log^2 n)$ in the word RAM-model~\cite{MR12}, to $n^2/2^{\Omega(\log n / \log\log n)^{1/2}}$~\cite{HLRW14}. The fastest solution at present is due to Chan and Lewenstein and has running time $O(n^{1.859})$~\cite{CL15}.

Normal forms are in effect an encoding of this linear size index. We have already seen that the $F$-function can be viewed as a binary string, namely $\mathrm{PNF}_1(w)$.
We have observed in the proof of Theorem \ref{thm:charparset} how the function $f_1(w)$ is determined by $F_0(w)$ and thus also by $\mathrm{PNF}_0(w)$, thus we have shown the following lemma.

\begin{lemma}
The answer for an IBJPM query $q=(x,y)$ is {\bf yes} if and only if $P_1(\mathrm{PNF}_1(w), x+y) \geq x \geq  P_1(\mathrm{PNF}_0(w), x+y)$.
\end{lemma}

Note that $P_1$ can be computed in constant time with constant time rank-queries on bit vectors, using only $o(n)$ bits of extra space~\cite{Munro96,Clark96}.

\begin{example}
Let $w=1001101$. Then the linear size data structure is given in the Table~\ref{table:lineards}, and the $F_1$ and $F_0$ functions in Table~\ref{table:lineards2}.

\begin{table}
\begin{center}
\begin{tabular}{c||cccccccc}
$k$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
$F_1(w,k)$ &  0    & 1& 2& 2& 3& 3& 3& 4\\
$f_1(w,k)$ &  0    & 0& 0& 1& 2& 2& 3& 4\\
\hline
\end{tabular}
\caption{The maximum and minimum number of $1$s for the word $w=1001101$.\label{table:lineards}}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{c||cccccccc}
$k$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
$F_1(w,k)$ &  0    & 1& 2& 2& 3& 3& 3& 4\\
$F_0(w,k)$ &  0    & 1& 2& 2& 2& 3& 3& 3\\
\hline
\end{tabular}
\caption{The maximum number of $1$s and $0$s for the word $w=1001101$. The normal forms of $w$ are $\mathrm{PNF}_1(w)=1101001$ and $\mathrm{PNF}_0(w) = 0011011$. \label{table:lineards2}}
\end{center}
\end{table}

\end{example}

At present, no faster computation of the normal forms is known than the algorithms cited above for the IBJPM problem. But the connection shown here implies that, should a fast normal form computation be found, it would immediately translate into a new solution for IBJPM.

\section{The language of prefix normal words}\label{sec:La}

In this section, we take a closer look at prefix normal words. We give several equivalent characterizations of prefix normality, explore some properties of prefix normal words, and then look at the language of prefix normal words. We denote by ${\mathcal L}_{\textrm{PN1}}\subset \Sigma^*$ the language of \pword{1} words, and by ${\mathcal L}_{\textrm{PN0}}\subset \Sigma^*$ the language of \pword{0} words. Note that these are exactly complemented, i.e.\ replacing every $1$ by a $0$ and vice versa, in each word of ${\mathcal L}_{\textrm{PN1}}$, yields ${\mathcal L}_{\textrm{PN0}}$. Therefore, every result about ${\mathcal L}_{\textrm{PN1}}$ has an equivalent formulation for ${\mathcal L}_{\textrm{PN0}}$, as well. Recall that whenever not further specified, we refer to 1-prefix normality. In Section~\ref{sec:preneck} only, we will talk about \pword{0} words, and we will show that ${\mathcal L}_{\textrm{PN0}}$ is strictly contained in the language of pre-necklaces, when adopting the usual order $0<1$ on the alphabet.

\subsection{General observations about prefix normal words}

We start with several characterizations of prefix normal words.

\begin{proposition}\label{prop:char}
Let $w\in \Sigma^{*}$. The following properties are equivalent:

\begin{enumerate}
\item $w$ is a prefix normal word;
\item $\forall i,j$ where $0\le i\le j \le |w|$, we have $ P_{1}(j) -  P_{1}(i) \leq  P_{1}(j-i)$;
\item $\forall v\in \textit{Fact}(w)$ such that $|v|_{1}=i$, we have $|v|\ge  \mathit{pos}_1(i)$;
\item $\forall i,j$ such that $i+j-1 \le |w|_{1}$, we have $ \mathit{pos}_1(i) +  \mathit{pos}_1(j) -1 \leq  \mathit{pos}_1(i+j-1)$.
\end{enumerate}
\end{proposition}

\begin{proof}

(1) $\Rightarrow$ (2). Follows from Lemma~\ref{lemma:Fa}, since $P_1(w) = F_1(w)$.

(2) $\Rightarrow$ (3). Assume otherwise. Then there exists $v\in \textit{Fact}(w)$ s.t.\ $|v| <  \mathit{pos}_1(k)$, where $k=|v|_1$. Let $v = w_{i+1}\cdots w_j$, thus $j-i=k$. Then $P_1(j) - P_1(i) = k$. But $P_1(j-i) = P_1(|v|) \leq k-1 < k = P_1(j) - P_1(i)$, a contradiction.

(3) $\Rightarrow$ (4). Again assume that the claim does not hold. Then there are $i,j$ s.t.\ $ \mathit{pos}_1(i+j-1) <  \mathit{pos}_1(i) +  \mathit{pos}_1(j) -1$. Let $k= \mathit{pos}_1(j)$ and $l =  \mathit{pos}_1(i+j-1)$ and define $v = w_k\cdots w_l$. Then $v$ has $i$ many $1$s. But $|v| =  \mathit{pos}_1(i+j-1) -  \mathit{pos}_1(j) + 1 <  \mathit{pos}_1(i) +  \mathit{pos}_1(j) - 1 -  \mathit{pos}_1(j) + 1 =  \mathit{pos}_1(i)$, in contradiction to (3).

(4) $\Rightarrow$ (1). Let $v\in \textit{Fact}(w)$, $|v|_1 = i$. We have to show that $P_1(|v|) \geq i$. This is equivalent to showing that $ \mathit{pos}_1(i) \leq |v|$. Let $v = w_{l+1} \cdots w_r$, thus $P_1(r) - P_1(l) = i$. Let $j = P_1(l)+1$, thus the first $1$ in $v$ is the $j$'th $1$ of $w$. Note that we have $l<  \mathit{pos}_1(j)$ and  $r\geq  \mathit{pos}_1(i+j-1)$. By the assumption, we have $ \mathit{pos}_1(i) \leq  \mathit{pos}_1(i+j-1) -  \mathit{pos}_1(j) + 1 \leq r-l = |v|$. \qed
\end{proof}

Next we formulate a characterization of the prefix normal property that will be useful in the enumeration of fixed-length prefix normal words (Section~\ref{sec:enumeration}).

\begin{lemma}
\label{lemma:equivDefPn}
Let $w\in 1\Sigma^*$. For some sequence of positive integers $r_1$, $r_2$, $\ldots$, $r_{d-1}$ we can write $w=10^{r_1-1}10^{r_2-1}\cdots 10^{r_d-1}$.
The word $w$ is prefix normal if and only if the following inequalities hold.
\begin{equation*}
\begin{array}{rcll}
r_1 &\leq& r_j \qquad & j=2, 3, \ldots, d-1 \\
r_1+r_2 &\leq& r_j+r_{j+1} \qquad & j=2, 3, \ldots , d-2 \\
&\vdots&& \vdots\\
r_1+r_2+\cdots + r_{d-2} &\leq& r_j+r_{j+1}+\cdots + r_{d-1} \qquad & j=2
\end{array}
\end{equation*}
\end{lemma}

\begin{proof}
Note that for $k=1, 2, \ldots d-1$, we have $\mathit{pos}_1(k) = 1+\sum_{j=1}^{k-1} r_j$. The statement of the lemma then follows by property (4) of Proposition \ref{prop:char}.
\qed
\end{proof}

We now give some simple facts about the language ${\mathcal L}_{\textrm{PN1}}$.

\begin{proposition}\label{prop:La_properties} Let ${\mathcal L}_{\textrm{PN1}}$ be the language of prefix normal words. \hfill \phantom{.}
\begin{enumerate}
\item ${\mathcal L}_{\textrm{PN1}}$ is prefix-closed, that is, any prefix of a word in ${\mathcal L}_{\textrm{PN1}}$ is a word in ${\mathcal L}_{\textrm{PN1}}$.
\item If $w\in {\mathcal L}_{\textrm{PN1}}$, then any word of the form $1^{k}w$ or $w0^{k}$, $k\ge 0$, also belongs to ${\mathcal L}_{\textrm{PN1}}$.
\item Let $|w|_1 <3$. Then $w\in {\mathcal L}_{\textrm{PN1}}$ iff either $w=0^n$ for some $n\ge 0$ or the first letter of $w$ is $1$.
\item Let $w\in \Sigma^{*}$. Then there exist infinitely many $v\in \Sigma^{*}$ such that $vw\in {\mathcal L}_{\textrm{PN1}}$.
\end{enumerate}
\end{proposition}

\begin{proof}
The claims {\em 1., 2., 3.} follow easily from the definition. For {\em 4.},  note that for any $n\ge |w|$, the word $1^{n}w$ belongs to ${\mathcal L}_{\textrm{PN1}}$. \qed
\end{proof}

We now deal with the question of how a prefix normal word can be extended to the right into another prefix normal word.

\begin{lemma}\label{lemma:test}
Let $w\in {\mathcal L}_{\textrm{PN1}}$. Then $w1\in {\mathcal L}_{\textrm{PN1}}$ if and only if for every $0\le k<|w|$ the suffix of $w$ of length $k$ has less $1$s than the prefix of $w$ of length $k+1$.
\end{lemma}

\begin{proof} Note that for all $1\leq k\leq |w|$, $P_1(w1,k)=P_1(w,k)$. Now if $w1\in {\mathcal L}_{\textrm{PN1}}$, then for the $k$-length suffix $u$ of $w$: $|u|_1 < |u1|_1 \leq P_1(w1,k+1) = P_1(w,k+1)$. Conversely, let $u$ be a factor of $w1$. If  $u$ is a factor of $w$, then $|u|_1\leq P_1(w,|u|)=P_1(w1,|u|)$. Else $u=u'1$, with $u'$ a suffix of $w$, and $|u|_1 = |u'|_1+1 < P_1(w,|u'|+1)+1 = P_1(w1,|u|)+1 = P_1(w1,|u|)+1$, and thus $|u|_1 \leq P_1(w1,|u|)$. Therefore, $w1\in{\mathcal L}_{\textrm{PN1}}$.
\qed
\end{proof}

We close this section by proving that ${\mathcal L}_{\textrm{PN1}}$ is not context-free.

\begin{theorem}\label{teor:CF}
${\mathcal L}_{\textrm{PN1}}$ is not context-free.
\end{theorem}

\begin{proof}
Recall that the intersection of a CFL with a regular language is a CFL.
We will show that $L' = {\mathcal L}_{\textrm{PN1}} \cap 1^* 0 1^* 0 1^*$ is not a CFL by using the pumping lemma.
Let $n$ be the constant of the pumping lemma and let $z = 1^n 0 1^n 0 1^n \in L'$.
Let $z = uvwxy$ be the usual factorization of the pumping lemma, where we may assume that
$|vx| \ge 1$, $|vwx| \le n$, and for all $i \ge 0$ we have $uv^iwx^iy \in L'$.
Clearly $vx$ cannot contain 0s.  If $vx$ contains some 1s from the first block of 1s in $z$, then
taking $i = 0$  give a contradiction since the third block of 1s is too long.
If $vx$ contains no 1s from the first block of 1s then taking $i = 2$ makes the second or
third block of 1s too long.  \qed
\end{proof}

\subsection{Connection with Lyndon words and pre-necklaces}\label{sec:preneck}

In this section we explore the relationship between the language ${\mathcal L}_{\textrm{PN0}}$ of prefix normal words w.r.t.\ $0$ and some known classes of words defined by means of lexicographic properties.  Note that in this section, when referring to prefix normality, we mean with respect to $0$. We assume the usual order $0<1$ on the alphabet.

A \emph{Lyndon word} is a word which is lexicographically strictly smaller than any of its proper non-empty suffixes. Equivalently, $w$ is a Lyndon word if it is the strictly smallest, in the lexicographic order, among its conjugates, i.e., for any factorization $w=uv$, with $u,v$ non-empty words, one has that the word $vu$ is lexicographically greater than $w$ \cite{LothaireAlg}. A word $w$ is a {\em power} if it can be obtained by concatenating two or more copies of another word, i.e.\ if there exists a non-empty $v$ and a $k>1$ such that $w=v^k$. A word that is not a power is called {\em primitive}. Note that, by definition, a Lyndon word is primitive. Let us denote by $Lyn$ the set of Lyndon words over $\Sigma$. One has that $Lyn\not\subseteq  {\mathcal L}_{\textrm{PN0}}$ and ${\mathcal L}_{\textrm{PN0}} \not\subseteq Lyn$. For example, the word $w=0101$ belongs to ${\mathcal L}_{\textrm{PN0}}$ but is not a Lyndon word since it is not primitive. An example of a Lyndon word which is not in normal form is $w=00110100111$.

A necklace is a Lyndon word or a power of a Lyndon word. A {\em pre-necklace} is a prefix of a necklace~\cite{Ruskey92} (also called  \emph{preprime word} \cite{Knuth42}, or \emph{sesquipower} or \emph{fractional power} of a Lyndon word \cite{ChHaPe04}). Let us denote by $P\!L$ the language of pre-necklaces.
The next proposition shows that every prefix normal word different from a power of the letter $1$ is a prefix of a Lyndon word.

\begin{proposition}\label{prop:preflin}
Let $w\in {\mathcal L}_{\textrm{PN0}}$ with $|w|_{0}>0$. Then the word $w1^{|w|}$ is a Lyndon word.
\end{proposition}

\begin{proof}
We have to prove that every rotation of $w' = w1^{|w|}$ is strictly greater than $w'$. If the rotation starts at a position within the second half of $w'$, then this is clearly true, since then its first character is $1$, while $w'$ starts with a $0$, $w$ being a prefix normal word containing at least one $0$. So let $v$ be a suffix of $w'$ of length at least $|w|+1$, and let $u$ be the longest common prefix of $v$ and $w'$. If $u=v$, then $v$ is a border (both a prefix and suffix) of $w'$, of length more than half its length, and thus $w'$ has a period of length $i = |w'| - |v| < |w|$, i.e., every character is the same as the one which follows $i$ positions later. Since the second half of $w'$ consists of $1$s only, this implies that so does the first half, contrary to our assumption. So $v$ is not a prefix of $w'$, and therefore $u$ is followed by two different characters in $v$ and in $w'$. Let us write $v=v'1^{|w|}$. If $|u|\geq |v'|$, then $u1$ is a prefix of $v$, implying that $u0$ is a prefix of $w'$, and thus $w'$ is smaller than $v$. If $|u|<|v'|$, assume that $u0$ is a prefix of $v$ and $u1$ of $w'$. Then $w$ has a substring ($u0$) which has more $0$s than the prefix of the same length ($u1$), a contradiction to $w$ being prefix normal. Therefore, again we have that $w'$ is smaller than $v$.
\qed
\end{proof}

We can now state the following result:

\begin{theorem}\label{theor:PL}
Every prefix normal word is a pre-necklace.
\end{theorem}

\begin{proof}
If $w$ is of the form $1^{n}$, $n\ge 1$, then $w$ is a power of the Lyndon word $1$, hence it is a pre-necklace. Otherwise, $w$ contains at least one $0$, thus by Proposition \ref{prop:preflin}, it is the prefix of a Lyndon word.  \qed
\end{proof}

The languages ${\mathcal L}_{\textrm{PN0}}$  and $ P\!L$, however, do not coincide. A shortest word in $ P\!L$ that does not belong to ${\mathcal L}_{\textrm{PN0}}$ is $w=00110100$.  Below we give the table of the number of words in ${\mathcal L}_{\textrm{PN0}}$ of each length $n\leq 16$, compared with that of pre-necklaces. Both sequences are listed in the On-Line Encyclopedia of Integer Sequences~\cite{sloane} (sequences A062692 and A194850), where the reader can find further terms.

\begin{table}[ht]
\centering
\begin{small}
\begin{raggedright}

\begin{tabular}{c || c *{29}{@{\hspace{2.1mm}}l}}
 $n$    & 1\hspace{1ex} & 2\hspace{1ex} & 3\hspace{1ex} & 4\hspace{1ex} & 5\hspace{1ex} & 6\hspace{1ex} & 7\hspace{1ex} &
8\hspace{1ex} & 9\hspace{1ex} & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\
\hline \rule[-6pt]{0pt}{22pt}
${\mathcal L}_{\textrm{PN0}}\cap \Sigma^{n}$ & 2 & 3 & 5 & 8 & 14 & 23 & 41 & 70 & 125 & 218 & 395 & 697 & 1273 & 2279 & 4185 & 7568 \\
$ P\!L\cap \Sigma^{n}$ & 2 & 3 & 5 & 8 & 14 & 23 & 41 & 71 & 127 & 226 & 412 & 747 & 1377 & 2538 & 4720 &
8800  \\
\hline
\end{tabular}
\end{raggedright}
\caption{\label{table:cardofL}The number of words in ${\mathcal L}_{\textrm{PN0}}$ and in $P\!L$ for each length up to 16.}
\end{small}
\end{table}

\section{Enumeration results about prefix normal words}\label{sec:enumeration}

Let $\textit{pnw}(n)$ denote the number of prefix normal words of length $n$.
It is an easy consequence both of Lemma~\ref{lemma:equivDefPn} and of Proposition~\ref{prop:La_properties} that $\textit{pnw}(n)$ grows exponentially. To see this, note that the conditions of Lemma~\ref{lemma:equivDefPn} are always satisfied if $r_1\leq r_2 \leq \ldots \leq r_k$, and thus the number of partitions of $n$ is a lower bound for $\textit{pnw}(n)$. On the other hand, Proposition~\ref{prop:La_properties} states that for all $w$, $1^{|w|} w$ is prefix normal, so $\textit{pnw}(2n) \geq 2^n$.

In Table~\ref{table:cardofL}, we give $\textit{pnw}(n)$ for $n$ up to $16$, the sequence for $n$ up to $50$ can be found in the On-Line Encyclopedia of Integer Sequences~\cite{sloane}, sequence A194850. In Fig.~\ref{fig:pnf_increase} we show the growth ratio for small values of $n$. Two interesting phenomena can be observed: the values seem to approach 2 slowly, i.e., the number of prefix normal words almost doubles as we increase the length by 1. Second, the values show on oscillation pattern between even and odd values.

\begin{figure}[h]
\begin{center}
\includegraphics[width=\textwidth]{pnf_increase_ratio1.pdf}
\end{center}
\caption{The value of $\textit{pnw}(n)/\textit{pnw}(n-1)$ for prefix normal words $w$ of length $n$, for $n \leq 50$ (loglinear scale).\label{fig:pnf_increase}}
\end{figure}

\subsection{Asymptotic bounds on the number of prefix normal words}\label{sec:enum1}

We give lower and upper bounds on the number $\textit{pnw}(n)$ of prefix normal words of length $n$.

\begin{theorem}

\label{thm:lowBound}
For $n$ sufficiently large
\begin{equation}
\textit{pnw}(n) \ge 2^{n-4\sqrt{n \log n}}.
\end{equation}
\end{theorem}

\begin{proof}
Let $k=k(n)$ be a positive integer to be fixed later. First we only consider words whose length, $n$, is a multiple of $2k$,
whose first $4k$ letters are $1$s, and in each of the following blocks of length $2k$, there are exactly $k$ $1$s and $k$  $0$s. The number of such words is  $\binom{2k}{k}^{(n-4k)/2k}$ and by construction, they are all prefix normal.

We use the inequality ${2k \choose k} \ge 2^{2k}/(2\sqrt{k})$ and substitute $k = \sqrt{n \log n}$ in the third step.
\begin{align*}
{2k \choose k}^{(n-4k)/2k}
& \ge \left( \frac{2^{2k}}{2\sqrt{k}} \right)^{n/(2k)-2} \\
& = \frac{2^n}{(2\sqrt{k})^{n/(2k)}} \frac{4k}{2^{4k}} \\
& = \frac{2^n}{2^{4\sqrt{n \log n}}} (2\sqrt{k})^{1-n/(2k)} \\
& \ge \frac{2^n}{2^{4\sqrt{n \log n}}}  \text{ for sufficiently large } n.
\end{align*}
The last inequality follows from the fact that $\lim_{n\rightarrow\infty} (2\sqrt{k})^{1-n/(2k)} = 0$ if $k = \sqrt{n \log n}$.
\qed
\end{proof}

Next we show how to obtain an upper bound on $\textit{pnw}(n)$, considering the length of the first 1-run.

\begin{theorem}
\label{thm:upBound}
For $n$ sufficiently large, we have $\textit{pnw}(n) \le 2^{n- \lg n + 1}$.
\end{theorem}

\begin{proof}
This will follow from enumeration results about pre-necklaces since every \pword{0} word is a pre-necklace.
Let $PL(n)$ be the number of pre-necklaces of length $n$.  In \cite{Ruskey92} it is shown (top of page 424) that
\[
PL(n) \le \sum_{i=1}^n \frac{2^i}{i} + \sum_{i=1}^n \sqrt{2^i}.
\]
They also show that (Lemma 5 of \cite{Ruskey92})
\[
\lim_{n \rightarrow \infty} \frac{n}{2^n} \sum_{i=1}^n \frac{2^i}{i} = 2.
\]
Thus, for large enough $n$, and fixed $\epsilon > 0$,
\[
PL(n) \le (1+\epsilon) \sum_{i=1}^n \frac{2^i}{i} \le (1+2\epsilon) 2^n/n \le 2^{n- \lg n + 1}.
\]
\hfill \qed

\end{proof}

\subsection{Exact formulas for words with fixed density.}\label{sec:enum2}

For a binary word $w$, its {\em density} is defined as the number of $1$s in $w$, i.e.\ as $|w|_1$. If we count the number of prefix normal words of length $n$ with a given fixed number of $1$s, we get exact results in a few cases. Let us denote by $\textit{pnw}(n, d)$ the cardinality of the set $\{w \in {\mathcal L}_{\textrm{PN1}} \cap \Sigma^n\mid |w|_1 = d\}$.

\begin{proposition}
\label{prop:genFunc}
For $d=0,1,\ldots,6$, we have the generating functions $f_d(x)=\sum_{n=0}^{\infty} \textit{pnw}(n,d)x^n$:
\begin{center}
\begin{minipage}{7.2cm}
\begin{eqnarray*}
f_0(x) &=&  \frac{1}{1-x}\\
f_1(x) &=&  \frac{x}{1-x}\\
f_2(x) &=&  \frac{x^2}{(1-x)^2}\\
f_3(x) &=& \frac{x^3}{(1-x^2)(1-x)^2}
\end{eqnarray*}
\end{minipage}
\begin{minipage}{7.2cm}
\begin{eqnarray*}
f_4(x) &=& \frac{x^4}{(1-x^3)(1-x)^3}\\[2mm]
f_5(x) &=&\frac{x^5(1+x+x^2)}{(1-x^4)(1-x^2)^2(1-x)^2}\\[2mm]
f_6(x) &=& \frac{x^6(1+x+x^2+x^3)}{(1-x^5)(1-x^3)(1-x^2)(1-x)^3}
\end{eqnarray*}
\end{minipage}
\end{center}
\end{proposition}

\begin{proof}
For $d\leq3$, one easily checks $\textit{pnw}(n,0)=\textit{pnw}(n,1)=1$, $\textit{pnw}(n,2)=n-1$ and $\textit{pnw}(n,3) = \floor{(n+1)^2/4}$, giving the desired functions.

For $d=4$, we calculate the number of positive solutions $r_1, r_2, r_3, r_4$ to the inequalities in Lemma \ref{lemma:equivDefPn}.
Let $q_1=r_1-1$, $q_4=r_4-1$, $d_2 = r_2-r_1$ and $d_3=r_3-r_1$. We are counting the nonnegative solutions of
\[
3q_1 + d_2 + d_3 + q_4 + 4 = n,
\]
which give generating function $f_4(x)$ by equating the coefficients of $x^n$ in the expansion of the following product:
\begin{gather}
(1+x^3+x^6+\cdots) (1+x+x^2+\cdots)^3\cdot x^4 \\
= \frac{x^4}{(1-x^3)(1-x)^3}.
\end{gather}
More complicated but manageable case analysis leads to the results for $d=5$ and $6$. \hfill \qed

\end{proof}

Similar formulas can be derived for $\textit{pnw}(n, n-d)$ for small values of $d$.
Unfortunately, no clear pattern is visible for $f_d(x)$ that we could use for calculating $\textit{pnw}(n)$.

The inequalities in Lemma \ref{lemma:equivDefPn} define linear diophantine equations. The general theory for enumerating solutions of such equations \cite{stanley} guarantees that there is a closed rational function form for the generating functions with the observed denominators, in \cite{LinDioph} there are algorithms for calculating these functions (which, however are not efficient enough to get results for much larger values of $d$). Above, we only discussed the first few simple cases. We did not succeed in extending our list of concrete formulas for the rational functions $f_d$ for $d>6$ using automated computation.

\subsection{Exact formulas for words with a fixed prefix.}\label{sec:enum3}

We now fix a prefix $w$ and give enumeration results on prefix normal words with prefix $w$. Our first result indicates that we have to consider each $w$ separately.

\begin{definition}
If $w$ is a binary word, let $\mathcal{L}_{\textrm{ext}}(w) = \{ w' : ww' \textrm{ is prefix normal} \}$, and $\mathcal{L}_{\textrm{ext}}(w, m) = \mathcal{L}_{\textrm{ext}}(w)\cap \Sigma^{m}$.
Let $\textit{ext}(w, m, d) = |\{ w' : ww'$  is prefix normal of length $|w|+m$  and density $d \}|$, and $\textit{ext}(w, m) = |\mathcal{L}_{\textrm{ext}}(w, m)|$.
\end{definition}

\begin{lemma}
\label{lemma:extLang}
Let $v, w \in 1\{0,1\}^*$ be both prefix normal. If $v\neq w$ then $\mathcal{L}_{\textrm{ext}}(v) \neq \mathcal{L}_{\textrm{ext}}(w)$.
\end{lemma}

\begin{proof}
We may assume $|v| \leq |w|$.\\
\emph{First case.} $v$ is not a prefix of $w$. Let $i$ denote the first position where they differ. If $v_i=1$ and $w_i=0$, then for $u=0^{|w|}v$ we have that $vu$ is prefix normal while $wu$ is not. If $v_i=0$ and $w_i=1$, then let $u=0^{|w|}w$. We have that $vu$ is not prefix normal but $wu$ is.\\
\emph{Second case.}
$v$ is a prefix of $w$. If $w$ has a 1 in any position after $|v|$, then we can proceed as in the first case. The remaining case is when $w = v0^m$ for some $m>0$. If $vv$ is prefix normal, then so must be $vvv$, but $v0^mvv$ cannot be. Otherwise, let $k\geq 1$ be the smallest integer (which is sure to exist) such that $v0^kv$ is prefix normal. Then $v0^{k-1}v$ is not prefix normal while $w0^{k-1}v$ is. This completes the proof.
\hfill \qed
\end{proof}

We were unable to prove that the growth of these two extension languages also differ.
\begin{conjecture}
Let $v, w \in 1\{0,1\}^*$ be both prefix normal. If $v\neq w$ then the infinite sequences $(\textit{ext}(v, m))_{m\geq1}$ and $(\textit{ext}(w,m))_{m\geq 1}$ are different.
\end{conjecture}

The values $\textit{ext}(w, m, d)$ seem hard to analyze. We give exact formulas for a few special cases of interest. Using Lemma \ref{lemma:equivDefPn}, it is possible to give formulas similar to those in Proposition \ref{prop:genFunc} for $\textit{ext}(w, m, d)$ for fixed $w$ and $d$. We only mention one such result.

\begin{lemma}
For $1\leq d\leq n$ we have $\textit{ext}(10, n+d-3, d)   = \textit{pnw}(n, d)$.
\end{lemma}

\begin{proof}
Consider the following map: let $w$ be an arbitrary word of length $n$ and density $d>1$, starting with $1$. Except for the starting $1$, insert a $0$ right before each subsequent occurrence of 1. This gives a word $w'$ of length $n+d-1$, starting with $10$ that does not contain the factor $11$. Clearly, the map is injective and all words of length $n+d-1$ starting with $10$ and containing no factor $11$ are obtained this way. In order to prove the lemma, we only need to show that prefix normality is preserved by the map and its inverse. For this, observe that there exists a prefix (resp.\ factor) of $w$ of length $k$ containing $r$ $1$s if and only if there exists a prefix (resp.\ factor) of $w'$ of length $k+r-1$ containing $r$ $1$s.
\hfill \qed
\end{proof}

The following lemma lists exact values for $\textit{ext}(w, |w|)$ for some infinite families of words $w$. Here $F(n)$ denotes the $n$th Fibonacci number, i.e.\ $F(1)=F(2)=1$ and $F(n+2) = F(n+1)+F(n)$.

\begin{lemma}
For all values of $n$ where the exponents are nonnegative, we have the following formulas:
\begin{center}
\begin{minipage}{7.2cm}
\begin{eqnarray*}
&&\textit{ext}(0^n,n) = 1\\[1mm]
&& \textit{ext}(1^n, n) = 2^n \\[1mm]
&& \textit{ext}(1^{n-1}0, n) = 2^n - 1 \\[1mm]
&& \textit{ext}(1^{n-2}01,n) = 2^n - 5 \\[1mm]
&& \textit{ext}(1^{n-2}00,n) = 2^n - (n+1)
\end{eqnarray*}
\end{minipage}
\begin{minipage}{7.2cm}
\begin{eqnarray*}
&&\textit{ext}((10)^{\frac n2}, n) = F(n+2) \textrm { if }n \textrm{ is even }\\[2mm]
&&\textit{ext}((10)^{\frac {n-1}2}1,n) = F(n+1) \textrm{ if }n\textrm{ is odd}\\[2mm]
&&\textit{ext}(10^{n-2}1,n) = 3\\[2mm]
&&\textit{ext}(10^{n-1},n) = n+1
\end{eqnarray*}
\end{minipage}
\end{center}

\end{lemma}

\begin{proof}
For $w=1^n$, $w=1^{n-1}0$, $w=1^{n-2}01$ and $w=1^{n-2}00$, it is easy to count those extensions that fail to give prefix normal words: None for $w=1^n$; only one for $w=1^{n-1}0$, namely $1^{n-1}01^n$; for $w=1^{n-2}01$, those extensions which contain a $1$-run of length $n-1$, namely $1^{n-2}$ followed by any two characters, or $01^{n-1}$; and for $w=1^{n-2}00$, those that contain at least $n-1$ many $1$s in the second half, i.e.\ with second half $1^n, 1^{n-1}0, 1^{n-2}01, \ldots, 01^{n-1}$.

Similarly, for $w=10^{n-2}1$, $w=10^{n-1}$ and $w=0^n$, counting the extensions that yield prefix normal words gives the result in a straightforward way.

Let $n$ be even. For $w=(10)^{\frac n2}$, note that $ww'$ is prefix normal if and only if $w'$ avoids $11$. The number of such words is known to equal $F(n+2)$. For $n$ odd, the argument is similar, with the prefix of interest, $w1$, being of length $n+1$, hence the previous Fibonacci number.
\hfill \qed
\end{proof}

\subsection{Some experimental results about enumeration of prefix normal words}\label{sec:enum4}

We consider extensions of prefix normal words by a single symbol to the right. It turns out that this question has implications for the enumeration of prefix normal words.

\begin{definition}[Extension-critical words]
We call a prefix normal word $w$ {\em extension-critical} if $w1$ is not prefix normal. Let $\textit{ecrit}(n)$ denote the number of extension-critical words in ${\mathcal L}_{\textrm{PN1}}\cap \Sigma^n$.
\end{definition}

The lemma below applies to any family of words $B$ for which $\varepsilon \in B$ and such that $x \in B$ implies $x0 \in B$.

\begin{lemma} For $n\geq 1$ we have
\begin{equation}
\label{eq:crit1}
\textit{pnw}(n) = 2\textit{pnw}(n-1) - \textit{ecrit}(n-1) = \textit{pnw}(n-1)\left(2-\frac{\textit{ecrit}(n-1)}{\textit{pnw}(n-1)}\right).
\end{equation}
From this it follows that
\begin{equation}
\label{eq:critProduct}
\textit{pnw}(n) = 2\prod_{i=1}^{n-1} \left(2-\frac{\textit{ecrit}(i)}{\textit{pnw}(i)}\right).
\end{equation}
\end{lemma}

\begin{proof}
The number of prefix normal words of length $n$ ending in $0$ is $\textit{pnw}(n-1)$, that of prefix normal words of length $n$ ending in $1$ is $\textit{pnw}(n-1)-\textit{ecrit}(n-1)$, hence we have  \eqref{eq:crit1}. The product form follows if we use $\textit{pnw}(n) = \textit{pnw}(1)  \prod_{i=1}^{n-1} \frac{\textit{pnw}(i+1)}{\textit{pnw}(i)}$. \qed
\end{proof}

\begin{lemma} For $n$ going to infinity, $\lim\inf \textit{ecrit}(n)/\textit{pnw}(n)  =  0$.
\end{lemma}

\begin{proof}
Assume that there exist an integer $N_0$ and a real number $\varepsilon > 0$ such that for $n\geq N_0$ we have $\textit{ecrit}(n)/\textit{pnw}(n) > \varepsilon$. Then by  \eqref{eq:critProduct} we would have $\textit{pnw}(n) = O((2-\varepsilon)^n)$, contradicting Theorem \ref{thm:lowBound}. \qed
\end{proof}

We conjecture that in fact the ratio of extension-critical words converges to $0$. We study the behavior of $\textit{ecrit}(n)/\textit{pnw}(n)$ for $n\leq 49$. The left plot in Fig.~\ref{fig:Crit} shows the ratio of extension-critical words for $n\leq 49$. These data support the conjecture that the ratio tends to $0$. Interestingly, the values decrease monotonically for both odd and even values, but we have $\textit{ecrit}(n+1)/\textit{pnw}(n+1) > \textit{ecrit}(n)/\textit{pnw}(n)$ for even $n$. We were unable to find an explanation for this.

The right plot in Fig.~\ref{fig:Crit} shows the ratio of extension-critical words multiplied by $n/\log n$. Apart from a few initial data points, the values for even $n$ increase monotonically and the values for odd $n$ decrease monotonically, and the values for odd $n$ stay above those for even $n$.

\begin{conjecture}
Based on empirical evidence, we conjecture the following:
\begin{eqnarray}
\textit{ecrit}(n) &=& \textit{pnw}(n) \Theta(\log n / n) ,\\
\textit{pnw}(n) &=& 2^{n-\Theta((\log n)^2)} .
\end{eqnarray}
\end{conjecture}

Note that the second estimate follows from the first one by  \eqref{eq:critProduct}.

\begin{figure}
\begin{minipage}[c]{6cm}
\begin{center}
\includegraphics[scale=0.3]{crit1}
\end{center}
\end{minipage}
\begin{minipage}[c]{6cm}
\begin{center}
\includegraphics[scale=0.3]{crit2}
\end{center}
\end{minipage}
\caption{The ratio $\frac{\textit{ecrit}(n)}{\textit{pnw}(n)}$ (left), and the value $\frac{\textit{ecrit}(n)}{\textit{pnw}(n)}\cdot\frac{n}{\ln n}$ (right).}
\label{fig:Crit}
\end{figure}

\section{Conclusion and open problems}
We introduced two new normal forms of binary words, the prefix normal forms with respect to $1$ and $0$, and showed how they arise naturally in the investigation of Parikh sets of binary words and jumbled pattern matching. We introduced prefix normal words (w.r.t.\ $1$ or $0$), words which equal their own normal form, and discussed several properties of these words. We showed results about the language of prefix normal words, among these that \pword{0} are strictly contained in the language of pre-necklaces. We also discussed extensively the growth behavior of the number of fixed-length prefix normal words.

Many open problems remain. It would be nice to have exact, or at least more precise asymptotic formulas for the enumeration of prefix normal words. Related to the enumeration, the strange oscillating behavior in Figures~\ref{fig:pnf_increase} and~\ref{fig:Crit} between odd and even values calls for an explanation.

Another question is testing binary words for prefix normality. Currently, no faster method is known (in worst-case running time), then calculating the normal form.

It would be an interesting direction to explore the connection between the normal forms w.r.t.\ $1$ and $0$, for example how many different values can $\mathrm{PNF}_0(w)$ take (and what can we say about them) if we fix $\mathrm{PNF}_1(w)$.

Finally, prefix normality could also be
defined over non-binary alphabets. In this case however, we do not obtain
an index directly applicable to jumbled pattern matching. Combinatorial or
formal language theoretic investigation and enumeration of prefix
normal words for general alphabets is subject of future work.

\section*{Acknowledgements}
Gabriele Fici was partially supported by the PRIN 2010/2011 project ``Automi e Linguaggi Formali: Aspetti Matematici e Applicativi'' of the Italian Ministry of Education (MIUR).  The research of Joe Sawada and Frank Ruskey was partially funded by grants from the National Engineering Research Council of Canada. We thank an anonymous referee for a very careful reading and helpful suggestions.

redpajama_set_name: RedPajamaArXiv


text:
Abu Dhabi school receives Dh1 million donation to promote students' tech skills
American Community School to engage students in new ways with focus on artificial intelligence, robotics, virtual reality and machine learning
Ismail Sebugwaawo
Published: Wed 10 Nov 2021, 5:16 PM
The American Community School of Abu Dhabi (ACS) has received a generous private-sector donation of Dh1 million from Raytheon Emirates Limited (REL) to help promote students' technological and critical thinking skills.
As an ACS partner since 2016, Raytheon's gift deepens support of educational initiatives that will inspire the next generation of scientists, engineers and business professionals.
Raytheon Emirates' investment will help ACS embed technology in every aspect of learning to encourage critical thinking, creativity and teamwork and will enable ACS students to further excel in science, technology, engineering and mathematics.
By leveraging Raytheon's expertise and investment, ACS will engage students in new ways with a focus on artificial intelligence, robotics, virtual reality and machine learning.
"I am grateful for Raytheon Emirates' ongoing support of ACS," said Monique Flickinger, ACS Superintendent. "Raytheon has demonstrated a long commitment to the school, including support of our award-winning Innovation Labs and other high-tech initiatives. Now, as they join a select group of cornerstone partners, ACS can leverage Raytheon's exceptional local talent and cutting-edge technology to equip students with the skills needed to thrive in a complex and competitive world."
Alan Davis, who is Raytheon Emirates' chief executive, toured the ACS campus, engaged with students in the Innovation Labs and commended ACS's faculty for inspiring students. He also presented a check to Monique Flickinger, Matt Ayoub, chair of the ACS Board of Trustees, and Serena Carnevale, vice chair of ACS Board of Trustees.
"Instilling a passion for math and science in young people has long been an objective of our company, and we are proud to have this opportunity to support the American Community School of Abu Dhabi in the next phase of its evolution," said Raytheon Emirates' chief executive Alan Davis. "With 34 years of experience serving the U.A.E in space, aviation and defense, we are committed to supporting leading non-profit organizations, like ACS, that share our mission of shaping the next generation of purpose-driven innovators and making a transformative impact on the local UAE community."
With nearly 50 years of institutional knowledge, ACS continues to provide exceptional programs that enhance young people's understanding of the world and enables them to design and engineer solutions to the future's most pressing problems.
"We are thrilled to expand our partnership with Raytheon at this pivotal moment in our school's history," said Matt Ayoub, chair of the ACS Board of Trustees. "Raytheon's support will provide critical resources and lead the way for other leading corporations to follow. I look forward to seeing how this important investment will impact ACS and the wider Abu Dhabi community for years to come."
ismail@khaleejtimes.com
More news from Schooling in UAE
New coding school opens up in Abu Dhabi
Sheikh Khaled inaugurates 42 Abu Dhabi which is the first GCC campus of the internationally renowned 42 Network of coding schools
Schooling in UAE3 months ago
Dubai: Some students unable to get seats on school buses
School says it is short on drivers; it is working to fix the issue

redpajama_set_name: RedPajamaCommonCrawl


Do I have to be a supply chain management major to join?
Absolutely not! We have a wide variety of business majors in our association. In addition, Engineering students, Education students, etc. have joined SCMA. If you are interested in what supply chain management has to offer, this is the place to be!
How much are dues to join the SCMA?
Is membership open all year?
Yes! You can become a member at any point throughout the year and we encourage you to do so!
Will I be behind if I join later in the semester?
SCMA encourages students to join at anytime throughout the year, therefore you will never be behind. What you get out of this organization is dependent on the effort you put in.
Can I come to the general membership meeting if I am not a member?
Absolutely, non-members are welcome to attend SCMA GMMs. However, all other events are limited to members. To attend these events, make sure to become a member!
Do I have to be a member to attend the events?
Except for general membership meetings and the SCM Career Fair, all other SCMA events are for members-only. Make sure to become a member!
Where are office hours held?
Office hours are held in the Supply Chain Management Department lobby, third floor BCC, by the elevators.
What are our office hours?
Come to a general membership meeting, attend an event, or stop by office hours!
How do I sign up for membership?
Sign up online and pay via PayPal or at one of our general membership meetings! Make sure when you sign up to take advantage of our networking and leadership opportunities! Ask for more details on how membership can benefit your future success here at MSU!
Do I have to be a member to go to the career fair?
No, however, priority fast-check-in will be given to SCMA members, as well as no charge at the door! Non-members will pay an additional fee for entrance.
Judy Jacobs, Director of Corporate & Student Relations, is the faculty advisor for SCMA.
How do I obtain a chair position?
Fill out the applications and make sure you talk to the appropriate Executive Board member about your interest!
How do I apply for the Executive Board?
Make sure to attend Leadership Academy in February!


I was given a Phase 2 IE Training in Ho Chi Minh City which means the class already did Phase 1. Phase 1 Training consisted of theory, computation, and application of Industrial Engineering in the apparel industry. The class was concluded with a summative assessment at the end and those who passed will have a training certificate.
While each participant already has a student manual, I do not have any material to start the training with. I need to prepare a PowerPoint presentation and I am thinking if I will align it with the student manual or with the final exam that was given during the Phase 1.
Anway, before the training we had a meeting with the factory and they requested certain topics as the focus of the Phase 2 training. Phase 2 usually is a form of an audit to check if the students still remember what they studied in Phase 1 and also practice the theories that they have learned but since the factory requested new topics to tackle and wanted to know how to implement change, I have to re-do my presentation to accommodate their request.
On the first day, I did a recap as a review of the past learning and also grouped them into teams to work on improvements. The class was composed on Koreans who have managerial positions and Vietnamese who have a staff level positions. To balance the team, I made sure that each team has at least 1 Korean and 1 Vietnamese. The whole week will be spent observing the factory production lines, monitoring their output and efficiency and finding ways to improve the current method, layout or process.
Each team needs to make a presentation of the data, findings, and proposals as the result of their study. Every day, I will go with 1 team and guide them on how they will go about their study. Sometimes, I will go with them just to observe how they work as a team and how they communicate with each other and the production leaders. Some teams work wonderfully in a group, but one team, in particular, is not so successful. Each individual has a different approach and ideas but has one goal. I explained to them that to be successful in their study, they have to listen to each other, disagree agreeably and work as a team.
In this training, I believe I have practiced both formative and informal assessment. Every day I will ask one member of each group to discuss their progress and in turn, I will give a comment or constructive feedback. What I will do on the next day will depend on how the class went during the day. Since the summative assessment was already done in Phase 1, it is optional in Phase 2 to give another assessment. The teams will be assessed based on their presentation and improvement outcome. The teams all did great in the end.
I was also planning to give them a short quiz at the end to gauge their learning, but since the team presentation went well, there is no need for this anymore. I have also planned to do peer assessment but the boss told me to dismiss the class early, thus it was not used.
Overall, I believe I achieved my goal of guiding them how to do improvement implementation and I am fortunate that I have the opportunity to apply what I learned in EDS113 in actual situations. Some of my students also came back to me to thank me for the guidance and support I gave them.
Robert Stake's maxim reminded me the difference between formative and summative assessment.
Indeed, every day is always an opportunity to learn something new.


Let me be straight here. I love the Oska Pulse. The week before I started using the device was the worst week of pelvic pain in my life. The week after? There was a glimmer of hope.
I want to go into more detail about what the device actually is and some of the pros and cons of it before I start going into details about how it's helped me.
But let me summarise first. While I am not going to tout it as a miracle cure, the Oska Pulse has helped me hugely in managing my various pain-related conditions (Endometriosis, Adenomyosis, Fibromyalgia).
I have been given this product as part of a product review through the Chronic Illness Bloggers network. Although the product was a gift, all opinions in this review remain my own and I was in no way influenced by the company. This post also contains affiliate links, which means if you click one of the product links I will get a small referral fee from any purchase. View my full Disclosure Policy.
I have gone from a daily 7-9 on the pain scale with pelvic cramps that had me unable to move on the floor three times a week to no cramps and a much more manageable steady 5 most days.
That, for me, is life changing and means I can now manage my pain. It is currently is only one of several tools I have to use to manage my pain, take any of them away and I'm in trouble. But before I added in the Oska Pulse I wasn't managing at all.
But more on that later, let's take a look at the device first.
The Oska Pulse is a blue oval device that delivers Pulsed Electromagnetic Field Therapy (PEMF).
This is basically an Electromagnetic field that stimulates your body to heal itself. I'll go into a bit more detail on how it works below.
The Oska Pulse is designed to target inflammation and pain at the site of injury. You don't have to wear it directly on your skin (it can be up to 8 inches away from the point you're treating) and it comes with a strap to help keep it attached if you're moving about.
To use it, just click the on button and it will run for 30 minutes, before beeping to let you know it's turning off. It flashes with a blue light whilst it is on too.
It's recommended to use it for 4-6 sessions per day at first, but you may be able to reduce this over time. Some people get some immediate relief but, particularly for chronic pain, you may need to be a bit more patient.
You might get some pain relief quickly but things like mobility can take a bit longer to improve.
I personally saw some immediate relief and also a slower long-term improvement.
P.S. if you order one yours may look slightly different to mine as they've recently updated the look of the device.
First of all, because this is what people think when you try and explain PEMF technology, it isn't a TENS device. You won't feel it doing anything.
The Electromagnet basically pulses and creates a force on the electrical charge in your cells, changing their behaviour and promoting healing and reducing inflammation.
I have read some of the scientific explanations for this and only just understand them, certainly not enough to confidently explain it back to you. So, for those of you who want a bit more detail, this is a good explanation: Brett Wade. A Review of Pulsed Electromagnetic Field (PEMF) Mechanisms at a Cellular Level: A Rationale for Clinical Use. American Journal of Health Research.
I'm going to be upfront here. This isn't a cheap solution to pain. It costs $399. Although, Oska Wellness has given me a discount for my readers of $55 if you use the code LAURASPEN.
It is a big investment. But they do offer a "no questions asked" 30-day money-back guarantee if you aren't satisfied with the Oska Pulse. And a reduction in pain may result in a reduction of costly medications, but, obviously, that will entirely depend on how you react to the device and your current situation.
Most of my readers are in the United States, but if you're not please also take into account international shipping fees and any customs/import duties.
How practical is it to use?
Once you press the little on button it goes for 30 minutes before discreetly beeping to let you know it's turning off. This is fairly quiet and unobtrusive if you're somewhere quiet. I don't work but if I did I'd happily sit with it on my lap without worrying the occasional beeping would upset anyone around me.
In a noisy environment, you will need to keep checking it to see if it's turned off.
It also flashes blue while it is working. It doesn't come with anything to cover it but I would recommend doing so if you suffer from migraines. I tend to wear it under my clothes, which covers it anyway.
The Oska Pulse comes with a strap to help you attach it to your body if you need to. But to be honest, if you are using it for the recommended amount of time 4-6 x 30-minute sessions a day, then you may well be able to fit this in when you're at home anyway.
It doesn't need to be directly on the skin. I will sometimes just rest it on my belly or on the sofa cushion directly behind my shoulder. I'm at home all day though so I don't need to feel self-conscious about other people seeing it.
One thing that may upset Adenomyosis or Endometriosis sufferers who are struggling to conceive is that, if you wear it strapped to your belly whilst out and about, it can make you like you're pregnant, which may invite unwanted comments.
I'm going to split this into two. As I've already talked about my Pelvic pain in my intro, let me start with my shoulder pain, which is down to Fibromyalgia and Endometriosis on my diaphragm.
Basically, the current working theory from my Physio is that I have an oversensitive nerve in the base of my neck causing referred pain from my neck, across to my shoulder. And all the muscles around it get upset and tighten up. We are working on increasing mobility in the neck and strengthening muscles.
Apparently, this is a common Fibromyalgia problem.
My Endometriosis specialist thinks the Endometriosis on my diaphragm is probably to blame, which irritates a nerve, again causing referred pain in the shoulder tip.
In truth, probably both are working together, making this a fairly complex problem. And both are causing secondary muscular pain.
So has the Oska Pulse helped? I've been using it for about a month and a half and had some immediate relief.
I still have a base level of pain that no-one and nothing have been able to alleviate but if I do something to irritate it (like my Physiotherapy exercises or certain movements) using the device calms it back down to my baseline. And I haven't had any big flares since using it.
Previously my shoulder pain was all over the place in terms of severity.
I haven't noticed an extra improvement over time in terms of pain but it's great that if I do something to irritate it I can whack on the device and it calms down, rather than running to the microwave constantly to warm up my wheat bags.
And no flares? That's brilliant. I wouldn't be able to think sometimes because my muscles locked up so much and the pain was so bad.
Interestingly, my Physiotherapist commented at my last appointment (which is the only time I've seen her since using the Oska Pulse), that my muscles were much more relaxed. I've been in and out of Physiotherapy for about two years and they normally only ever comment that my muscles are tight.
There's still room for improvement here. I may have to update you if I get greater improvement as time goes on. But I've made more progress with it than with two years of Physiotherapy.
Now let's move on to where the device really wowed me.
These are the issues I have causing Pelvic pain: I have had expert excision surgery for my Endometriosis but I have deep infiltrating Endometriosis on my bowel that will require bowel resection to remove. I have suspected Adenomyosis which is a condition where Endometrial tissue is found inside the muscular wall of the uterus. It is also suspected that more adhesions (scar tissue that can bind organs together) formed after my surgery.
When I received the Oska Pulse I was about ready to ask for a hysterectomy despite the fact I want children. This is not a treatment for Endometriosis, I need to stress this as many doctors mistakenly tell patients it is (Endometriosis by its nature occurs outside the uterus and also produces its own oestrogen).
But it is a cure for Adenomyosis. Unfortunately, it's quite a dramatic one.
I had just experienced the worst week of pain of my life. I had cramps on three days that left me unable to move on the floor for several minutes. The rest of the time it felt like someone was simultaneously burning and grating the entire insides of my pelvis.
I had been told to double my progesterone-only birth control pill and prescribed Diclofenac suppositories to reduce inflammation. I'd been on these for several weeks and still, things just seemed to be getting worse.
My whole body was tense and painful in reaction to the pelvic pain. My Fibromyalgia was having a field day.
Then the Oska Pulse arrived and I can't explain the emotional and physical relief. I had some (fairly dramatic) relief immediately and by the end of the week, I was a changed woman. My pain was there but manageable. I could forget about it. It wasn't there constantly screaming at me. And the rest of my body relaxed.
Now, I got a bit cocky and stopped my Diclofenac. Bad idea. The pain returned. I'm now prescribed them as needed rather than for constant use. I'm having a mini flare now because I left it too long before restarting them. But it's nearly back under control after a couple of days. It still didn't get as bad as before. And I didn't have any cramps!
The Oska Pulse means it seems possible to manage my Adenomyosis for now, rather than being forced (by my body, not anyone else) to remove my uterus.
I really can't stress how life-changing this is for me. But one thing. I did go a bit mad and use the device pretty much constantly for a while.
Now, a common co-condition with pelvic conditions like mine is pelvic floor dysfunction, caused by a build-up of and over-tight muscle that forms in reaction to the constant irritation of the muscles. I think what was happening was that over-use of the device was irritating my already tight muscles. I get a different pain from my pelvic muscles and this is what seemed to be hurting.
I had a day off from the device and started using it as per instructions (with a cheeky extra session or two as I go off to sleep) and no more problems on this count.
So, I hope this review has been helpful for you. If you'd like more information please do check out the Oska Pulse website or you can follow them on Facebook. And don't forget, if you do go on to purchase, use the code LAURASPEN for $55 off.


Giant Eagle Supermarket can be found at 5055 Library Road, Suite 5 . The following is offered: Grocery Stores, Bakeries, Delicatessens, Food Manufacturers & Processors, Produce Retailers, Pharmacies . In Bethel Park there are 6 other Grocery Stores. An overview can be found here.


There is a song by Halestorm called Mz. Hyde and I found that I could identify with it a bit. Living with Bi-Polar disorder, well sometimes I am Ms. Hyde and sometimes I'm Dr. Jekyll, just depends on the day, sometimes the moment. And, one really never knows in advance which girl you will be dealing with, including myself. Dealing with Schizophrenia hasn't been easy either, seeing & hearing things that I swear are real and really haven't had many in my life who can relate. Here's a poem that talks about my struggles with Bi-Polar & Schizophrenia, how it shapes my life, and how I refuse to let it hinder me.
i like the realness of the topic and the fact that you share it. i hope you will take some time to comment on the art of the other folks on the site….it might help get everyone talking. thanks!


text: Low (as opposed to high) culture, parts of which are known as kitsch and camp. With the increasing economic power of the middle- and lower-income populace since the beginning of the Industrial Revolution in the nineteenth century, artists created various new diversions to answer the needs of these groups. These have included pulp novels and comic books, film, television, advertising, "collectibles," and tract housing. These have taken the place among the bourgeois once taken among the aristocracy by literature, opera, theater, academic painting, sculpture, and architecture. But modernist artists rarely cultivated the popular success of these new cultural forms. Modernist works were little appreciated outside of a small elite. Life magazine's 1950s articles on the abstract expressionist Jackson Pollock (American, 1912-1956), and the silkscreened paintings by Andy Warhol (American, 1928?-1987) of soup cans and celebrities signaled unprecedented fusions between high and low art and the transition to the postmodern age.Quotations: "Popularity is the crown of laurel which the world puts on bad art. Whatever is popular is wrong." Oscar Wilde (1854-1900), Anglo-Irish playwright, author. Lecture, June 30, 1883, to students of the Royal Academy, London (published in Aristotle at Afternoon Tea: The Rare Oscar Wilde, 1991). "The artist should never try to be popular. Rather the public should be more artistic." Oscar Wilde. "The fact is popular art dates. It grows quaint. How many people feel strongly about Gilbert and Sullivan today compared to those who felt strongly in 1890?" Stephen Sondheim (1930-), contemporary American composer, lyricist. International Herald Tribune (Paris, June 20, 1989). "Popular art is the dream of society; it does not examine itself." Margaret Atwood (1939-), Canadian novelist, poet, critic. "A Question Of Metamorphosis," interview in Malahat Review, no. 41 (1977; reprinted in Conversations, edited by Earl G. Ingersoll, 1990). "Popular culture is the new Babylon, into which so much art and intellect now flow. It is our imperial sex theater, supreme temple of the western eye. We live in the age of idols. The pagan past, never dead, flames again in our mystic hierarchies of stardom." Camille Paglia (1947-), American author, critic, educator. Sexual Personae, chapter 4 (1990). Also see brummagem, counterculture, ephemera, gewgaw, high art, low art, mass media, memorabilia, paint-by-number, Pop Art.


These days, travel is anything but 'standard'. With the steady rise in boutique hotels, unique accommodations, and innovative technology, luxury brand PR and a deft touch of personalized guest experience are all required in this extremely competitive market. This is why hospitality PR and travel PR must make a crucial contribution.
Of course, with all that is new and exciting, comes the question: How does a hotel stay at the forefront of the movement? How can a hotelier capitalize on this evolution to maximize their offerings and subsequent revenue model?
More than anything, how can you continuously put your hotel at the forefront of innovation with ideas that can make you stand out from the competition and keep guests coming back? Hotel PR and a creative and powerful strategy together with flawless execution by a boutique public relations agency wise choices for success.
Luckily, we have the answers for you.
With millennial and solo travelers on the rise and twenty-five percent saying they will travel solo in 2018, hotels should look beyond traditional hotel rooms and layouts to include more non-traditional spaces. If your offering includes a blend of hotel amenities and alternative accommodations – you open yourself up to myriad of different travelers (millennials, solo travelers, young couples, bleisure travelers, families, baby boomers and more). This could include shared sleeping areas for up to multiple guests, and private rooms for families or groups.
By catering to this wider range of guest preferences, hotels can remain competitive against the rising market of vacation rentals and Airbnb's. After all, guests today not only love authentic spaces, but also crave hotels offering their own personalities and unique experiences.
An extreme example of this approach can be seen with Peru's Skylodge Adventure Suites; a boutique hotel offering 'transparent luxury capsule' rooms which hang off the side of a mountain. Accessing these rooms, in fact, involves climbing up a few hundred feet or zip lining, if that's more your speed.
Each room is about 24 feet long and 8 feet wide with enough room for four beds and is crafted out of aerospace aluminum and weather resistant polycarbonate. As the capsule is completely transparent (with the exception of a private bathroom), guests are treated with a 300-degree view of the Urubamba Valley. Not surprisingly, this experience comes at a price, with each room coming at a $1,000/night fee.
Any hotel hoping to maximize their marketing strategy knows that social media marketing and online reviews simply can't be ignored. However, it's not just important to occupy social platforms that are popularly used by guests. Rather, hoteliers should be leveraging those platforms for what they are: a personalized look at each guest's personality desires and travel experience.
Tapping into this generation of travelers through blogger PR and SEO PR will reach those who are eager to share their experiences, opinions and lifestyle with the likes of their online followers. In this way hotels, through engaging a luxury brand PR agency have an opportunity to know their guests better than ever before. This also allows hotel staff to be more readily responsive to guest demands and/or complaints, a capability which can drastically improve guest experience.
Not only can hotels use this public information shared by their guests to better predict their travel expectations, but they can also use the relevance of aesthetically driven platforms like Instagram as design influence. Tell you market about it through engaging a luxury brand PR agency. Many travelers determine their next vacation inspiration from Instagram, favoring those picturesque landscapes and bright color schemes, innovative design quirks or popular quotes/messaging that are splayed across their newsfeed. You can see this marketing tactic at work in hotels (and other businesses), which feature quirky lines, song lyrics, and unusual designs etc. on their walls, stairs, products and more.
We've said this once, and we will say it time and time again: the future is mobile. A mobile device is quite often a guest's most important travel accessory, and the more power they have within that device (as it relates to their travel experience) the better. Your luxury brand PR agency can help with promoting this for maximum exposure on the web.
The highly mobile guest experience extends to reservations, pre-arrival messages, mobile check-in, access to a hotel room with a mobile key, special offers, upgrades, mobile checkout and more. Allow guests the opportunity to bypass reception and use their smartphones to not only open their doors, but to choose their level of experience right from the palm of their hand. Talk to your luxury PR firm about getting the message out about what you are doing.
Of course, the desire for mobile-friendly hotels also includes modern travelers' penchant for apps, with hotels around the world creating user-friendly, integrated apps for their guests. These often allow guests to choose their room, order extra pillows or towels, call a cab, order food, and control the lighting and thermostat and more. This design is convenient as much as it is low-touch, allowing guests to choose a more independent experience if that's what they prefer.
Some hotels have even gone as far as implementing 'Emoji Room Service', where guests can simply text emojis from the in-room menu to a dedicated number and the order is brought to their room. This is luxury travel brand PR at its most authentic when it is set to spin in the news.
Today's travel and hospitality landscape is all about the guest, and today's guests want an experience that is mobile, convenient, unique and entirely personalized. With this understanding in place, your hotel has the tools to create an offering that will remain at the forefront of innovation and hospitality evolution.
Never before have hotel PR and the spin that a luxury brand PR agency can provide been more important. Get the news out through mainstream media like Conde Nast Traveler and blogs, as well as TV exposure on the Travel Channel. Talk to your boutique PR firm — and Abelow PR is always here to help.


Open Source project contribution focuses a lot on the code committed to projects, but there is so much more that goes on behind the scenes that is just as valuable to FOSS than the code itself.
LABHR seeks to find those that provide these non-code contributions, and thank them.
LABHR started as an idea by Leslie Hawthorn. She advocates openly thanking people on social media, and writing recommendations.
This idea was extended by Katie McLaughlin with her work on automating this process on GitHub.


text:
Deed Worth
Success Dictionary
35 Inspirational Barbara Corcoran Quotes On Success
By Asad Meah
Barbara Corcoran is an American businesswoman, investor, speaker, consultant, syndicated columnist, author, and television personality. As a television personality, she is a "Shark" investor on ABC's Shark Tank. May her quotes inspire you to be yourself and live your dreams.
1. "Finding opportunity is a matter of believing it's there." Barbara Corcoran
2. "Stop putting it off! Procrastination breeds guilt, guilt breeds depression, and depression breeds failure." Barbara Corcoran
3. "The difference between successful people and others is how long they spend time feeling sorry for themselves." Barbara Corcoran
4. "Some of the worst pitches are the people who talk all fancy who've been to business school." Barbara Corcoran
5. "My best successes came on the heels of failures." Barbara Corcoran
6. "Stop comparing yourself to everyone else around you." Barbara Corcoran
7. "If you're minding someone else's business, no one is minding yours." Barbara Corcoran
8. "I consider rejection a lucky charm." Barbara Corcoran
9. "Your heart must always be in it. That's part of an entrepreneurs DNA." Barbara Corcoran
10. "When you're building a business, you're either all in, or you're not." Barbara Corcoran
11. "Procrastination is the enemy of success and the guilt of not doing something always steals your energy." Barbara Corcoran
12. "All the best things that happened to me after I was rejected. I knew the power of getting past no." Barbara Corcoran
13. "If I could set a world record, it would be that I have 150 business partners, all with thriving businesses of their own, that started with nothing, and I made the difference to make them all billionaires." Barbara Corcoran
14. "In business, you're the chief salesman. Create a sense of demand, rather than waiting to have demand." Barbara Corcoran
15. "You don't need an MBA to launch a business. You need street smarts and grit." Barbara Corcoran
16. "Always choose attitude over experience. Always." Barbara Corcoran
17. "Most great entrepreneurs I know are nothing like the other kids." Barbara Corcoran
18. "If people like you, they're going to want to do business with you. And if they don't you're going to have an almost insurmountable obstacle to overcome." Barbara Corcoran
19. "You don't have to get it right, you just have to get it going." Barbara Corcoran
20. "The biggest challenge in business is not the competition, it's what goes on inside your own head." Barbara Corcoran
21. "You can catch a great attitude from great people." Barbara Corcoran
22. "Every single failure has an equally great upside if you are willing to stay in the game." Barbara Corcoran
23. "Walk in their shoes and see what they see within the first eight seconds." Barbara Corcoran
24. "Play what you've got and don't waste time worrying about what you don't." Barbara Corcoran
25. "Don't you dare underestimate the power of your own instinct." Barbara Corcoran
26. "People imitate their leader. Lead by example." Barbara Corcoran
27. "People most resistant to fun need it the most." Barbara Corcoran
28. "I turned $1,000 into a billion-dollar business." Barbara Corcoran
29. "I had twenty-two jobs before I started my business at the age of twenty-three and I didn't want one more boss telling me what to do. So I was motivated simply because I didn't want a boss." Barbara Corcoran
30. "Everytime you push through failure there's always a prize for you on the other side. " Barbara Corcoran
31. "I have a theory and I really believe it. I think your worst weakness can become your greatest strength." Barbara Corcoran
32. "I love myself." Barbara Corcoran
33. "Insecurity is a wonderful motivator." Barbara Corcoran
34. "I built the business exactly the way my mother built and ran her family. I wanted a replication of the big, happy family I grew up in. I wanted happy people having fun." Barbara Corcoran
35. "Never be ashamed of who you are. People always recognize and appreciate authenticity." Barbara Corcoran
Share With Others To Help Them Awaken!
Millionaire Success
Success Quality
Previous article35 Inspirational Daisaku Ikeda Quotes On Success
Next article35 Inspirational Imam Al-Ghazali Quotes On Success
Asad Meah
My name is Asad Meah, I am the CEO & Founder of AwakenTheGreatnessWithin. I am a dreamchaser who has gained a wealth of knowledge in entrepreneurship and personal development over the past five years through self-education. My mission is to inspire millions of people to become entrepreneurs by awakening their minds to their greatness that resides within them.
35 Inspirational Will Rogers Quotes On Success
35 Inspirational Avicii Quotes On Success
35 Inspirational Kevin Gates Quotes On Success
DO YOU WANT TO IMPROVE YOUR LIFE? Download this free eBook On Goals!
Subscribe now and receive a free eBook on Goals! and be the first to receive all the latest updates!
https://www.youtube.com/watch?v=rUY2PzagY7U
35 Inspirational Quotes On Curiosity
35 Inspirational Mark Zuckerberg Quotes On Success
35 Inspirational Keanu Reeves Quotes On Success
Why Have People Stopped Dreaming?
25 Inspirational Quotes On Quitting
20 Inspirational Sara Blakely Quotes
39 Inspirational Quotes On The Power Of Habits
© Copyright 2019 - AwakenTheGreatnessWithin


This policy states the requirements for the awarding, disbursement, renewal, cancellation, and reinstatement of institutional tuition merit scholarships.
The dollar values of these scholarships are listed in Appendix A.
With the exceptions set forth in policy statement 3.A. and 3.B., an institutional tuition scholarship award will be made to each student who meets the award criteria set forth in this policy.
Freshman Colorado Resident Achievers Tuition Scholarship and Freshman Nonresident Achievers awards cannot exceed $75,000, with Colorado resident awards counting $1,000 toward the maximum and nonresident awards counting $2,500 toward the maximum.
Freshman New Mexico Reciprocal Scholarship awards are limited to 30 freshmen and 15 transfer students each academic year, with a total number of awards to not exceed 135 at any time.
The application for admission serves as the application for institutional tuition merit scholarships.
Freshman Colorado Resident Achievers Tuition Scholarship and Freshman Nonresident Achievers Tuition Scholarship – A awardee must be admitted as a first-time freshman in the Fall semester and, on the date of admission, have a CCHE Admission Index of 95 or higher and qualify as college-level in English and mathematics under the Colorado Commission on Higher Education policy Section I, Part E, Statewide Remedial Policy.
When the number of students who meet the eligibility requirements is greater than the number of available scholarships, the Director of Admission may prioritize recipients according to these criteria.
Good fit, with students expected to exceed average retention and graduation rates receiving higher priority.
Freshman Colorado Resident Tuition Merit Scholarship and Colorado Nonresident Tuition Merit Scholarship – An awardees must be admitted as a first-time freshman in a Fall or Spring semester and, on the date of admission, have a CCHE Admission Index of 95 or higher.
New Mexico Reciprocal Scholarship – An awardee must be admitted as a first-time freshman in a Fall or Spring semester and, on the date of admission, have a CCHE Admission Index of 100 or higher, be a permanent resident of New Mexico, and qualify as college-level in English and mathematics under the Colorado Commission on Higher Education policy Section I, Part E, Statewide Remedial Policy or be admitted as a transfer student in a Fall or Spring semester; be pursuing his or her first baccalaureate degree; and, have on the date of admission, a permanent address in the State of New Mexico, a cumulative college grade point average of 3.00 or higher, and qualify as college-level in English and mathematics.
Transfer Colorado Tuition Merit Scholarship and Transfer Nonresident Tuition Merit Scholarship – An awardee must be admitted as a transfer student in a Fall or Spring term; be pursuing his or her first baccalaureate degree; and, on date of admission, have a cumulative college grade point average of 3.00 or higher.
Appeals for an increased award amount based on changes to the CCHE Admission Index or cumulative college grade point average after the date of admission are not allowed.
Students may receive only one institutional tuition merit scholarship.
Students receiving benefits under Fort Lewis College policy 4-13 Tuition Reduction Benefit Program for Spouses and Dependent Children are eligible for a tuition merit scholarship but the scholarship will be applied last, after the tuition reduction, and after any external agency tuition benefits, up to the cost of in-state tuition.
Students receiving full tuition benefits from an external agency are not eligible for an institutional tuition merit scholarship.
Students receiving partial tuition benefits from an external agency are eligible for the institutional tuition merit scholarship, but the scholarship will be applied last, after the external agency tuition benefits, up to the cost of tuition, unless an agreement with an external agency specifies otherwise.
Any time new information is received by Fort Lewis College pertinent to the eligibility requirements, exclusions, and reductions addressed in this policy, the Office of Financial Aid will adjust a student's scholarship award. This includes but is not limited to change of tuition classification from nonresident to resident, discovery that a student haw an earned baccalaureate degree, notification of a tuition scholarship awarded by an external agency, and qualification for the Native American Tuition Waiver.
Students will be notified of tuition merit scholarship awards by letter to the permanent address by the Director of Admission and of any subsequent exclusions or reductions by email to the Fort Lewis College account by the Director of Admission or the Director of Financial Aid.
Institutional tuition merit scholarships can only be applied to Fort Lewis College tuition expenses.
Scholarships will be disbursed at 50% of the annual award amount each Fall and Spring semester. Under no circumstances will the scholarship be disbursed in one payment for the full annual award.
A maximum of 50% of an annual scholarship award may be approved for disbursement by the Scholarship Appeals Committee in a Summer semester upon appeal by a senior who can graduate in August instead of December.
A student must be enrolled in a minimum of 12 credits each Fall and Spring semester at Census date to be eligible for disbursement.
Scholarship disbursements are applied automatically to the Fort Lewis College tuition bill by the Assistant Controller A/R.
Institutional tuition merit scholarships are renewable up to 120 earned credits or eight semesters, whichever comes first.
Credit Counting Protocol -- All earned college-level credits, including credits earned through evaluation of prior learning or transfer, count toward the 120 credit limit.
Semester Counting Protocol – The eight semester limit will be counted out from the student's term of matriculation.
All students receiving a tuition merit scholarship, regardless of whether the initial award was in a Fall or Spring semester, will be evaluated for renewal criteria after the positing of grades by the Registrar for the Spring semester.
For renewal of a scholarship for the next academic year, students receiving a tuition merit scholarship in both the Fall and Spring semesters must have a cumulative grade point average of 2.00 or higher on college-level coursework taken at Fort Lewis College.
An exception will be made for first-time freshmen matriculating in the Fall semester who may have a cumulative grade point average below 2.00 if the term grade point average for the Spring semester was 2.00 or higher. These students will be considered probationary and must meet the condition of a cumulative grade point average of 2.00 or higher for subsequent renewals.
For renewal of a scholarship for the next academic year, students who have received a tuition merit scholarship in Fall and Spring must have earned 30 credits, remedial or college-level, at Fort Lewis College at the time of evaluation with a grade of A, B, C, D, P, or S.
Credits earned through prior learning assessment or transfer prior to matriculation do not toward the 30-credit minimum.
An exception to the 30-credit minimum will be made for first-time freshmen matriculating in the Fall semester who have earned at least 24 credit hours. These students will be considered probationary and must meet the condition of 30 earned credits each academic year for subsequent renewals.
For renewal of the scholarship for the next academic year, students receiving a tuition merit scholarship only in the Spring semester must have a cumulative grade point average of 2.00 or higher on college-level coursework taken at Fort Lewis College.
An exception to the 2.00 cumulative grade point average rule will be made for first-time freshmen who earned a cumulative grade point average of 1.75 or higher. These students will be considered probationary and must meet the condition of a cumulative grade point average of 2.00 or higher for subsequent renewals.
For renewal of the scholarship for the next academic year, students who have received a tuition merit scholarship only in the Spring must have earned 15 credits, remedial or college-level, at Fort Lewis College at the time of evaluation with a grade of A, B, C, D, P, or S.
An exception to the 30-credit rule will be made for first-time freshmen who earned at least 12 credits in the Spring semester. These students will be considered probationary and must meet the condition of 30 earned credits each academic year for subsequent renewals.
Students who do not accept their tuition merit scholarship through processes established by the Director of Financial Aid by Census date of the first payment period will have their scholarship cancelled, unless an earlier deadline was established by the Office of Admission.
Students who do not meet the terms and conditions for disbursement set forth in Section III will have their scholarship cancelled.
Students receiving the tuition merit scholarship who do not meet the renewal criteria in Section IV will have their scholarship cancelled.
Students who fail to attend consecutive Fall and Spring semesters after award of the scholarship will have their scholarship cancelled.
Enrollment in a Summer semester cannot substitute for failure to enroll in a Fall or Spring semester for purposes of meeting the continuous enrollment standard.
Enrollment in but subsequent withdrawal from a term is considered failure to attend continuously.
Students who have earned 120 credits or received the scholarship for eight semesters will have their scholarship cancelled.
Students will receive notification of scholarship cancellation via email to their Fort Lewis College account.
Appeals for reinstatement of a tuition merit scholarship or an increase in the amount of a tuition merit scholarship due to loss of external agency benefits are allowed.
A completed and signed Scholarship Cancellation Appeals Form and supporting documentation must be submitted by the published deadline at the Office of Admission in Kroeger Hall for an appeal to be considered by the Scholarship Appeals Commitee. The deadlines, form, submission instructions and additional items are published ast www.fortlewis.edu/scholarhsips.
The Scholarship Appeals Committee membership is: the Associate Vice President for Enrollment Management, Chair; Chair, Director of Admission, Scholarship Coordinator for the Office of Financial Aid, Scholarship Manager for the Fort Lewis College Foundation; and the Assistant Controller A/R.
The Scholarship Appeals Committee will issue a response to all appeals submitted by the final deadline for a semester to a student's Fort Lewis College email account.
The Scholarship Appeals Committee will consider a student's personal statement, supporting documentation, and academic and disciplinary history and standing in making its decision.
The Scholarship Appeals Committee should make decisions consistent with the intention of the scholarship to incentivize on-time graduation and the academic requirements for degree completion.
Approval for immediate reinstatement of partial scholarship amount, with or without conditions.
Decisions of the Scholarship Appeals Committee may be appealed to the President. The President's decision is final.
This policy provides a framework for the management of the variables of the institutional tuition merit scholarship program that impact the institution's discount rate.
Difference between non-resident tuition and resident tuition student's share cost..
Difference between non-resident tuition and resident tuition student's share cost.


October 15, 2008, is the deadline to submit letters of intent for symposium proposal for the SLEEP 2009 23rd Annual Meeting of the Associated Professional Sleep Societies, LLC. The letters of intent will be used by the Program Committee to identify potential overlap among submitted proposals that needs to be resolved early and to identify gaps in the scientific program that need to be filled. Submission of your letter of intent will enhance the likelihood of your symposium being accepted.
A list of potential speakers plus the possible titles of their talks.
Note: potential speakers do not need to be contacted at this time.
A template for the letter of intent is located on the SLEEP 2009 Web site at www.sleepmeeting.org. The letter must be submitted via e-mail to Amber Josi, Meeting Planner: ajosi@aasm.org. The Program Committee will provide feedback concerning your letter of intent in early November 2008. A final version of the symposium proposal must be submitted online via the SLEEP 2009 Web site by December 1, 2008.