text:
\subsection{Negative results}

In the previous subsection we showed the strongly positive result that, on non-recursive games or games with finite target languages, the existence of a dominant strategy always implies that there exists a \emph{strongly regular} dominant strategy. We now turn to the negative results of this section and show that the above implication does not generalise to arbitrary games or to undominated strategies; in fact, the following theorem states that even much weaker statements do not hold in general.

\begin{theorem}\label{theo:wrong}
  \begin{enumerate}[(a)
  \item 	There exists a game $G_1$ with a regular dominant strategy but no forgetful dominant strategy.\label{it:negA}
  \item There exists a game $G_2$ with a forgetful regular dominant strategy but no strongly regular dominant strategy.\label{it:negB}
    \item The statements (a) and (b) hold also when ``dominant'' is replaced by ``undominated''. In this case, $G_1$ and $G_2$ can even be chosen as non-recursive games with a finite target language.
  \end{enumerate}
\end{theorem}

\full{
\begin{proof
  \begin{enumerate}[(a)
  \item The game $G_1=(\Sigma,R,T)$ with $\Sigma=\{a\}$, the only replacement rule being $a\to aa$ and $L(T)=\{a^k\mid k\ge 2\}$ has the stated property. The strategy plays Call exactly if it has not seen any symbol $\call{a}$. Since this strategy wins on every word, it is dominant. However, a forgetful strategy that plays Call on the first symbol $a$ is bound to play Call forever, and therefore does not win on any word. On the other hand, a forgetful strategy that plays Read on the first symbol $a$ does not win on the word $a$ and is therefore not dominant, either.
  \item Let $G_2=(\Sigma,R,T)$ with $\Sigma=\{a,b,c,d\}$, rule set $R$ given by
\begin{align*}
&a\to b\\
&c\to ac\\
&d\to bad
\end{align*}
and the target language automaton $T=(Q,\Sigma,\delta_T,q_0,F)$ depicted in Figure~\ref{fig:dominant45wrongT}. We claim that the regular forgetful strategy~$\sigma_{\mathcal A}$ based on the automaton $\mathcal A$ shown in Figure~\ref{fig:dominant45wrongA} fulfils $W(\sigma_{\mathcal A} )=\Sigma^*$ and is thus dominant.
\begin{figure}[ht]
\centering
\begin{subfigure}{.5\textwidth}
\centering
\begin{tikzpicture}[xscale=2.3,yscale=2.3,>=stealth',initial text=,initial distance=1.5ex,every state/.style={inner sep=0pt,minimum size=1.5em}]
\node[state,initial,accepting] at (0,1) (q0) {$q_0$};
\node[state,accepting] at (0,0) (q1) {$q_1$};
\node[state] at (1,0.5) (q2) {$q_2$};
\path[->] (q0)	edge[loop above]	node[above] {$a,d$} ()
				edge[bend left]		node[right] {$b$} (q1)
				edge				node[above] {$c$} (q2)
		  (q1)	edge[bend left]		node[left]	{$b,c$} (q0)
				edge				node[below] {$a,d$} (q2)
		  (q2)	edge[loop above]	node[above] {$a,b,c,d$} ();
\end{tikzpicture}
\caption{Target language automaton $T$}\label{fig:dominant45wrongT}
\end{subfigure
\begin{subfigure}{.5\textwidth}
\centering
\begin{tikzpicture}[xscale=2.3,yscale=2.3,>=stealth',initial text=,initial distance=1.5ex,every state/.style={inner sep=0pt,minimum size=1.5em}]
\node[state,initial] at (0,2) (q0) {$q_0$};
\node[state] at (0,0) (q0') {$q'_0$};
\node[state] at (2,1) (q1) {$q_1$};
\node[state,accepting] at (0.6,1) (q3) {$q_3$};
\path[->] (q0)	edge[loop above]	node[above] {$d$} ()
				edge		node[left] {$a$} (q0')
				edge				node[above] {$b$} (q1)
				edge	node[left] {$c$} (q3)
		  (q0')	edge[bend left]		node[left]	{$d$} (q0)
				edge				node[below] {$b$} (q1)
				edge				node[right] {$a,c$} (q3)
		  (q1)	edge[bend right]		node[above] {$b,c$} (q0)
				edge				node[above] {$a,d$} (q3);

\end{tikzpicture}
\caption{Strategy automaton $\mathcal A$; missing transitions lead into a non-accepting sink state (not shown).} \label{fig:dominant45wrongA}
\end{subfigure}
\caption{Automata used in the proof of Theorem~\ref{theo:wrong}~(b)}
\end{figure}
Indeed, by induction on the length of $w$, the following is easy to show: for each input word $w$, the strategy $\sigma_\ensuremath{{\mathcal A}}\xspace$ yields a terminating play with a final string $u$ such that:
$\delta_T(q_0,u)=\delta_\ensuremath{{\mathcal A}}\xspace(q_0,u)$, if $u$ does not end with $a$, and $\delta_T(q_0,u)=q_0$ and $\delta_\ensuremath{{\mathcal A}}\xspace(q_0,u)=q_0'$, otherwise.

However, for a strategy automaton $\mathcal B=(Q\cup\{\ensuremath{\mathit{Call}}\xspace\},\Sigma,\delta_{\mathcal B},q_0,\{\ensuremath{\mathit{Call}}\xspace\})$ of a strongly regular strategy $\sigma_{\mathcal B}$, it holds that $W(\sigma_{\mathcal B})\subsetneq\Sigma^*$, and thus no such $\sigma_{\mathcal B}$ is dominant.
For a proof of this claim, we can assume that $\delta_{\mathcal B}(q_0,c)=\delta_{\mathcal B}(q_1,a)=\delta_{\mathcal B}(q_1,d)=\ensuremath{\mathit{Call}}\xspace$ since otherwise $\sigma_{\mathcal B}$ would lose on $c$, $ba$ or $bd$. If $\delta_{\mathcal B}(q_0,a)=q_0$, then the play of $\sigma_{\mathcal B}$ on $ac$ is infinite. On the other hand, if $\delta_{\mathcal B}(q_0,a)=\ensuremath{\mathit{Call}}\xspace$, then play of $\sigma_{\mathcal B}$ on $ad$ is infinite.
\item For the analogon of (a), let $G_1=(\Sigma,R,T)$ over the alphabet $\Sigma=\{a,b,c,d,e\}$ with the set of rules $R$ given by
	\begin{align*}
		&a\to b+c\\
		&b\to cd\\
		&c\to e
	\end{align*}
	and target language $L(T)=\{e,cd\}$. It is not hard to see that the strategy that plays Call on $(\epsilon,a)$, $(\epsilon,b)$, $(\epsilon,c)$, $(\call{a},b)$ and $(\call{a},c)$ and Read otherwise is regular, wins on $\{a,b,c,e\}$, and is undominated.

Towards a contradiction, let us assume that $\sigma$ is a forgetful strategy for $G_1$ that is undominated. We show first that $\sigma$ does not win on $a$. Suppose $\sigma$ does win on $a$. Then $\sigma(\epsilon,a)=\sigma(\epsilon,b)=\ensuremath{\mathit{Call}}\xspace$. If $\sigma(\epsilon,c)=\ensuremath{\mathit{Read}}\xspace$, then the play
$(\epsilon,a),(\call a,c),(\call ac,\epsilon)$
of $\sigma$ on $a$ is losing -- contradiction. If $\sigma(\epsilon,c)=\ensuremath{\mathit{Call}}\xspace$, then the play
$$(\epsilon,a),(\call a,b),(\call a\call b,cd),(\call a\call b\call c,ed),(\call a\call b\call ce,d),(\call a\call b\call ced,\epsilon)$$
of $\sigma$ on $a$ is losing -- contradiction.

It is also easy to see that no strategy can win on a word that starts with $a$ and has length at least $2$. A one-pass strategy $\sigma'$ that wins on all words from $W(\sigma)$ and also on $a$ can be defined by
\[\sigma'(\alpha, f)=
\begin{cases}
\ensuremath{\mathit{Call}}\xspace,&\text{if $\alpha f\in\{a, \call a b, \call a c\}$,}\\
\ensuremath{\mathit{Read}}\xspace,&\text{if $\alpha f=\call a\call b c$,}\\
\sigma(\alpha, f),&\text{otherwise}
\end{cases}\]
for $\alpha\in\hist{\Sigma}^*$, $f\in\Sigma_f=\{a,b,c\}$. Since $W(\sigma)\subsetneq W(\sigma)\mathbin{\dot{\cup}}\{a\}=W(\sigma')$, it follows that $\sigma$ is not undominated.

For the analogon of (b), consider the game $G_2=(\Sigma,R,T)$ over the alphabet $\Sigma=\{a,b,c\}$ with rules given by
\begin{align*}
	&a\to bb+cbc\\
	&b\to cc
\end{align*}
and target language automaton $T$ as per Figure~\ref{fig:optimal45wrongT}. The finite target language is $L(T)=\{bbc,bcc,cbc,ccc\}$.

\begin{figure}[ht]
	\centering
	\subcaptionbox{Target language automaton $T$\label{fig:optimal45wrongT}}[.5\textwidth]{
		\centering
		\begin{tikzpicture}[xscale=2.3,yscale=2.3,>=stealth',initial text=,initial distance=1.5ex,every state/.style={inner sep=0pt,minimum size=1.5em}]
		\node[state,initial] at (0,0) (q0) {$q_0$};
		\node[state] at (0.8,0) (q1) {$q_1$};
		\node[state] at (1.6,0) (q2) {$q_2$};
		\node[state,accepting] at (2.4,0) (q3) {$q_3$};
		\node[state] at (1.2,1) (q4) {$q_4$};
		\path[->] (q0)	edge node[above] {$b,c$} (q1)
		edge[bend left] node[left] {$a$} (q4)
		(q1)	edge node[above] {$b,c$} (q2)
		edge node[left] {$a$} (q4)
		(q2)	edge node[above] {$c$} (q3)
		edge node[right] {$a,b$} (q4)
		(q3)	edge[bend right] node[right] {$a,b,c$} (q4)
		(q4)	edge[out=135,in=45,loop] node[above] {$a,b,c$} ();
		\end{tikzpicture}}
			\subcaptionbox{Strategy automaton $\mathcal A$\label{fig:optimal45wrong4}}[.5\textwidth]{
		\centering
		\begin{tikzpicture}[xscale=2.3,yscale=2.3,>=stealth',initial text=,initial distance=1.5ex,every state/.style={inner sep=0pt,minimum size=1.5em}]
		\node[state,initial] at (0,0) (p0) {$q_0$};
		\node[state] at (0,2) (p1) {$q_1$};
		\node[state] at (3,0) (p2) {$q_2$};
		\node[state] at (3,2) (p3) {$q_3$};
		\node[state] at (2.2,1) (p4) {$q_4$};
		\node[state,accepting] at (1,1) (p5) {$q_5$};
		\path[->] (p0)	edge node[left] {$b$} (p1)
		edge node[below] {$c$} (p2)
		edge node[below] {$a$} (p5)
		(p1)	edge node[above] {$c$} (p3)
		edge node[right] {$a,b$} (p5)
		(p2)	edge node[below right] {$b,c$} (p3)
		edge node[below] {$a$} (p5)
		(p3)	edge node[above] {$c$} (p4)
		edge node[above] {$a,b$} (p5)
		(p4)	edge[out=-45,in=35,loop] node[right] {$c$} ()
		edge node[below right] {$a,b$} (p5);
		\end{tikzpicture}}
	\caption{Automata used in the proof of Theorem~\ref{theo:wrong}~(c)}
\end{figure}

We claim that the regular forgetful strategy $\sigma_{\mathcal A}$ based on the automaton $\mathcal A$ shown in Figure~\ref{fig:optimal45wrong4} is undominated. It can be checked easily that $W(\sigma_{\mathcal A})=\{a,bb,bcc,cbc,ccc\}$. The only words that are not in $W(\sigma_{\mathcal A})$ even though a strategy exists that wins on them are $bc$, $bbc$ and $cb$. However, a one-pass strategy that wins on $bc$ cannot win on $bcc$; a strategy that wins on $bbc$ cannot win on $bb$; a strategy that wins on $cb$ cannot win on $cbc$. Therefore, every one-pass strategy that wins on a word on which $\sigma_{\mathcal A}$ does not win also loses on a word on which $\sigma_{\mathcal A}$ wins. Hence, there exists no strategy $\sigma$ with $W(\sigma_{\mathcal A})\subsetneq W(\sigma)$, which means that $\sigma$ is undominated.

It remains to show that there exists no undominated strongly regular strategy for $G$.
Let $B=(Q\cup\{\ensuremath{\mathit{Call}}\xspace\},\Sigma,\delta_{\mathcal B},q_0,\{\ensuremath{\mathit{Call}}\xspace\})$ be the strategy automaton of a strongly regular strategy $\sigma_{\mathcal B}$. Observe that $\sigma_{\mathcal B}$ cannot win on $a$: In order to win on $a$, a strategy must play Call in the configurations $(\epsilon,a,\epsilon)$ and $(\call ab,b, \epsilon)$ and it must play Read in the configurations $(\call a,b,b)$ and $(\call ac,b,c)$. But a strongly regular strategy must play the same in the configurations $(\call ab,b,\epsilon)$ and $(\call ac,b,c)$, because both have $T$-state $q_1$ and current symbol $b$. However, we can find a one-pass strategy $\sigma$ with $W(\sigma_{\mathcal B})\subsetneq W(\sigma_{\mathcal B})\mathbin{\dot{\cup}}\{a\}=W(\sigma)$. Indeed, such a strategy can be defined by
\begin{align*}
\sigma(\alpha,f)=
\begin{cases}
\ensuremath{\mathit{Call}}\xspace,&\text{if $(\alpha,f)=(\epsilon,a)$ or $(\alpha,f)=(\call ab,b)$,}\\
\ensuremath{\mathit{Read}}\xspace,&\text{if $(\alpha,f)=(\call a,b)$ or $(\alpha,f)=(\call ac,b)$,}\\
\sigma_{\mathcal B}(\alpha,f),&\text{otherwise}
\end{cases}
\end{align*}
for $\alpha\in\hist{\Sigma}^*$ and $f\in\Sigma_f=\{a,b\}$. Hence, $\sigma_{\mathcal B}$ is not undominated.
\end{enumerate}
\vspace{-\baselineskip}
\end{proof}
 }

\subsection{Positive results}

Our positive results are summarised in the following theorem.

\begin{theorem}\label{theo:right}
  \begin{enumerate}[(a)
  \item Every game with the bounded depth property has a  weakly dominant strategy.
  \item Every prefix-free game has a regular weakly dominant strategy.
  \item Every game with a finite target language that has a dominant strategy has a strongly regular dominant strategy.
  \item Every non-recursive game with a dominant strategy has a strongly regular dominant strategy.
  \item Every unary game has an undominated strategy.
  \end{enumerate}
\end{theorem}
Since every non-recursive game trivially has the bounded-depth property, it also has an undominated strategy by part (a). Games with a finite target language constitute a  further class with the bounded-depth property and with regular undominated strategies \cite[Corollary 4.15]{Coester15}.

A concept used in the proofs of parts (a) and (d) is the convergence of a sequence of one-pass strategies.

\begin{definition}
	A sequence $(\sigma_k)_{k\in\mathbb N}$ of strategies \emph{converges to} a strategy $\sigma$ if for each $n\in\mathbb N$ there exists $k_0\in\mathbb N$ such that for each $k\ge k_0$ and $(\alpha,a)\in\hist{\Sigma}^{\le n}\times\Sigma$ it holds that $\sigma(\alpha,a)=\sigma_k(\alpha,a)$.
\end{definition}

\full{
	This is the same as the convergence in the metric space of strategies where the metric $d$ is given by $d(\sigma,\sigma)=0$ and $d(\sigma,\sigma')=\frac{1}{n}$ for $\sigma\ne\sigma'$, where $n$ is minimal such that there exists $(\alpha,a)\in\hist{\Sigma}^n\times\Sigma$ and $\sigma(\alpha,a)\ne\sigma'(\alpha,a)$.
}

\begin{lemma}[Convergence Lemma]\label{lemma:conv}
	Let $G$ be a game and $(\sigma_k)_{k\in\mathbb N}$ be a sequence of one-pass strategies that converges to some one-pass strategy $\sigma$. Let  $L_1\subseteq L_2 \subseteq \cdots$ be an infinite sequence of languages such that, for every $k$, $L_k\subseteq W(\sigma_k)$ and let $L\df \displaystyle \bigcup_{k\in\mathbb N} L_k$.

	Then $\sigma$ wins on every word $w\in L$ for which it terminates.
\end{lemma}
\full{
	\begin{proof}
		Towards a contradiction, suppose that $\sigma$ loses on a word $w\in L$. Then there exists a strategy of Romeo with which he wins the (finite) play $\Pi=\Pi(\sigma,\tau,w)=(K_0,\dots,K_n)$. Let $k_0\in\mathbb N$ be such that for each $k\ge k_0$ and $(\alpha,a)\in\hist{\Sigma}^{\le n}\times\Sigma$ it holds that $\sigma(\alpha,a)=\sigma_{k}(\alpha,a)$. Let furthermore $k_1$ be such that $w\in L_{k_1}$ and let $k\df \max(k_0,k_1)$.
		Then $\Pi$ is also a play of $\sigma_{k}$ on $w$. But then $\sigma_k$ loses on $w\in L_{k_1}\subseteq L_k$, the desired contradiction.
	\end{proof}
}

\short{In the next section, we give the proof of part (a). In the subsequent section, we sketch the proofs of parts (b), (c) and (d). We also explain our motivation for prefix-freeness, which we consider the most relevant case and with the most interesting proof.}

\subsubsection{Games with the bounded depth property}\label{sec:boundedDepth}

Before we prove Theorem~\ref{theo:right}~(a), we define some further notation.
For a strategy $\sigma$ and some $i\ge0$, we denote by $\restr{\sigma}{i}$ the restriction of $\sigma$ to the first $i$ rounds of the game. Thus $\restr{\sigma}{i}$ is a mapping $\restr{\sigma}{i}\colon \hist{\Sigma}^{\le i-1}\times\Sigma\to\{\ensuremath{\mathit{Call}}\xspace,\ensuremath{\mathit{Read}}\xspace\}$ and $\restr{\sigma}{0}$ is the mapping with empty domain.

\begin{proofof}{Theorem~\ref{theo:right}~(a)}
    Let $G$ be a context-free game with the {bounded depth property} and let $(B_k)_{k\in\mathbb N_0}\subseteq \mathbb N$ be its sequence of depth bounds.

We first define a language $L$ which will serve as the winning set of
the weakly dominant strategy that will be constructed below.

The definition of $L$ is by induction. For each $k\ge 0$, we define a set $L_k\subseteq \Sigma^{\le k}$ such that $L_k\subseteq L_{k+1}$, and finally let $L\df \bigcup_k L_k$.

Let $L_0=\{\epsilon\}$ if $\epsilon$ is in the target language of $G$, and $L_0=\emptyset$ otherwise.

For $k\ge 0$, we define $L_{k+1}$ as the maximal set with respect to $\ensuremath{\le_{\textsf{sl}}}$ of the form $W(\sigma)\cap\Sigma^{\le k+1}$ for some strategy $\sigma$ with $L_k\subseteq W(\sigma)$.
It is easy to see that the following two properties hold by construction.
\begin{enumerate}[(1)
\item For each $k$, there is a strategy $\sigma$ such that $L_k\subseteq W(\sigma)$.
\item There is no strategy $\sigma$ with $L\ensuremath{<_{\textsf{sl}}} W(\sigma)$.
\end{enumerate}
Thanks to property (2), it suffices to construct a strategy $\ensuremath{\hat{\sigma}}$ with $L\subseteq W(\ensuremath{\hat{\sigma}})$

For each $k\ge 0$, let $S_k$ be the set of strategies $\sigma$ with $L_k\subseteq W(\sigma)$ for which each play on a word $w\in L_k$ has depth at most $B_{|w|}$.  Because of property (1) and since $G$ has the bounded depth property, we have $S_k\not=\emptyset$ for every $k\ge 0$.

    We will construct mappings $\rho_k\colon \hist{\Sigma}^{\le k-1}\times\Sigma\to\{\ensuremath{\mathit{Call}}\xspace,\ensuremath{\mathit{Read}}\xspace\}$ such that for every $k\ge 0$,
    \begin{itemize}
    	\item $\rho_{k+1}$ extends $\rho_k$; more
    	precisely: $\restr{\rho_{k+1}}{k}=\rho_k$, and
    	\item for each $\ell\ge k$ there exists $\sigma^k_\ell\in S_\ell$ with $\rho_k=\restr{\sigma^k_\ell}{k}$.
    \end{itemize}
	Let $\rho_0$ be the mapping with empty domain. Fix $k$ such that $\rho_0,\dots,\rho_k$ are defined and have the stated properties. Since there are only finitely many mappings $\hist{\Sigma}^{\le k}\times\Sigma\to\{\ensuremath{\mathit{Call}}\xspace,\ensuremath{\mathit{Read}}\xspace\}$, one of them has to occur infinitely often within $\big(\restr{\sigma^k_\ell}{k+1}\big)_{\ell\ge k}$. Let $\rho_{k+1}$ be such a mapping. For $\ell'\ge k+1$ we can choose $\sigma^{k+1}_{\ell'}=\sigma^{k}_{\ell}$ for some $\ell\ge\ell'$ with $\rho_{k+1}=\restr{\sigma^k_\ell}{k+1}$. This defines a sequence $\rho_0,\rho_1,\dots$ with the properties above. Let $\ensuremath{\hat{\sigma}}$ be the strategy that is uniquely determined by $\restr{\ensuremath{\hat{\sigma}}}{k}=\rho_k$, for every $k$. Clearly $(\rho_k)_{k\in\mathbb N}$ converges\footnote{Since the $\rho_k$ are only partially defined, one might consider the strategies $\sigma_k$ that result from the $\rho_k$ which take the value \ensuremath{\mathit{Call}}\xspace whenever $\rho_k$ is undefined.} to $\ensuremath{\hat{\sigma}}$.

Thanks to Lemma~\ref{lemma:conv} it suffices to show that $\ensuremath{\hat{\sigma}}$ terminates on $L$.
Let thus $w\in L$ and $\tau$ be a Romeo strategy. We show that the depth of  $\Pi\df\Pi(\ensuremath{\hat{\sigma}},\tau,w)$ is at most $B_{|w|}$. Otherwise let $k$ be such that in the $k$th round Juliet does a $\ensuremath{\mathit{Call}}\xspace$ move of nesting depth $B_{|w|}+1$. However, $\restr{\ensuremath{\hat{\sigma}}}{k}=\rho_k=\restr{\sigma_\ell^k}{k}$, where $\ell=\max\{k,|w|\}$, and $\sigma_\ell^k\in S_\ell$ has depth at most $B_{|w|}$ on $w\in L_\ell$, a contradiction. Therefore the depth of $\Pi$ is at most $B_{|w|}$ and by K\"{o}nig's Lemma $\Pi$ is thus finite, completing the proof.
\end{proofof}

\subsubsection{Prefix-free games}\label{sec:selfDelim}

Prefix-freeness appears as a realistic constraint for a practical
(Active XML) setting since it can be easily enforced by suffixing each
replacement string with a special end-of-file symbol. In this sense,
\emph{every} game $G=(\Sigma,R,T)$ can be transformed into a
prefix-free game $G'=(\Sigma',R',T')$ by letting
$\Sigma'=\Sigma\mathbin{\dot{\cup}}\{\$\}$ for some new symbol $\$\notin\Sigma$
that shall denote the end of replacement strings, and further letting
$R_a'=R^{\phantom\prime}_a\$$ for each $a\in\Sigma_f$ to enforce that
replacement words end with $\$$, and adding a loop transition for the
symbol $\$$ to each state of $T$ (accomplishing that the symbol~$\$$
is ``ignored'' by the target language). Another special case of
prefix-free games, which is similar to the \emph{one-pass with size}
setting discussed in \cite{AbiteboulMB05}, are games where the
alphabet $\Sigma$ contains (besides other symbols) numbers $1,\dots,N$
for some $N\in\mathbb N$ and all replacement strings are of the form
$nx$ where $x\in\Sigma^+$ and $n=\abso{x}$. Our result for prefix-free games also easily transfers to the setting where the input word is revealed to Juliet in a one-pass fashion, but Romeo's replacement words are revealed immediately.

We \short{sketch}\full{give} the proof of Theorem~\ref{theo:right}~(b) in the following.

A context-free game on a string $w=a_1\cdots a_n$ can be viewed as a
sequence of $n$ games on the single symbols $a_1,\ldots,a_n$.
Intuitively, in prefix-free games Juliet has the benefit to know when
a subgame on some symbol $a_i$ has ended and when the next subgame
starts.

This allows us to view strategies of Juliet in a hierarchical
way: they consist of a top-level strategy that chooses, whenever a
subgame on some $a_i$ starts, a strategy for this subgame. This
choice may take the current history string into account.
We will use this view to proceed in an inductive fashion: we
establish that there are automata for the subgame strategies and then combine these
automata with suitable automata for a ``top-level'' strategy.

It turns out that the choice of the top-level strategy boils down to
an ``online word problem'' for NFAs which we introduce and study first.

\paragraph*{The online word problem for NFAs}

In the online-version of the word problem for an NFA $\ensuremath{{\mathcal N}}\xspace$, denoted \online, the
single player gets to know the symbols of a word one by one, and always needs to decide which transition $\ensuremath{{\mathcal N}}\xspace$ should
take before the next symbol is revealed. We only consider the case that $\ensuremath{{\mathcal N}}\xspace=(Q,\Sigma,\delta,s,F)$ has at
least one transition for each symbol from each state. Formally, a strategy is a map $\rho\colon\Sigma^*\to Q$ such that $\rho(\epsilon)=s$ and $(\rho(w),a,\rho(wa))\in\delta$ for each $w\in\Sigma^*$ and $a\in\Sigma$.

Given a strategy $\rho$
for \online, we denote by $W_\ensuremath{{\mathcal N}}\xspace(\rho)$ the \emph{winning
  set} of words that are accepted by $\ensuremath{{\mathcal N}}\xspace$ if the player follows
$\rho$. A strategy $\rho$ is
\emph{weakly dominant}  if, for every
strategy $\rho'$, it holds $W_\ensuremath{{\mathcal N}}\xspace(\rho')\ensuremath{\le_{\textsf{sl}}} W_\ensuremath{{\mathcal N}}\xspace(\rho)$.

\full{
For an NFA $\ensuremath{{\mathcal N}}\xspace=(Q,\Sigma,\delta,s,F)$ and a state $q\in Q$, we
write $\ensuremath{{\mathcal N}}\xspace^q$ for the NFA $(Q,\Sigma,\delta,q,F)$ with starting
state $q$.
We say that a word $w$ is \emph{universally accepted} by an NFA
$\ensuremath{{\mathcal N}}\xspace$, if \emph{every} run of $\ensuremath{{\mathcal N}}\xspace$ on $w$ is accepting.

We are interested in strategies that can be computed by automata. A
particularly simple such strategy for \textsc{OnlineNFA}($\mathcal
N$) can be obtained by transforming $\mathcal N$ into a DFA $\mathcal
D$ by removing transitions. The associated strategy $\rho_{\mathcal
  D}$ is the one that only uses the transitions of $\ensuremath{{\mathcal D}}\xspace$. We prove that $\ensuremath{{\mathcal D}}\xspace$ can be chosen such that $\rho_{\mathcal
  D}$ is weakly dominant.

\begin{lemma}\label{lem:OnlineNFA}
	For each NFA $\mathcal N$, there exists a DFA $\mathcal D$
        obtained by removing transitions from $\mathcal N$ such that
        $\rho_{\mathcal D}$ is a weakly dominant strategy for \online.
\end{lemma}
\full{
\begin{proof}
	We define a sequence $\mathcal N_0,\mathcal N_1,\dots$
        of NFAs, starting from $\mathcal N_0=\mathcal N$. Each
        $\ensuremath{{\mathcal N}}\xspace_{n+1}$ results from $\ensuremath{{\mathcal N}}\xspace_n$ by removing
        transitions in the following way. For a state $q$, let
        $L^q_n$ be the set of words of length at most $n$ that are
        non-deterministically accepted by $\mathcal N^q_n$. For each state $q$ and symbol $a$, we only keep
        the transitions to those successor states $p$ that maximise
        $L^{p}_n$ with respect to $\ensuremath{\le_{\textsf{sl}}}$.

	Since there are only finitely many transitions in $\ensuremath{{\mathcal N}}\xspace$, the
        sequence $\mathcal N_0,\mathcal N_1,\dots$ becomes stationary
        after finitely many steps. By $\widetilde{\ensuremath{{\mathcal N}}\xspace}$ we denote the last NFA
        of the sequence.

	\begin{myclaim}\label{cl:LSnAlsoUniv}
	For each $q$ and $n$, all words in $L^q_n$ are
        non-deterministically and universally accepted by $\widetilde{\ensuremath{{\mathcal N}}\xspace}^q$.
	\end{myclaim}
	\begin{proof}
		We show a slightly stronger claim by induction on $n$:
                for each $q$, $n$ and $m\ge n$, all words in $L^q_n$ are
        non-deterministically and universally accepted by $\ensuremath{{\mathcal N}}\xspace^q_m$.
                 For $n=0$ the statement is trivial.

		Let $aw\in L^q_{n+1}$ with $a\in\Sigma$ and
                $w\in\Sigma^{\le n}$. Let $p$ be a state reached
                after reading the initial $a$ in some accepting run of
                $\ensuremath{{\mathcal N}}\xspace^q_{n+1}$ on
                $aw$. Then
                $w\in L^p_n$. By definition of $\mathcal N_{n+1}$,
                $L^r_n=L^p_n$ for every state $r$ reachable
                from $q$ by reading $a$ in $\mathcal
                N_{n+1}$. Therefore, by the induction
                hypothesis, $w$
                is universally accepted by $\ensuremath{{\mathcal N}}\xspace^r_n$, for any such $r$. Thus,
                $aw$ is universally accepted by $\ensuremath{{\mathcal N}}\xspace^q_{n+1}$.

	Since each $\ensuremath{{\mathcal N}}\xspace_{i+1}$ results from $\ensuremath{{\mathcal N}}\xspace_{i}$ by removing
        transitions, every word that is universally accepted by
        $\ensuremath{{\mathcal N}}\xspace_{i}$ is also universally accepted by
        $\ensuremath{{\mathcal N}}\xspace_{i+1}$. On the other hand, since each state has a
        transition for each symbol, every universally accepted word is
        also nondeterministically accepted.
Therefore, for each $q$, $n$, all words in $L^q_n$ are
non-deterministically and universally accepted by
$\widetilde{\ensuremath{{\mathcal N}}\xspace}^q_m$, for every $m\ge n$, and therefore also by $\ensuremath{{\mathcal N}}\xspace^q$.
	\end{proof}

	\begin{myclaim}\label{cl:LSnMax}
For each strategy $\rho$ for \online, $W_\ensuremath{{\mathcal N}}\xspace(\rho)\ensuremath{\le_{\textsf{sl}}}  L(\widetilde{\ensuremath{{\mathcal N}}\xspace})$.
	\end{myclaim}
	\begin{proof}
We show a more precise statement: for each $q$,
each $n\ge 0$,  and
each strategy $\rho$ for \online[\ensuremath{{\mathcal N}}\xspace^q],
$W_{\ensuremath{{\mathcal N}}\xspace^q}(\rho)\cap\Sigma^{\le n}\ensuremath{\le_{\textsf{sl}}}  L^q_n$.
Claim~\ref{cl:LSnMax} easily follows from this statement and Claim~\ref{cl:LSnAlsoUniv}.

Towards a contradiction, assume that there are $n,q,\rho$
with $W_{\ensuremath{{\mathcal N}}\xspace^q}(\rho)\cap\Sigma^{\le n}\ensuremath{>_{\textsf{sl}}} L^q_n$. Let $n$ be minimal
with this property and let $w\in (W_{\ensuremath{{\mathcal N}}\xspace^q}(\rho)\cap\Sigma^{\le
  n})\setminus L^q_n$ be chosen minimal with respect to
$\ensuremath{\le_{\textsf{sl}}}$. Clearly, for all $w'\ensuremath{<_{\textsf{sl}}} w$ it holds $w'\in (W_{\ensuremath{{\mathcal N}}\xspace^q}(\rho)\cap\Sigma^{\le
  n}) \Leftrightarrow w'\in L^q_n$

Clearly $n>0$, so we
can write $w=au$ for $a\in\Sigma$ and $u\in\Sigma^{n-1}$. Let $p=\rho(a)$. Since $n$ is minimal, for the
strategy $\rho'$ induced by $\rho$ for $\ensuremath{{\mathcal N}}\xspace^p$, defined by $\rho'(v)=\rho(av)$, it holds
\begin{align}\label{eq:prefixfreeTyp2UndomExists1}
W_{\ensuremath{{\mathcal N}}\xspace^p}(\rho')\cap\Sigma^{\le n-1}\ensuremath{\le_{\textsf{sl}}}  L^p_{n-1}.
\end{align}

Let $r$ be some state for which $(q,a,r)$ is a transition in
$\ensuremath{{\mathcal N}}\xspace_n$. We claim
\begin{align}\label{eq:prefixfreeTyp2UndomExists2}
W_{\ensuremath{{\mathcal N}}\xspace^p}(\rho')\cap\Sigma^{\le n-1}\ensuremath{>_{\textsf{sl}}}  L^r_{n-1}.
\end{align}
Towards a contradiction assume otherwise. Since $u\in W_{\ensuremath{{\mathcal N}}\xspace^p}(\rho')\cap\Sigma^{\le n-1}$ and $u\not\in
L^r_{n-1}$, there must be some  $u'\ensuremath{<_{\textsf{sl}}} u$ with $u'\not\in W_{\ensuremath{{\mathcal N}}\xspace^p}(\rho')\cap\Sigma^{\le n-1}$ and $u'\in
L^r_{n-1}$. However, then $au'\not\in W_{\ensuremath{{\mathcal N}}\xspace^q}(\rho)\cap\Sigma^{\le
  n}$ and $au'\in L^q_n$, a contradiction, since $au'\ensuremath{<_{\textsf{sl}}} au=w$.

(\ref{eq:prefixfreeTyp2UndomExists1}) and
(\ref{eq:prefixfreeTyp2UndomExists2}) imply that $(q,a,p)$ is not a transition in
$\ensuremath{{\mathcal N}}\xspace_n$.
	Let $m\le n-1$ be maximal such that $(q,a,p)$ is a transition in
        $\mathcal N_m$. Then $L^p_m\ensuremath{<_{\textsf{sl}}} L^r_m$ and hence
        $L^p_{n-1}\ensuremath{<_{\textsf{sl}}} L^r_{n-1}$, contradicting (\ref{eq:prefixfreeTyp2UndomExists1}) and
(\ref{eq:prefixfreeTyp2UndomExists2}).
	\end{proof}

	 Let
        $\ensuremath{{\mathcal D}}\xspace$ be any DFA resulting from $\widetilde{\ensuremath{{\mathcal N}}\xspace}$ by removing some
        further transitions. By Claim~\ref{cl:LSnAlsoUniv},
        $L(\ensuremath{{\mathcal D}}\xspace)=L(\widetilde{\ensuremath{{\mathcal N}}\xspace})$. Therefore, by Claim~\ref{cl:LSnMax},
        $\rho_\ensuremath{{\mathcal D}}\xspace$ is weakly dominant, concluding the proof of Lemma~\ref{lem:OnlineNFA}.
\end{proof}
}

\paragraph*{Game composition and game effects.}

Let in the following, $G=(\Sigma,R,T)$ be a prefix-free game with
        $T=(Q,\Sigma,\delta,s,F)$. Let furthermore, for every
        $a\in\Sigma$,
        $\ensuremath{{\mathcal A}}\xspace_a=(Q_a,\Sigma,\delta_a,s_a,\{f_a\})$ be a minimal DFA for the replacement language $L_a$ of $a$. Since $L_a$ is
        prefix-free, $\ensuremath{{\mathcal A}}\xspace_a$ has a unique accepting state $f_a$.

For a strategy $\sigma$ (for Juliet or Romeo) and a string $\alpha\in\hist{\Sigma}^*$, we define the \emph{substrategy} $\sigma^\alpha$ of $\sigma$ by $\sigma^\alpha(\beta,a)=\sigma(\alpha\beta, a)$.

In the following,
        $\states{q}{w,\sigma}$ denotes the set of $T$-states that can be
        reached at the end of a play of $\sigma$ on $w$ if the initial
        state of $T$ were $q$. More precisely, it is the
set of states of the form
        $\delta^*(q,\natural \alpha)$ where $\alpha$ is a final history string of a play of $\sigma$ on $w$.

An \emph{effect triple} $(p,a,S)$ consists of a state $p\in Q$, a
symbol $a\in \Sigma$ and a set $S\subseteq Q$. We say that $(p,a,S)$
is an effect triple of $\sigma$ if $\states{p}{a,\sigma}\subseteq S$. We call $(p,a,S)$ \emph{trivial} if $\delta(p,a)\in S$, i.\nolinebreak[4]\hspace{0.125em}e.\nolinebreak[4]\@\xspace if it is an effect triple of a strategy that plays Read on $a$.
The \emph{single-symbol effect} $\ensuremath{\textsf{sse}}(\sigma)$ of a strategy $\sigma$
is the set of all its effect triples. Finally, we define the
\emph{effect set} $E(\sigma)$ of a
strategy $\sigma$ as $\displaystyle E(\sigma)\df \bigcup_{\alpha\in\hist{\Sigma}^*} \ensuremath{\textsf{sse}}(\sigma^\alpha)$. That is, $E(\sigma)$
contains all effect triples that are induced by
substrategies of $\sigma$.

With a set $E$ of effect triples we associate an NFA
$\ensuremath{{\mathcal N}}\xspace_E=(\ensuremath{{\mathcal P}}\xspace(Q),\Sigma,\delta_E,\{s\},\ensuremath{{\mathcal P}}\xspace(F))$, where
$\delta_E$ is defined as follows. For sets $S,S'\subseteq Q$ and
$a\in\Sigma$, $(S,a,S')\in\delta_E$ if, for each $p\in S$, there is
some $S''\subseteq S'$ such that $(p,a,S'')\in E$.

\begin{proposition}\label{prop:GameToOnline}
Let $G=(\Sigma,R,T)$ be a prefix-free game, $E$ a set of effect triples, and $\sigma$ a
terminating strategy such that $E(\sigma)\subseteq E$. Then there is a strategy
$\rho$ for $\online[\ensuremath{{\mathcal N}}\xspace_E]$ such that $W_G(\sigma)=W_{\ensuremath{{\mathcal N}}\xspace_E}(\rho)$.
\end{proposition}
\begin{proof}
  It is straightforward to verify that $\rho(w)\df \states{s}{w,\sigma}$ yields a well-defined strategy $\rho$ for $\online[\ensuremath{{\mathcal N}}\xspace_E]$. The proposition follows, since $w\in W_{\ensuremath{{\mathcal N}}\xspace_E}(\rho)$ if and only if $\rho(w)\subseteq F$, and $w\in W_G(\sigma)$ if and only if $\states{s}{w,\sigma}\subseteq F$.
\end{proof}

We say that a strategy automaton $\ensuremath{{\mathcal A}}\xspace=(Q_\ensuremath{{\mathcal A}}\xspace,\hist{\Sigma},\delta_\ensuremath{{\mathcal A}}\xspace,s_\ensuremath{{\mathcal A}}\xspace,F_\ensuremath{{\mathcal A}}\xspace)$ is
\emph{$(p,a,S)$-inducing} if $\sigma_\ensuremath{{\mathcal A}}\xspace$ is terminating, $a\in \Sigma_f$, and the following conditions hold.
\begin{itemize}
\item For each $u\in L_a$, $\states{p}{u,\sigma_\ensuremath{{\mathcal A}}\xspace}\subseteq S$.
\item There are disjoint subsets $Q_{\ensuremath{{\mathcal A}}\xspace,q}\subseteq Q_\ensuremath{{\mathcal A}}\xspace$, for $q\in S$,
  such that for every play of $\sigma$ on some $u\in L_a$ with final history string $\alpha$,
  it holds $\delta_\ensuremath{{\mathcal A}}\xspace^*(s_\ensuremath{{\mathcal A}}\xspace,\alpha)\in Q_{\ensuremath{{\mathcal A}}\xspace,q} \Leftrightarrow \delta^*(p,\natural\alpha)=q$.\\
Furthermore, there is no proper
  prefix $\beta$ of $\alpha$ for which $\delta_\ensuremath{{\mathcal A}}\xspace^*(s_\ensuremath{{\mathcal A}}\xspace,\beta)\in
  Q_{\ensuremath{{\mathcal A}}\xspace,r}$, for any $r$.
\end{itemize}

\begin{proposition}\label{prop:OnlineToGame}
Let $G=(\Sigma,R,T)$ be a prefix-free game and $E$ a set of effect
triples such that for each non-trivial $t\in E$, there exists a $t$-inducing
strategy automaton $\ensuremath{{\mathcal A}}\xspace_t$. Then there is a strategy automaton $\ensuremath{{\mathcal A}}\xspace$ for
$G$ such that, for each strategy
$\rho$ for $\online[\ensuremath{{\mathcal N}}\xspace_E]$, $ W_{\ensuremath{{\mathcal N}}\xspace_E}(\rho) \ensuremath{\le_{\textsf{sl}}} W_G(\sigma_\ensuremath{{\mathcal A}}\xspace)$.
\end{proposition}
\full{
\begin{proof}
Let $\ensuremath{{\mathcal D}}\xspace$ be the DFA guaranteed by Lemma~\ref{lem:OnlineNFA}, giving the weakly dominant strategy $\rho_\ensuremath{{\mathcal D}}\xspace$ for
\online[\ensuremath{{\mathcal N}}\xspace_E].
	It suffices to construct $\ensuremath{{\mathcal A}}\xspace$ such that $ W_{\ensuremath{{\mathcal N}}\xspace_E}(\rho_\ensuremath{{\mathcal D}}\xspace) \subseteq W_G(\sigma_\ensuremath{{\mathcal A}}\xspace)$.

	The strategy automaton $\mathcal A$ has a non-accepting state $(p,S)$ for
        each $ S\subseteq Q$ and $p\in S$, further states of the form
        $(S,r)$, where $r$ is a state of some
        $\ensuremath{{\mathcal A}}\xspace_t$, and $(S,r)$ is accepting if and only if $r$ is
        accepting in $\ensuremath{{\mathcal A}}\xspace_t$, and an accepting state \ensuremath{\mathit{Call}}\xspace. The
        initial state is $(s,\{s\})$. We construct $\ensuremath{{\mathcal A}}\xspace$ such that,
        if $\alpha$ is the final history string of a play of
        $\sigma_\ensuremath{{\mathcal A}}\xspace$ on $w$, then
        $\delta_\ensuremath{{\mathcal A}}\xspace^*(s_\ensuremath{{\mathcal A}}\xspace,\alpha)=(p,S)$, where
        $S=\rho_\ensuremath{{\mathcal D}}\xspace(w)$, $p=\delta^*(s,\natural\alpha)$, and $p\in
        S$.
Thus, whenever a subplay on a prefix of the input word is completed, $\ensuremath{{\mathcal A}}\xspace$
knows the state $p$ that has been reached, and the state $S$ that $\rho$
has reached in $\ensuremath{{\mathcal N}}\xspace$.

To this end, $\delta_\ensuremath{{\mathcal A}}\xspace$ is defined as follows. Let
$(p,S)$ be the current state and $a$ the next symbol and let
$S'=\delta_\ensuremath{{\mathcal D}}\xspace(S,a)$.
If  $\delta(p,a)\in S'$ then from $p$ a state in $S'$ can be
reached by playing \ensuremath{\mathit{Read}}\xspace on $a$ and thus
$\delta_\ensuremath{{\mathcal A}}\xspace((p,S),a)=(\delta(p,a),S')$. Otherwise,
$\delta_\ensuremath{{\mathcal A}}\xspace((p,S),a)=\ensuremath{\mathit{Call}}\xspace$. In the latter case, we can choose some $t=(p,a,S'')\in E$ with $S''\subseteq S'$, corresponding to a $t$-inducing automaton $\ensuremath{{\mathcal A}}\xspace_t$.
To continue the play after playing \ensuremath{\mathit{Call}}\xspace on $a$, let $\delta_\ensuremath{{\mathcal A}}\xspace((p,S),\call{a})=(S',s_t)$, where $s_t$ is the initial state of $\ensuremath{{\mathcal A}}\xspace_t$. That is,
a subrun is started in which $\ensuremath{{\mathcal A}}\xspace_t$ is simulated on the replacement word of $a$, and $S'$
is laid aside.

To carry out the simulation of $\ensuremath{{\mathcal A}}\xspace_t$, we simply define
$\delta_\ensuremath{{\mathcal A}}\xspace((S',x),b)=(S',\delta_t(x,b))$ for every state $x$ of $\ensuremath{{\mathcal A}}\xspace_t$ and every $b\in\hist{\Sigma}$, unless $\delta_t(x,b)\in Q_{\ensuremath{{\mathcal A}}\xspace_t,q}$ for some $q$. If $\delta_t(x,b)\in Q_{\ensuremath{{\mathcal A}}\xspace_t,q}$, then
$\delta_\ensuremath{{\mathcal A}}\xspace((S',x),b)=(q,S')$, ending the
subgame.

By induction on the length of $w$, it is straightforward to show that $\ensuremath{{\mathcal A}}\xspace$ meets
the above specification. In particular, whenever $\rho_\ensuremath{{\mathcal D}}\xspace$ wins for
a word $w$ in $\online[\ensuremath{{\mathcal N}}\xspace_E]$, $\ensuremath{{\mathcal A}}\xspace$ yields a strategy that ends
in a state of the form $(p,S)$ with $S\subseteq F$ and $p\in S$ and it
holds $\delta^*(s,\natural\alpha)=p\in F$, for the final history
string $\alpha$. Therefore, $W_{\ensuremath{{\mathcal N}}\xspace_E}(\rho_\ensuremath{{\mathcal D}}\xspace) \subseteq W_G(\sigma)$ indeed
holds.
\end{proof}
}

\full{
	The next lemma gives a crucial property of prefix-free games. Intuitively, it says that Juliet always knows the maximal prefix $u$ of the input word that is completely processed, the history string $\alpha$ corresponding to the subgame on $u$, and the next symbol $b$ of the input word that is currently processing.
\begin{lemma}\label{lem:pfree}
	Let $(\gamma,c,v)$ be a configuration in a play $\Pi(\sigma,\tau,w)$ of a prefix-free game $G=(\Sigma,R,T)$. Then $\gamma$ and $c$ uniquely determine $u\in\Sigma^*$, $b\in\Sigma$, and a prefix $\alpha$ of $\gamma$ such that $ub$ is a prefix of $w$, $\alpha$ is the final history string of $\Pi(\sigma,\tau,u)$, and $u$ has maximal length.
\end{lemma}
\begin{proof}
	Let $(K_0,K_1,\dots,K_n)$ be the prefix of $\Pi(\sigma,\tau,w)$ with
	$K_i=(\gamma_i,c_i,v_i)$, for each $i$, and
	$(\gamma_n,c_n)=(\gamma,c)$. We show by backwards induction that for
	$i=n,n-1,\dots,0$, there are unique $u_i,b_i,\alpha_i$ such that
	$\gamma_i\alpha_i$ is a prefix of $\gamma$, $u_ib_i$ is a prefix of
	$c_iv_i$, $\alpha_i$ is the final history string of
	$\Pi(\sigma^{\gamma_i},\tau^{\gamma_i},u_i)$, and $u_i$ has maximal
	length. In a nutshell, from $K_i$ onwards, the string to be
	played on is $c_iv_i$. The string $u_ib_i$ is the prefix of  $c_iv_i$
	that has been ``touched''  by the play from $K_i$ to
	$K_n$. The subplay on $u_i$ yielded the additional history string
	$\alpha_i$. The subplay on $b_i$ is ongoing at $K_n$.
	The lemma then follows by choosing
	$(u,b,\alpha)=(u_0,b_0,\alpha_0)$.

	The base case is $u_n=\alpha_n=\epsilon$ and $b_n=c_n$. For the
	induction step, either $\gamma_i=\gamma_{i-1}c_{i-1}$ or
	$\gamma_i=\gamma_{i-1}\call{c_{i-1}}$. In the former case,
	$u_{i-1}=c_{i-1}u_i$, $b_{i-1}=b_i$,
	$\alpha_{i-1}=c_{i-1}\alpha_i$. Otherwise, we consider two
	sub-cases. If $u_i=xx'$ for some $x\in L_{c_{i-1}}$ and $x'\in\Sigma^*$
	(here, $x$ is uniquely determined thanks to prefix-freeness of $ L_{c_{i-1}}$), then
	$\tau(\gamma_{i-1},c_{i-1})=x$. Thus, we have
	$K_i=(\gamma_{i-1}\call{c_{i-1}},\tau(\gamma_{i-1},c_{i-1})x'b_iz)$ for
	some $z$ and hence $K_{i-1}=(\gamma_{i-1},c_{i-1}x'b_iz)$. Then
	$u_{i-1}=c_{i-1}x'$, $b_{i-1}=b_i$,
	$\alpha_{i-1}=\call{c_{i-1}}\alpha_i$. Otherwise, the subgame for
	$c_{i-1}$ has not ended in $K_n$, and thus $u_{i-1}=\alpha_{i-1}=\epsilon$, $b_{i-1}=c_{i-1}$. It
	is easy to verify in all cases that $(u_{i-1},b_{i-1},\alpha_{i-1})$
	is the unique  solution for the required properties.
\end{proof}
}

A crucial ingredient is the following proposition, which will allow us to restrict our attention to strategies of finite depth. An almost identical proof can also be used to show that prefix-free games have the bounded depth property, and we could use this and Theorem~\ref{theo:right}~(a) to deduce immediately that they have weakly dominant strategies. However, we are aiming for the stronger result that they have \emph{regular} weakly dominant strategies.

\begin{proposition}\label{prop:prefixfreeBDP}
	In prefix-free games, each effect triple of a terminating strategy is also an effect triple of a strategy of bounded depth.
\end{proposition}
\short{
\begin{proof}[Proof idea]
	Let $E$ denote the set effect triples of bounded depth strategies. Consider an effect triple $(p,a,S)\notin E$ of a strategy $\hat\sigma$. If the effect triples of $\hat\sigma$'s substrategies on the symbols of $a$'s replacement word were all in $E$, then these substrategies could be replaced so as to obtain a bounded depth strategy $\sigma$ for $(p,a,S)$, contradicting $(p,a,S)\notin E$. Thus, for each $(p,a,S)\notin E$, Romeo can force a configuration in the play against $\hat\sigma$ on $a$ where the effect triple of the substrategy is again not in $E$. But Romeo can do this repeatedly, so $\hat\sigma$ is not terminating.
\end{proof}
}
\full{
	\begin{proof}
		Let $E$ denote the set effect triples of all strategies of bounded depth. For $t\in E$ fix such a bounded depth strategy $\sigma_t$ with effect triple $t$. Since $E\subseteq Q\times\Sigma\times \mathcal P(Q)$ is finite, there exists $B$ such that for each $t\in E$, the depth of plays of $\sigma_t$ is at most $B$.

We claim that if $(p,a,S)\notin E$ is an effect triple of strategy $\hat\sigma$, then there is a Romeo strategy $\tau$ such that $\Pi(\hat\sigma,\tau,a)$ contains a configuration $(\call a\alpha,b,w)$ with $(q,b,S')\notin E$ for $q=\delta^*(p,\natural\alpha)$ and $S'=\states{q,b}{\hat\sigma^{\call a\alpha}}$. But this means that Romeo can repeatedly force a configuration where $\hat\sigma$'s substrategy on the current symbol has an effect triple outside of $E$, and hence $\hat\sigma$ would not be terminating. Thus, each effect triple of a terminating strategy is in $E$.

It remains to show the claim. Let $(p,a,S)\notin E$ be an effect triple of a strategy $\hat\sigma$. Suppose for the sake of contradiction that for each configuration of the form $(\call a\alpha,b,w)$ occurring in some play of $\hat\sigma$ on $a$ it holds that $(q,b,S')\in E$, where $q=\delta^*(p,\natural\alpha)$ and $S'=\states{q,b}{\hat\sigma^{\call a\alpha}}$. We claim that in this case, $(p,a,S)$ is an effect triple of a strategy of depth at most $B+1$, in contradiction to $(p,a,S)\notin E$.

We first define a strategy $\sigma$ that plays on input words from $L_a$. We define $\sigma(\gamma,c)$ for $(\gamma,c)\in\hist\Sigma^*\times\Sigma_f$ such that a configuration of the form $(\gamma,c,v)$ occurs in some play of $\sigma$ on an input word from $L_a$ (given the definition of $\sigma$ for previous configurations). Consider $u,b,\alpha$ determined by $(\gamma,c)$ as per Lemma~\ref{lem:pfree}. The definition of $\sigma$ will ensure by induction on the length of $u$ that $\states{p,u}{\sigma}\subseteq\states{p,u}{\hat\sigma^{\call a}}$. Clearly this holds for $u=\epsilon$.

Let $q=\delta^*(p,\natural\alpha)$. Since $q\in\states{p,u}{\sigma}\subseteq\states{p,u}{\hat\sigma^{\call a}}$, there is a history string $\alpha'$ that is the final history string of a play of $\hat\sigma^{\call a}$ on $u$ such that $q=\delta^*(p,\natural\alpha')$. Choose such $\alpha'$ lexicographically minimal. Since $\hat\sigma(\epsilon,a)=\ensuremath{\mathit{Call}}\xspace$ (because $(p,a,S)\notin E$) and $ubw\in L_a$ for some $w$, the configuration $(\call a\alpha',b,w)$ occurs in some play of $\hat\sigma$ on $a$. Let $S'=\states{q,b}{\sigma^{\call a\alpha'}}$. By assumption, $(q,b,S')\in E$. For each non-final configuration $(\beta,c,z)$ occurring in some play of $\sigma_{q,b,S'}$, let $\sigma(\alpha\beta,c)=\sigma_{q,b,S'}(\beta,c)$. Note that $\gamma=\alpha\beta$ for some such $\beta$. This defines $\sigma$ until $ub$ is completely processed. Since $S'\subseteq \states{p,ub}{\sigma^{\call a}}$, we have $\states{p,ub}{\sigma}\subseteq\states{p,ub}{\hat\sigma^{\call a}}$, which completes the induction step.

Consider now the strategy $\sigma'$ given by $\sigma'(\epsilon,a)=\ensuremath{\mathit{Call}}\xspace$, $\sigma'(\call a\gamma,c)=\sigma(\gamma,c)$ if the latter is defined, and defined as $\ensuremath{\mathit{Read}}\xspace$ everywhere else. Since $$\states{p,u}{\sigma}\subseteq\states{p,u}{\hat\sigma^{\call a}}\subseteq\states{p,a}{\hat\sigma}=S$$ for all $u\in L_a$, it follows $\states{p,a}{\sigma'}\subseteq S$ and hence $(p,a,S)$ is an effect triple of $\sigma'$. But the depth of $\sigma'$ is at most $B+1$, contradicting $(p,a,S)\notin E$.
\end{proof}
}

The finite depth allows us to construct $t$-inducing strategy automata by induction on the depth of a strategy with effect triple $t$.

\begin{proposition}\label{prop:sse}
 Let $G=(\Sigma,R,T)$ be a prefix-free game and $(p,a,S)$ a non-trivial effect triple of some terminating strategy $\sigma$. Then there exists a $(p,a,S)$-inducing strategy
 automaton.
\end{proposition}
\full{
\begin{proof}
Due to Proposition~\ref{prop:prefixfreeBDP}, we can assume that the depth of $\sigma$ is bounded by some finite $k$. We proceed by induction on $k$.

Since $(p,a,S)$ is non-trivial, $\sigma(\epsilon,a)=\ensuremath{\mathit{Call}}\xspace$.  Let
$\sigma'$ be the strategy defined by $\sigma'(\alpha,b)=\sigma(\call{a}\alpha,b)$ if a configuration $(\call a\alpha,b,u)$ can occur in a play of $\sigma$ on $a$, for some $u$,
and $\sigma'(\alpha,b)=\ensuremath{\mathit{Read}}\xspace$ otherwise. Note that the depth of $\sigma'$ is
at most $k-1$. Moreover, for every $u\in L_a$, it holds
$\states{p}{u,\sigma'}\subseteq S$, since $\states{p}{a,\sigma}\subseteq S$.

Let $T'$ be the target automaton $(Q\times
Q_a,\Sigma,\delta\times\delta_a,(p,s_a),S\times \{f_a\})$, that is, the
product automaton of $T^p$ and $\ensuremath{{\mathcal A}}\xspace_a$ whose accepting states are
chosen to require $T^p$ to end in
$S$ and $\ensuremath{{\mathcal A}}\xspace_a$ to end in $f_a$. Let $G'$ be the game
$(\Sigma,R,T')$. We consider $\sigma'$ as a strategy for
$G'$. Since $\states{p}{u,\sigma'}\subseteq S$ for each $u\in L_a$, we have $L_a\subseteq W_{G'}(\sigma')$.

Let $E$ be the set of effect triples $(q,b,S')$ of strategies for $G'$ with
depth at most $k-1$. For each non-trivial $t\in E$, a
$t$-inducing strategy automaton exists by induction.
Let
$\ensuremath{{\mathcal A}}\xspace$ be the strategy automaton for the set $E$, defined in the proof of Proposition~\ref{prop:OnlineToGame}.

By Proposition~\ref{prop:GameToOnline},  there is a strategy
$\rho$ for $\online[\ensuremath{{\mathcal N}}\xspace_E]$ such that $W_{G'}(\sigma')=
W_{\ensuremath{{\mathcal N}}\xspace_E}(\rho)$. By Proposition~\ref{prop:OnlineToGame},
$W_{\ensuremath{{\mathcal N}}\xspace_E}(\rho)\ensuremath{\le_{\textsf{sl}}} W_{G'}(\sigma_\ensuremath{{\mathcal A}}\xspace)$. Altogether, we have
$L_a\ensuremath{\le_{\textsf{sl}}} W_{G'}(\sigma_\ensuremath{{\mathcal A}}\xspace)$ and, by definition of $G'$,
$W_{G'}(\sigma_\ensuremath{{\mathcal A}}\xspace)\subseteq L_a$,  hence $W_{G'}(\sigma_\ensuremath{{\mathcal A}}\xspace)= L_a$. Therefore, $\ensuremath{{\mathcal A}}\xspace$ is $(p,a,S)$-inducing if we choose $Q_q=\{((q,f_a),S')\mid S'\ni(q,f_a)\}$ for every $q\in S$.
  \end{proof}
}
Now we are ready to prove Theorem~\ref{theo:right}~(b).

\begin{proofof}{Theorem~\ref{theo:right}~(b)}
   Let $G=(\Sigma,R,T)$ be prefix-free. Let $E$ be the set of effect triples of terminating strategies. By
   Proposition~\ref{prop:sse} there is a $t$-inducing automaton for
   each non-trivial $t\in E$. Let $\sigma_\ensuremath{{\mathcal A}}\xspace$ be
the regular strategy as guaranteed by Proposition~\ref{prop:OnlineToGame}. We
show that $\sigma_\ensuremath{{\mathcal A}}\xspace$ is weakly dominant.

To this end, let $\sigma$ be any terminating strategy for $G$. Since $E(\sigma)\subseteq
E$, Proposition~\ref{prop:GameToOnline} guarantees a strategy $\rho$
for $\online[\ensuremath{{\mathcal N}}\xspace_E]$ such that $W_G(\sigma)=
W_{\ensuremath{{\mathcal N}}\xspace_E}(\rho)$. By Proposition~\ref{prop:OnlineToGame}, $
W_{\ensuremath{{\mathcal N}}\xspace_E}(\rho) \ensuremath{\le_{\textsf{sl}}} W_G(\sigma_\ensuremath{{\mathcal A}}\xspace)$, and therefore, altogether
$W_G(\sigma)  \ensuremath{\le_{\textsf{sl}}} W_G(\sigma_\ensuremath{{\mathcal A}}\xspace)$ as required.
\end{proofof}

\subsubsection{Games with finite target language}\label{sec:ex-nr-finite}
\short{
	\begin{proof}[Proof idea of Theorem~\ref{theo:right}~(c)]
		Let $\sigma$ be a dominant strategy. We say that $\sigma$ has a \emph{$(q,a)$-conflict}, for $q\in Q$ and $a\in\Sigma_f$, if there are configurations $(\alpha_1,a,u_1)$ and $(\alpha_2,a,u_2)$ in plays on words from $W(\sigma)$ such that $\delta^*(s,\natural\alpha_1)=\delta^*(s,\natural\alpha_2)=q$ and
		$\sigma(\alpha_1,a)\ne \sigma(\alpha_2,a)$.

		If $\sigma$ has no conflicts, then changing it to a strongly regular strategy requires modification only on configurations that do not occur in plays on words from $W(\sigma)$.

		Thus we only need to show that a dominant strategy $\sigma$ with some
		conflicts can be transformed into a dominant strategy $\sigma'$ with less conflicts. By repeating this process at most $|Q||\Sigma_f|$ times, we reach a strategy without conflicts.

		If $\sigma$ only plays $\ensuremath{\mathit{Read}}\xspace$ on some $v_1\in\Sigma^*$ with $\delta^*(s,v_1)=q$, we say that $\sigma$ is \emph{$(q,a)$-conflict-free after $v_1$} if either $\sigma(v_1,a)=\ensuremath{\mathit{Read}}\xspace$ and there is no $(q,a)$-conflicting
		\ensuremath{\mathit{Call}}\xspace-move in plays of $\sigma$ on any word $v_1au\in W(\sigma)$, for some $u$, or vice versa with \ensuremath{\mathit{Read}}\xspace and \ensuremath{\mathit{Call}}\xspace reversed. In both cases, a strategy without any $(q,a)$-conflicts can be obtained by ``copying'' the substrategy of the subgame starting from $(v_1,a,u)$ to any conflicting configuration.

		However, we need to show how to guarantee $(q,a)$-conflict-freeness after $v_1$.
		Actually, thanks to the finiteness of $L(T)$
		there can be no such conflict if $\sigma(v_1,a)=\ensuremath{\mathit{Read}}\xspace$, since $T$ can not return to state $q$ after taking a
		transition from $q$. But  in the case where
		$\sigma(v_1,a)=\ensuremath{\mathit{Call}}\xspace$, there could be a conflicting $\ensuremath{\mathit{Read}}\xspace$-move at
		some configuration $(\alpha,a,u')$ after $(v_1,a,u)$. However, again thanks to the finiteness of
		$L(T)$, there can not be any \ensuremath{\mathit{Read}}\xspace moves between $(v_1,a,u)$ and
		$(\alpha,a,u')$ and therefore, in particular, $u$ must be a suffix of $u'$.
		In this case we show that actually $u'=u$ must hold. By copying the strategy of $\sigma$ of the
		subgame on  $(\alpha,a,u)$ to the subgame on $(v_1,a,u)$, a strategy that matches the first
		case above can be obtained.
	\end{proof}
}
\full{
\begin{proofof}{Theorem~\ref{theo:right}~(c)}
Let $G = (\Sigma,R,T)$ with $T=(Q,\Sigma,\delta,s,F)$ such that $L(T)$ is finite, and let $\sigma$ be a dominant strategy for $G$. Thanks to Lemma~\ref{lem:alwaysTerm} we can assume that all plays of $\sigma$ are finite.

We say that $\sigma$ has a \emph{$(q,a)$-conflict}, for $q\in Q$ and $a\in\Sigma_f$, if there are words $w_1,w_2\in W(\sigma)$ and strategies $\tau_1,\tau_2$ of Romeo such that $\Pi(\sigma,\tau_1,w_1)$ reaches some configuration $(\alpha_1,a,u_1)$ with $\delta^*(s,\natural\alpha_1)=q$ and $\sigma(\alpha_1,a)=\ensuremath{\mathit{Read}}\xspace$,  and
$\Pi(\sigma,\tau_2,w_2)$ reaches some configuration $(\alpha_2,a,u_2)$
with $\delta^*(s,\natural\alpha_2)=q$ and
$\sigma(\alpha_2,a)=\ensuremath{\mathit{Call}}\xspace$. By $C(\sigma)$ we denote the set of pairs
$(q,a)$, for which $\sigma$ has a $(q,a)$-conflict.

If $C(\sigma)=\emptyset$, then $\sigma$ is already almost strongly
regular. The only exceptions might be configurations that are not
reached by plays on strings from  $W(\sigma)$ and
we can easily change $\sigma$ on those configurations to make it
entirely  strongly regular without affecting $W(\sigma)$.

Thus we only need to show that a dominant strategy $\sigma$ with some
conflicts can be transformed into a dominant strategy $\sigma'$ with
$C(\sigma')\subsetneq C(\sigma)$. By repeating this process at most
$|Q||\Sigma_f|$ times, we reach a strategy without conflicts.

To this end, let $\sigma$ have a $(q,a)$-conflict, for some $q$ and
$a$, with $\tau_1,\tau_2,\alpha_1,\alpha_2,u_1,u_2$ as above such that
$\alpha_1$ has minimal possible length. Let $v_1=\natural\alpha_1$.

We first claim that $\sigma$ only plays Read moves on the input word $v_1$.
As a first step towards this claim, we show $v_1au_1\in
W(\sigma)$. Indeed, the strategy $\widetilde{\sigma}$ that plays Read
on $v_1$ and is defined by
$\widetilde{\sigma}(v_1\beta,x)=\sigma(\alpha_1\beta,x)$ afterwards
(and arbitrarily on other configurations) clearly wins on $v_1au_1$,
since $\sigma$ wins from $(\alpha_1,a,u_1)$ on. As $\sigma$ is
dominant, therefore $v_1au_1\in W(\sigma)$ holds.
As $\sigma$ plays Read on all $\Sigma$-symbols of $\alpha_1$, the assumption that $\sigma$ plays Call on some prefix of $v_1$ would yield a smaller instance of a conflict (with respect to the length of $\alpha_1$), and therefore, the claim that   $\sigma$ only plays Read moves on the prefix of $v_1$ is shown.

We say that $\sigma$ is \emph{$(q,a)$-conflict-free after $v_1$} if either $\sigma(v_1,a)=\ensuremath{\mathit{Read}}\xspace$ and there is no $(q,a)$-conflicting
\ensuremath{\mathit{Call}}\xspace-move in plays of $\sigma$ on any word $v_1au\in W(\sigma)$, for some $u$, or vice versa with \ensuremath{\mathit{Read}}\xspace and \ensuremath{\mathit{Call}}\xspace reversed. In both cases, a strategy without any $(q,a)$-conflicts can be obtained by ``copying'' the substrategy of the subgame starting from $(v_1,a,u)$ to any conflicting configuration.

However, we need to show how to guarantee $(q,a)$-conflict-freeness after $v_1$.
Actually, thanks to the finiteness of $L(T)$
there can be no such conflict if $\sigma(v_1,a)=\ensuremath{\mathit{Read}}\xspace$, since $T$ can not return to state $q$ after taking a
transition from $q$. But  in the case where
$\sigma(v_1,a)=\ensuremath{\mathit{Call}}\xspace$, there could be a conflicting $\ensuremath{\mathit{Read}}\xspace$-move at
some configuration $(\alpha,a,u')$ after $(v_1,a,u)$. However, again thanks to the finiteness of
$L(T)$, there can not be any \ensuremath{\mathit{Read}}\xspace moves between $(v_1,a,u)$ and
$(\alpha,a,u')$ and therefore, in particular, $u$ must be a suffix of $u'$.
In this case we show that actually $u'=u$ must hold. By copying the strategy of $\sigma$ of the
subgame on  $(\alpha,a,u)$ to the subgame on $(v_1,a,u)$, a strategy that matches the first
case above can be obtained.

In all cases, it can be concluded from the dominance of $\sigma$ that the new strategies obtained by the described modifications are
again dominant.

We now turn to a more detailed description of the proof.

We first show how to get rid of $(q,a)$-conflicts after $v_1$. Let us thus assume that $\sigma(v_1,a)=\ensuremath{\mathit{Call}}\xspace$, $v_1au\in W(\sigma)$, and for some strategy $\tau$ of Romeo,
$\Pi(\sigma,\tau,v_1au)$ contains a configuration $(\alpha,a,u')$ with
$\delta^*(s,\natural\alpha)=q$ and $\sigma(\alpha,a)=\ensuremath{\mathit{Read}}\xspace$, for some $u'$. As already argued above, there can
not be any \ensuremath{\mathit{Read}}\xspace moves between  $(v_1,a,u)$ and $(\alpha,a,u')$ and
therefore $u$ must be a suffix of $u'$.
We claim that $u'=u$.

Towards a contradiction, let us assume that $u'=u''u$ for some $u''\not=\epsilon$.
We show by induction on $k$ that
$v_1a(u'')^ku\in W(\sigma)$ for each $k$. This is true for $k=0$ by
assumption. Suppose now that $v_1a(u'')^ku\in
W(\sigma)$. Similarly as
before, the play $\Pi(\sigma,\tau,v_1a(u'')^ku)$ reaches configuration
$(v_1,a,(u'')^ku)$ and later on $(\alpha,a,(u'')^{k+1}u)$. From this
configuration on, $\sigma$ is winning.
But then the strategy that plays from $(v_1,a,(u'')^{k+1}u)$ on like
$\sigma$ plays from $(\alpha,a,(u'')^{k+1}u)$ on wins on the string
$v_1a(u'')^{k+1}u$. By dominance of $\sigma$, it follows that $v_1a(u'')^{k+1}u\in W(\sigma)$, completing the inductive step.

However, now we can choose $k$  larger than the length $\ell$ of the longest string
in $L(T)$ to get the desired
contradiction: $v_1a(u'')^{k}u$ has more than $\ell$ symbols and
each of them contributes at least one symbol from $\Sigma$ to the
final history string, which therefore can not yield a win for Juliet.
 Altogether, we have established that $u'=u$.

We now define
$\widetilde{\sigma}$ by
\[
\widetilde{\sigma}(\beta,x)=
\begin{cases}
  \sigma(\alpha\beta',x) & \text{if $\beta=v_1\beta'$, and $\beta'x$ begins with $a$,}\\
\sigma(\beta,x) & \text{otherwise.}
\end{cases}
\]
That $W(\sigma)\subseteq W(\widetilde{\sigma})$ is easy to show: if the
difference between $\sigma$ and $\widetilde{\sigma}$ actually matters for some
word $w\in W(\sigma)$, then $w$ must be of the form $v_1aw'$ and the
first configuration in which $\sigma$ and $\widetilde{\sigma}$ differ is
$(v_1,a,w')$. However, since Romeo can enforce the configuration
$(\alpha,a,w')$, $\sigma$ is winning from that configuration on. Since
$\widetilde{\sigma}$ plays from $(v_1,a,w')$ on like $\sigma$ plays from
$(\alpha,a,w')$ on, we can conclude that $\widetilde{\sigma}$ is winning from
$(v_1,a,w')$, as desired.

Therefore, in the following we can assume that $\sigma$ is $(q,a)$-conflict-free after $v_1$.

Now we are ready to get rid of the $(q,a)$-conflict altogether. We define a strategy $\sigma'$ that copies the substrategy of $\sigma$ from configurations of the form $(v_1,a,u)$ onwards to any conflicting configuration. Formally,
\[
\sigma'(\beta,x)=
\begin{cases}
  \sigma(v_1\beta'',x) & \text{
    \begin{minipage}[t]{8cm}
      if $\beta=\beta'\beta''$,
      $\delta^*(s,\natural\beta')=q$,
      $\beta''x$ begins
      with $a$ or $\call{a}$, and $\sigma(\beta',a)\ne \sigma(v_1,a)$, where $\beta'$ is minimal
    \end{minipage}
}\\
\sigma(\beta,x) & \text{otherwise.}
\end{cases}
\]

Since the sub-plays of $\sigma$ from $(v_1,a,u)$ on do not contain any configurations that can cause a $(q,a)$-conflict, and since clearly no new conflicts are induced, we can conclude that $C(\sigma')\subsetneq C(\sigma)$.

To show that $\sigma'$ is again dominant it suffices to show
$W(\sigma)\subseteq W(\sigma')$. If the
difference between $\sigma$ and $\sigma'$ matters for some
word $w\in W(\sigma)$, then the
first configuration in which $\sigma$ and $\sigma'$ differ is of the form
$(\beta',a,u)$, with
$\beta'$ as in the definition of $\sigma'$ and $u\in\Sigma^*$. Since $\sigma$ is winning from $(\beta',a,u)$ on, a
strategy that plays \ensuremath{\mathit{Read}}\xspace on $v_1$ and plays from
$(v_1,a,u)$ on like $\sigma$ from $(\beta',a,u)$ on wins on the word
$v_1au$. Since $\sigma$ is dominant, $\sigma$ wins on $v_1au$ as well. Since
$\sigma'$ plays from $(\beta',a,u)$ on like $\sigma$ from
$(v_1,a,u)$, it also wins, as desired.
\end{proofof}

\subsubsection{Non-recursive games}\label{sec:ex-nr-nonrecursive}
\short{
	\begin{proof}[Proof idea of Theorem~\ref{theo:right}~(d)]
		Starting with some dominant strategy $\sigma_1$, we inductively construct a
		sequence $(\sigma_1,\sigma_2,\dots)$ of dominant strategies that is
		either finite and ends with a strategy that has no $(q,a)$-conflict, or is infinite and converges to such a strategy. In the convergent case, since each strategy in a non-recursive game is terminating, the limit strategy is also dominant by Lemma~\ref{lemma:conv}. To construct a strategy $\sigma_{k+1}$, the idea is to modify $\sigma_k$ so as to move the earliest $(q,a)$-conflict to a later time in the future.
	\end{proof}
}
\full{
\begin{proofof}{Theorem~\ref{theo:right}~(d)}
Let $G=(\Sigma,R,T)$ with $T=(Q,\Sigma,\delta,s,F)$. Starting with some dominant strategy $\sigma_1$, we inductively construct a
sequence $(\sigma_1,\sigma_2,\dots)$ of dominant strategies that is
either finite and ends with a strategy that has no $(q,a)$-conflict, or is infinite and converges to such a strategy. To construct a strategy $\sigma_{k+1}$, the idea is to modify $\sigma_k$ so as to move the earliest $(q,a)$-conflict to a later time in the future.

We describe next how $\sigma_{k+1}$ is defined from $\sigma_k$. We distinguish two cases.

The first case is that for all $q\in Q$, $a\in\Sigma_f$ and all
configurations $(\alpha_1,a,u_1)$ and $(\alpha_2,a,u_2)$ with
$q=\delta^*(s,\natural\alpha_1)=\delta^*(s,\natural\alpha_2)$ that
occur in plays of $\sigma_k$ on strings from $W(\sigma_k)$, it holds that
$\sigma_k(\alpha_1,a)=\sigma_k(\alpha_2,a)$. In this case
$\sigma_k$ is the last strategy of the sequence.

In the other case,  let $w_1,w_2\in W(\sigma)$ and strategies $\tau_1,\tau_2$ of Romeo such that $\Pi(\sigma_k,\tau_1,w_1)$ reaches some configuration $(\alpha_1,a,u_1)$ with $\delta^*(s,\natural\alpha_1)=q$,
$\Pi(\sigma_k,\tau_2,w_2)$ reaches some configuration $(\alpha_2,a,u_2)$
with $\delta^*(s,\natural\alpha_2)=q$ and
$\sigma_k(\alpha_1,a)\not=\sigma_k(\alpha_2,a)$, such that $|\alpha_2|\ge|\alpha_1|$ and $(|\alpha_2|,|\alpha_1|)$ is lexicographically minimal.

As in the proof of
Theorem~\ref{theo:right}~(c), it can be shown that $\sigma_k$ only
plays \ensuremath{\mathit{Read}}\xspace moves on $\natural\alpha_1$ and that it wins on
$\natural\alpha_1au_1$. By minimality of $(|\alpha_2|,|\alpha_1|)$ with $|\alpha_2|\ge|\alpha_1|$, we can conclude that actually $\alpha_1=\natural\alpha_1$.

Now we are ready to define $\sigma_{k+1}$. It plays like $\sigma_k$
except that if it reaches a configuration with
$T$-state $q$ and current symbol $a$ after precisely $|\alpha_2|$ moves, then it continues to play like
$\sigma_k$ for the history string $\alpha_1$. Formally,
\[
\sigma_{k+1}(\beta,x)=
\begin{cases}
  \sigma_k(\alpha_1\beta'',x) & \text{
    \begin{minipage}[t]{7.8cm}
      if $\beta=\beta'\beta''$, $|\beta'|=|\alpha_2|$, $\delta^*(s,\natural\beta')=q$, and
      $\beta''x$ begins with $a$ or $\call{a}$,
    \end{minipage}
}\\
\sigma_k(\beta,x) & \text{otherwise.}
\end{cases}
\]

We need to show that $\sigma_{k+1}$ is dominant. Towards a
contradiction, suppose it is
not.
Since $\sigma_k$ is dominant by the induction hypothesis, there exist $w\in
W(\sigma_k)$ and a Romeo strategy $\tau$ such
that Juliet does not win $\Pi(\sigma_{k+1},\tau,w)$. Thus, the plays of
$\sigma_{k+1}$ and $\sigma_k$ against $\tau$ on $w$ reach a
configuration $(\beta,av)$ with $\beta\in\hist{\Sigma}^*$ and
$v\in\Sigma^*$ such that $\delta^*(s,\natural\beta)=q$. Furthermore,
$\sigma_k$ wins from $(\beta,av)$ on, but $\sigma_{k+1}$ does not, and
therefore $\sigma_k$
does not win on $\alpha_1av$. Since $\sigma_k$ is dominant, no
strategy wins on $\alpha_1av$. However, consider the strategy $\widetilde{\sigma}$
defined by
\begin{align*}
\widetilde{\sigma}(\alpha,b)=
\begin{cases}
\sigma_k(\alpha,b),&\text{if $\alpha_1$ is not a prefix of $\alpha$,}\\
\sigma_k(\beta\alpha',b),&\text{if $\alpha=\alpha_1\alpha'$ for some $\alpha'\in\hist{\Sigma}^*$.}
\end{cases}
\end{align*}
 On the input word $\alpha_1av$, $\widetilde{\sigma}$ initially plays only Read moves on the prefix $\alpha_1$. Upon reaching the configuration $(\alpha_1,av)$, it starts playing like $\sigma_k$ would play after reaching the configuration $(\beta,av)$.
Since $\sigma_k$ wins from $(\beta,av)$ on, $\widetilde{\sigma}$ wins on $\alpha_1av$, the desired contradiction.

Altogether, $(\sigma_1,\sigma_2,\dots)$ is indeed a sequence of dominant
strategies. If it is finite, then its last strategy $\sigma_k$ has no two conflicting
configurations that can occur in plays on words from $W(\sigma_k)$. Thus, it can be turned into a strongly regular dominant strategy by adapting it only for configurations that cannot occur in plays on words where it does not win.

If $(\sigma_1,\sigma_2,\dots)$ is infinite, it converges towards a strategy
$\sigma'$, because, for each $n$, $\alpha_2$ can be of length $n$  at most $|Q||\Sigma_f|$
times in the above construction. Since $G$ is non-recursive, every play terminates, and
therefore Lemma~\ref{lemma:conv} guarantees that $\sigma'$ is
dominant as well. Finally, $\sigma'$ can be transformed into a
strongly regular strategy just as in the finite case.
\end{proofof}
We note that the proof uses non-recursiveness only to guarantee that
$\sigma'$ has the same winning set as every $\sigma_k$.

\subsubsection{Unary games}\label{sec:unary}

To complete the proof of Theorem~\ref{theo:right} we show in this subsection that every unary game has an undominated strategy. Before we turn to this proof, we first present some observations and a helpful lemma.
Let in the following always $\Sigma=\{a\}$ and

We first observe that, since the DFA $T$ for the unary target language is minimal, we can assume that it is of the following form: $Q=\{0, 1, \dots, m-1\}$, for some $m$, with $1$ as initial state; the transitions are precisely the edges $(i-1, i)$ for $i=1,\dots,m-1$ and the edge $(m-1,j)$ for some state $j\in Q$.

We can assume that $a\not\in R_a$, since otherwise always playing Read is a dominant strategy. Indeed, playing Call cannot yield an advantage in this case, since Romeo can choose to never change the current word. Thus, we can restrict our attention to the case where the replacement language contains only words of length at least $2$.

We call a strategy $\sigma$ \emph{almost undominated} if there are only finitely many words on which $\sigma$ does not win but some strategy dominating $\sigma$ does win.

\begin{lemma}\label{lem:almost}
  If a game has an almost undominated strategy then it also has an undominated strategy.
\end{lemma}
\begin{proof}
  Let $\sigma_0$ be an almost undominated strategy, let $W_0$ be the finite set of words  on which $\sigma_0$ does not win but some strategy dominating $\sigma_0$ does win, and let $n=|W_0|$. For each $i>0$, we define $\sigma_i$ as $\sigma_{i-1}$ if  $\sigma_{i-1}$ is undominated or as some strategy that dominates $\sigma_{i-1}$ and wins on the smallest word in $W_{i-1}$. We define $W_i$ as the subset of $W_{i-1}$ of words on which $\sigma_i$ does not win but some other strategy dominating $\sigma$ does win. Clearly, $W_n$ is empty and thus $\sigma_n$ is undominated.
\end{proof}

\begin{proofof}{Theorem~\ref{theo:right}~(e)}
Thanks to Lemma~\ref{lem:almost} it suffices to show that any unary game has an almost undominated strategy.

	We may assume that the target language $L(T)$ is $m$-periodic,
        meaning that $\delta(m-1,a)=0$. The theorem for the general
        case where $\delta(m-1,a)>0$ is then implied as follows: the
        target language of such a general automaton differs from some
        $(m-j)$-periodic language by at most the $j$ shortest
        words. Hence, if a strategy is almost undominated for the
        associated $(m-j)$-periodic language, then it is also almost
        undominated for the actual target language. We can also assume
        that $|R_a|>1$, since otherwise $G$ is prefix-free.

In the following, we identify a string $a^\ell$ with the number $\ell$.	 Let $n, k\ge 1$ be such that $1+n$ and $1+n+k$ are the shortest words in $R_a$.

	Since every Call extends the remaining string by at least $n$ symbols, for each strategy there is a strategy with (at least) the same winning set, which always plays at least $n$ Reads after each Call. We denote such a combined move by CR$^{n}$. We therefore assume in the following that all strategies of Juliet that we consider are of this normal form and we only consider configurations and history strings where every CR$^n$ is complete. Moreover, whenever the successor state of the $T$-state of the current configuration is accepting, Juliet plays Read (because if this Read reaches the end of the word, then Juliet wins, and otherwise she does not hurt her chances to win by delaying Calls until later).

With each configuration $K$ we associate a profile $(c,r,\ell)$
consisting of the number $c$ of CR$^n$s that were played so far, the
number $r$ of additional Reads played so far (outside CR$^n$ moves)\footnote{Thus the total number of Reads before $K$ is $cn+r$.} and the length $\ell$ of the remaining string.
We note that history strings for games with unary alphabet are very uniform. Indeed, for arbitrary strategies $\sigma$ of Juliet, strategies $\tau,\tau'$ of Romeo, strings $w,w'$ and $i\ge 0$ it holds: if the plays $\Pi(\sigma,\tau,w)$ and $\Pi(\sigma,\tau',w')$ last for at least $i$ moves, then their history strings after $i$ moves are identical. In particular, for every fixed $\sigma$, each profile determines uniquely its underlying configuration.

By $\sigma_0$ we denote Juliet's strategy that always reads, and by $\tau_0$ and $\tau_1$ we denote the strategies of Romeo that always play $1+n$ and always play $1+n+k$, respectively.
We say that a strategy $\sigma$ is \emph{patient} if there is a string $w$ such that $\Pi(\sigma,\tau_0,w)$ has at least $m$ Call-moves.

Let $L$ be the union of $L(T)$ and the set of all strings of the form $w+ik$ with $w\in L(T)$, $w\ge m$, and $i\in \{1,\ldots,m-1\}$. We note that $L$ is ultimately $k$-periodic. More precisely, for all words $w$ of length at least $(k+1)|Q|$ it holds that $w\in L$ if and only if $w+k\in L$.

The existence of an almost undominated strategy can be concluded from the following three claims:
	\begin{enumerate}[(a)]
        \item If $\sigma_0$ is not undominated then there is a patient strategy that dominates $\sigma_0$. \label{it:unaryPatient}
		\item If there is a patient strategy that dominates $\sigma_0$, then there is a strategy that wins on $L$. \label{it:unaryInducedGood}
		\item Every strategy that wins on $L$ is almost undominated. \label{it:unaryNoneBetter}
	\end{enumerate}

	\ \\
	\noindent \textit{Proof of (\ref{it:unaryPatient}):}

	\noindent The proof is by contradiction. We assume that $\sigma_0$ is not undominated but that every strategy $\sigma$ that dominates it, uses at most $C$ Call-moves, for some $C<m$.
Let $\sigma$ be a strategy dominating $\sigma_0$ that has maximally $C$ Call moves.
Let $w$ be sufficiently large and $K$ be a configuration in the play $\Pi(\sigma,\tau_0,w)$ with $T$-state $0$ with $C$ Call moves in its history string $\alpha$. Let $\sigma'$ be the strategy that plays $\sigma'(\beta,a)=\sigma(\beta,a)$ for strict prefixes $\beta$ of $\alpha$ and $\sigma'(\alpha\beta,a)=\sigma(\beta,a)$, otherwise.
It is easy to see that $\sigma'$ has more than $C$ Call moves and dominates $\sigma_0$, the desired contradiction.

	\ \\
	\noindent \textit{Proof of (\ref{it:unaryInducedGood}):}

	\noindent

Let $\sigma$ be a patient strategy that dominates $\sigma_0$.
Let $K$ be some configuration with profile $(m,r,\ell)$ and for which Read was played in the last move. We claim that $\sigma$ wins from $K$ on, if $r+\ell-ik\in L(T)$, for some $i\in\{0,\ldots,m-1\}$ with $ik<\ell$.

To this end, let $\tau^j$ denote the Romeo strategy that plays $1+n+k$ during its first $j$ moves and $1+n$ afterwards.

Let thus $w=r+\ell-ik$.
Since $w\in L(T)$, $\sigma$ wins on $w$. In particular, $\sigma$ wins against strategy $\tau^i$. It is easy to see that the play $\Pi(\sigma,\tau^i,w)$ reaches a configuration with the same profile as $K$ and thus, as explained before, $K$.
Since $\sigma$ wins on $w$, it thus wins all plays from $K$ on.

Next, we are going to construct from $\sigma$ a strategy $\sigma'$ that wins on $L$. To this end, let $w\in L(T)$ be such that $\Pi(\sigma,\tau_0,w)$ has at least $m$ Call-moves. Let $(m,r,\ell)$ be the profile of the configuration $K$ that is reached in $\Pi(\sigma,\tau_0,w)$ after the $m$-th Call move.  By the above claim, $\sigma$ wins from every configuration $(m,r,\ell')$, for which $r+\ell'-ik\in L(T)$, for some $i\in\{0,\ldots,m-1\}$ with $ik<\ell'$. The $T$-state of $K$ is $r'=r \mod m$.

Strategy $\sigma'$ is defined as follows.
It first does $r'$ Read moves, yielding some configuration $K'$ with $T$-state $r'$.
 From there on, it copies the strategy of $\sigma$ in plays that start from $K$. More precisely, let $\alpha$ be the history string of $K$ and $\alpha'=r'$ be the history string of $K'$. Then, for every history string $\beta$, $\sigma'$ plays on $\alpha'\cdot\beta$ like $\sigma$ on  $\alpha\cdot\beta$. We can conclude that $\sigma'$ not only wins on every string $v\in L(T)$ but also on every string of the form $v+ik$ with $v\in L(T)$, $v\ge r'$ and $i\in\{0,\ldots,m-1\}$.

Therefore, $\sigma'$ is a winning strategy for $L$, and \ref{it:unaryInducedGood} holds.

	\ \\
	\noindent \textit{Proof of (\ref{it:unaryNoneBetter}):}

\noindent We show that there is no strategy for Juliet that wins on $L$ and some word $w\not\in L$ of length at least $(k+1)m$.

Let $d$ be the ultimate number of words in $L$ per $k$ words, that is let $d:=|L\cap\{km+1,\ldots,km+k\}|$ be the number of words in $L$ per every $k$ adjacent words. Suppose some strategy $\sigma'$ wins on $L$ and on some word $w\notin L$ of length at least $km$, and let $L'=L\cup\{w\}$. In particular, the play $\Pi(\sigma',\tau,v)$ terminates, for every $v\in L'$ and every strategy of Romeo. Towards a contradiction, we prove by induction that, for every $t\ge 1$, $\Pi(\sigma',\tau_1,w)$ reaches\footnote{We recall that $\tau_1$ is the strategy of Romeo that always chooses the answer string $1+n+k$.}  some configuration $K_m$ with profile $(t,r,\ell)$, for some $r,\ell$. Clearly, this contradicts the assumption that $\Pi(\sigma',\tau_1,w)$ terminates.

For $m=1$, the claim follows since $w\not\in L(T)$.

For the inductive step, let $K$ be the first configuration  in $\Pi(\sigma',\tau_1,w)$ with profile $(m,r,\ell)$, for some $r,\ell$. Clearly, the move that leads to $K$ is a $CR^n$-move and $\ell> k$, since Romeo played $1+n+k$. If $\Pi(\sigma',\tau_1,w)$ makes a further $CR^n$-move after $K$, we are done with the inductive step, thus we assume it does not. Since $\ell> k$, the play must therefore reach a configuration $K''$ with profile $(m,r',k)$, for some $r'$. Let  $\alpha$ be its history string.

By $w_1,\ldots,w_d$ we denote the minimal $d$ words that are longer than $w$, and for which $\sigma'$ is a winning strategy. For every $i\le d$, let $c_i=|w_i|-|w|$. By the choice of $d$ and since $L$ is $k$-periodic beyond $km$, it follows that $c_d\le k-1$.

Let $\tau'$ denote the strategy that deviates from $\tau_1$ (only) by answering the $CR^n$-move at configuration $K'$ by $1+n$.
 It is easy to see that, for each $i\le d$, the play $\Pi(\sigma',\tau',w_i)$ reaches, following the same history string $\alpha$,  a configuration $K''_i$ with profile $(t,r',c_i)$. Since we assume that $\sigma'$ wins from all these configurations, and there can be at most $d$ accepting states within the next $k$ states from the state of $T$ for $K''$, $\sigma'$ has to play $CR^n$ at least once during the next $k$ steps. The play  $\Pi(\sigma',\tau_1,w)$ thus reaches a configuration with profile $(t+1,r'',\ell')$ with some $r''$ and $\ell'$, completing the inductive step.
\end{proofof}
}

\section{Introduction}
\input{1_introduction}
\section{Preliminaries}\label{cha:preliminaries}
\input{2_preliminaries}
\section{Existence of dominant and undominated strategies}\label{cha:existence}
\input{3_existence}
\input{3_existence-positive}
\input{3_existence-negative}
\section{Complexity results for regular strategies}\label{cha:complexity}
\input{6_complexity}
\section{Conclusion and open questions}\label{cha:summary}
\input{7_conclusion}
\bibliographystyle{plainurl}

redpajama_set_name: RedPajamaArXiv


text:
Vic govt. arm puts blade to power use
Sustainability Victoria to cut its power consumption in half
By Scott Mckenzie | January 22, 2007 -- 22:00 GMT (14:00 PST) | Topic: IBM
Sustainability Victoria expects to slash its energy use by more than 50 percent with the implementation of IBM BladeCenter servers in its new office in Melbourne.
The organisation, which partners with the state government and individual businesses to encourage Victorians to use resources more efficiently, practised what it preached with a drastic revamp of its server room when it moved to a single location in October 2006.
Jan Reiher, Sustainability Victoria knowledge and ICT manager, told ZDNet Australia the adoption of the blade servers and better management tools would enable it to cut its yearly power consumption from well over 100,000 kW-h to 40,000 kW-h.
A review of its energy use by a third party prior to the move revealed that Sustainability Victoria's IT infrastructure consumed up to 75 percent of its electricity usage across three sites. The server room on its own accounted for 60 percent of the total.
To minimise energy usage in the datacentre being built, Sustainability Victoria reduced the number of servers from 30 to 13 (64-bit) blades in two stages. It had previously deployed "lots and lots of racks" to run two platforms, she said.
The initial move cut the number of servers to 20, while the introduction of a single platform reduced the number to 13.
Reiher said the deployment was radical, but very exciting. It's all about a better way to manage the use of energy and not just saved space in the datacentre, she added. "We have to limit the energy input which means that we have to re-think the way servers are used."
The ability to intelligently manage server usage, as well as a reduction in overall heat due to fewer servers, will not only slash power consumption but result in lower ongoing costs for the datacentre, according to Reiher. Using IBM management tools, for example, Sustainability Australia is able to track the energy usage of each blade. The organisation is also able to reduce the power consumption of non-critical servers at night and on weekends.
Being able to manage the heat is a big plus for Sustainability Victoria. It means the organisation is able to install a smaller air conditioning system in its revamped datacentre to keep the servers cool. Reiher said air conditioners are a major source of power consumption for organisations.
The move to the new office last year presented the organisation with a challenge in more ways than one. As well as the server room re-design, Sustainability Victoria -- formed in October 2005 -- had to merge IT systems and platforms of two predecessor organisations.
The organisation was in the process of "moving around 40 to 50 applications -- including document systems, Web applications and GIS Mapping -- to the new server environment". Reiher said it expects to complete the migration by mid to late February.
Everything from its former offices had to be dismantled and moved to the new premises over a weekend to ensure there was no interruption with the old platform, she said.
Once it had the old platform bedded-down and working, Sustainability Victoria, in conjunction with independent IBM consultants IQT Systems and business partner Southern Cross Computing Services, began migrating the duplicated servers into a single technology environment.
"Our objective is for a server a day to be closed," Reiher said. "We have built [configured] the servers and implemented the IBM management system, and we are moving the applications now."
Sustainability Victoria is also looking into virtualisation technology for further server consolidation and more efficient utilisation of its resources, according to Reiher.
For her the major benefit is the maximum utilisation of each server -- using the same amount of energy -- without additional heat being produced. She spoke of up to 80 percent server utilisation as opposed to around 20 percent -- confirmed in actual tests by the organisation -- on the old servers.
In addition to the blades, the new datacentre includes an IBM System Storage DS4700 storage area network (SAN) and an IBM tape back-up library. Of the SAN, Reiher said it was new for the organisation and "quite a bit of work".
"Data is critical to our organisation. Our future data demands are high so it's important that we can manage any extension easily. It [the SAN] gives us greater flexibility to grow."
Servers Big Data Analytics Artificial Intelligence Cloud Enterprise Software Data Centers
More from Scott Mckenzie
Vista take-up hits bumpy patch
Broadband ... it's time to take the glasses off
BlackBerry ... not as safe as you thought?
Access Card is not a national ID: Govt
Brazil completes first blockchain real estate sale
The transaction led by local construction giant Cyrela and startup Growth Tech used IBM Blockchain technology.
IBM teams up with Columbus Crew to design, deliver digital experiences
IBM is increasingly looking toward sports as a way to highlight its technology and digital design services.
ANZ, CBA, Westpac partner IBM for Lygon blockchain bank guarantee pilot
Three of the four Australian banking heavyweights are trialling Lygon, a new digital bank guarantees platform that uses blockchain.
HCL now fully controls IBM software including Notes and Domino
A new division, called HCL Software, has also been created by the company to push out the software products.
IBM's Watson Marketing breaks off into separate company
On its first day as a standalone business, the new company says it's mature yet agile enough to take on major competitors like Adobe, Oracle and Salesforce. ...

redpajama_set_name: RedPajamaCommonCrawl


NEW YORK—Knowcross has partnered with Ritz Paris, which recently reopened its doors after a $400-million, four-year renovation. Ritz Paris turned to Knowcross for a central, real-time communication center that speeds up responses to guests' requests and allows the hotel to function more efficiently overall, according to the company.
Ritz Paris has integrated the entire Knowcross suite of services: Know Service, Know Housekeeping, Know Glitch, Know Inspection and Know Mobile.
Knowcross offers a mobile communication system across all departments to anyone on any computer or smartphone, anywhere. This eliminates the need to travel to and from a set location in the hotel for assignments. Language settings can also be customized for multilingual staffs.
Post-renovation, the platform's reporting system spotlighted repeat failures of equipment and room issues that wouldn't have otherwise been as easily detected, according to the company. Ritz Paris was able to make replacements rather than continued unsuccessful repairs.


A toddlers' outfit that shows off seasonal camouflage graphics.
A sporty look that's ready for warm weather. This toddlers' two-piece outfit comes with a t-shirt that shows off a tongue-label graphic set against a seasonal camouflage pattern. The shorts are covered in the same camouflage pattern. Both are made of 100% cotton single jersey for a comfortable feel.


text:
Heads Up, Mann Fan(n)s, the 'Blackhat' Director's Cut Is Coming to FX
Charles Bramesco Published: May 8, 2017
As currently working American directors of action cinema go, you can't do a whole lot better than Michael Mann. And in Mann's filmography, you can't do a whole lot better than Heat. His 1995 magnum opus is a gem of committed masculine performance, from the robbers' finely tailored robbin' suits to the concluding note of man-to-man camaraderie. And in between the hyper-masc displays of honor and strength, Mann stages some of the most technically accomplished set pieces of his career, all but putting the audience's nerves through a paper shredder. Heat will get a full director's cut set for release tomorrow (though the changes will be mostly limited to image processing), but today brings the news that another Mann film is taking on a second life.
The Playlist notes that the director's cut of Blackhat, Mann's somewhat polarizing techno-thriller featuring Chris Hemsworth from a couple years back, will play on FX tomorrow (Tuesday, May 9) at 7PM. This will mark the broadcast premiere of the film's complete and unexpurgated version, though the full Blackhat director's cut originally played at the Brooklyn Academy of Music in February 2016, where reports indicated that the changes made to the film were minor. But even so, a new version of a Mann film is a new version of a Mann film. Hopefully the expanded runtime allows for more highly specialized jargon about the ins and outs of hacking.
A big week for Mann Fanns, as they're called. But as he fine-tunes Heat and Blackhat, the question of when we can expect an original feature from the director persists. Movement remains slow on his Enzo Ferrari biopic, but hopefully we'll get an update on the film scheduled for a 2019 release.
Hugh Jackman to Replace Christian Bale in Mann's Ferrari Biopic
Filed Under: Michael Mann
Categories: Movie News


nd's new album completed !
Recording Artist Nader DeAik wrapped up his highly anticipated album that will include duets with international star singers. Release date to be announced!
Check out Nader DeAik's original 2014 Single "Pa'lante" featuring Cris Matos! Available online. Nader DeAik is back with a smashing groove "Pa'lante" that defines World Fusion pop music at its best!


text:
Jade Mebarak je izmišljena arapska žena i protagonistica telenovele Klon. Glumi ju Sandra Echeverria, a kreirala ju je Glória Perez.

Pozadina
Jade je jedina kći svojih roditelja. Iako potiče iz muslimanske obitelji, odrastala je u Miamiju.  Nakon smrti svojih roditelja seli se u Maroko, k ujaku Sidi Ali Rashidu.

Obitelj

Ujak Sidi Ali Rashid
Sidi Ali Rashid je Jadein ujak. Preuzeo je o njoj brigu kada joj je bilo dvanaest godina.

Djeca

Khadija
Khadija je Jadeina i Saidova kći. Ona je željela da joj roditelji žive zajedno, sretni. Veoma voli Jade, no kada sazna da joj je majka zaljubljena u "zapadnog" čovjeka, naljuti se na nju i odbacuje ju.

Nećak ili nećakinja

Samira
Samira je Jadeina nećakinja. Kći je njene rođakinje Latife. Samira veoma nalikuje na Jade jer je, kao i ona, odrastala u "zapadnoj" zemlji.

Amin
Amin je Jadein nećak. Sin je njene rođakinje Latiffe. Amin veoma nalikuje na Jade jer je, kao i ona, odrastao u "zapadnoj" zemlji.

Izvori
 http://www.imdb.com
Izmišljeni likovi
Likovi iz televizijskih serija

redpajama_set_name: RedPajamaWikipedia


text:
Sports-Free
Bossier falls to No. 4 Evangel
rhedges@bossierpress.com
The Bossier Bearkats couldn't get anything going against the No. 4 Evangel Eagles in a 42-0 loss Friday night at Rodney Duron Field.
Bossier managed just two first downs and 38 total yards.
The Bearkats fell to 1-7 overall and 0-3 in District 1-3A. Evangel improved to 6-1 and 3-0.
Evangel rolled to a 21-0 first-quarter lead and extended it to 35-0 at the half.
Freshman quarterback Connor Curry tossed six touchdown passes. He completed 14 of 25 for 214 yards with one interception.
Chris Hall led Bossier with 40 yards on 18 carries.
Isaiah McKinsey led the defense with six tackles, including two sacks and two for losses.
Jonathan Van Vleet and Jalen Oliver had four apiece.
Chris Williams had a interception.


text:
Leks Drops Debuts Single on ProgRAMLeks makes his debut on the label!
Leks makes his debut on ProgRAM with a mixture of lush rhythms and guttural basses, the type of which have made RAM's sister-label a poster for versatility within its roster. A debut for the producer on ProgRAM, his forthcoming single demonstrates his viability to be part of its ever-growing catalog, with growling drum & bass spiced with soulful flavors. And it leaves a stamp for the artist to build from as the New Year rolls out.
'Wasted Time', the releases a-side, rolls with thumping bass levels tied with the track's vocal textures; its reverse 'Focus For Me' continues with winding LFOs and razor-sharp beats, providing an even moodier offering. So once again, it's time to get with the ProgRAM. One which provides another slamming introduction.


This is a placeholder page for Nellie Farmer, which means this person is not currently on this site. We do suggest using the tools below to find Nellie Farmer.
You are visiting the placeholder page for Nellie Farmer. This page is here because someone used our placeholder utility to look for Nellie Farmer. We created this page automatically in hopes Nellie Farmer would find it. If you are not Nellie Farmer, but are an alumni of Reidsville High School Reidsville, NC, register on this site for free now.


The heavy handed measures can be gotten away with BECAUSE it's China. While they have a right to make complaints, I disagree with the manner in which companies get treated.
China thinks all of Asia is "theirs", they just haven't gotten around to convincing the rest of the world!
... now replace the word "china" with "USA" and you reuse your text for most other issues as well.
The Senkakus are a part of Japan - not sure why china remains confused. Taiwan is Taiwan. Muji is Muji. And of course the South china Sea, well, the islands/shoals therein belong to many countries.
As an aside to that, I think the Australian government is going to issue new rules pretty soon about free expression at university. They need to stamp out the bullying of teachers and professors who suggest Taiwan is a sovereign country. Multiple instances in recent years related to that. They might also crack down on Confucius institutes. I'm looking forward to it.
China can take a long walk off a short pier. The CCP dictatorship is so used to being able to get away with it's authoritarian ways domestically that it thinks it can do this with the entire world. If China wants to trade with the rest of the world it needs to learn to behave like everyone else. Or maybe they should borrow "juche" from North Korea and see how that works out.
Taiwan is a country, regardless of what Winnie the Pooh says. They even have their own flag, currency, and Olympic team.
This is why China will never gain respect from the international community. Keeps your politics out of business.
Call the Chinese Embassy and ask for visa to go Taiwan, they'll tell you they cant issue one.
Yeah, I need a visa to go to China but I never needed one to go to Taiwan or Hong Kong.
Abe must wise up. As PM of Japan, if Abe truly believe that senkakus are a part of Japan, then he should exercise the sovereignty right to donate them to China as gift. The problem is solved and must be solved.
I don't agree with China but a business is a business is a business. Why push nationalistic ideas, regardless of who you favor? National sovereignties are passé. It's just a matter of time before they disappear. Don't get involved in these matters.
I wonder if Muji can get away with ignoring the complaint or if China's business is to valuable to lose. I hope they choose the morally right option and fight the PRC's bullying and censorship.
just don't distribute the catalog in china. i'm sure they'd be very popular in taiwan. i don't see how they can complain in the disputed islands are excluded.
I hope China confirmed this with the local government in Chinese Taipei.
now replace the word "china" with "USA" and you reuse your text for most other issues as well.
Really now? When has the US laid claim to Taiwan, or worried about the Senkaku Islands being their property?
You are just looking to compare, deflect, and obfuscate the discussion, how very Japanese.
Sorry China, other people are free to do and think as they please.
"There is no territorial dispute to be settled over the Senkaku Islands.
Always find comments like this strange. If there were no territorial dispute, we would not be having this discussion and this story would not have been written. I don't approve of China's actions on this at all, but Japan's stance also doesn't make much sense.
China is being a terrible bully.
Watch out Japan, in one hand is the olive leaf of friendship of trade and exchange, while round their back they are holding a knife to stab you if you don't do what they want..
Likewise I don't recall China having anything to do with trips to Taiwan or Hong Kong.
Abe has to make choice, put Japan before law, or law before Japan. Cario Declaration terminates Japan's historical claims at the end of WW2. As a defender of rule of the world, Abe must obey the law. There is no basis for Japan to continue using pre-war argument, no matter how laughable that might be. On the other hand, China has longer historical claim than Japan and no law terminates China's claim.