\section*{Abstract}{\small
Within our Galaxy, supernova remnants are believed to be the major sources of cosmic rays up to the “knee”. However important questions remain regarding the share of the hadronic and leptonic components, and the fraction of the supernova energy channelled into these components. We address such question by the means of numerical simulations that combine a hydrodynamic treatment of the shock wave with a kinetic treatment of particle acceleration. Performing 3D simulations allows us to produce synthetic projected maps and spectra of the thermal and non-thermal emission, that can be compared with multi-wavelength observations (in radio, X-rays, and gamma-rays).
Supernovae come in different types, and although their energy budget is of the same order, their remnants have different properties, and so may contribute in different ways to the pool of Galactic cosmic-rays. Our first simulations were focused on thermonuclear supernovae, like Tycho's SNR, that usually occur in a mostly undisturbed medium. Here we present our 3D simulations of core-collapse supernovae, like the Cas~A SNR, that occur in a more complex medium bearing the imprint of the wind of the progenitor star.
\vspace{10mm}
\normalsize}
\end{minipage}

\section{Introduction}
\label{sec:intro}

Supernova remnants (SNRs) are believed to be the major sources of Galactic cosmic rays (CRs), although their efficiency in accelerating protons -- that make most of the CRs, but are difficult to detect -- is not firmly established. Understanding the origin of Galactic CRs requires a joint modeling of the remnant evolution and of particle acceleration by shock waves. We have developed a framework for simulating this in a 3-dimensional and time-dependent manner, which allows us to produce realistic synthetic maps of the broadband emission from the SNR including the effect of efficient particle acceleration at the blast wave \citep{Ferrand2010a, Ferrand2012g, Ferrand2014b}.
We applied our simulations previously to the case of the remnant from a typical thermo-nuclear (TN) supernova (Type Ia), evolving in a uniform medium. We showed how energetic protons affect the emission from the remnant: they impact the dynamics of the shock wave, and therefore the thermal emission from the shell (in optical and X-rays), and they impact the evolution of the magnetic field, and therefore the non-thermal emission from the electrons (in radio to X-rays and $\gamma$-rays).
Here we present our first results for the case of the remnant of a core-collapse (CC) supernova (type II or Ib/c), that is still evolving inside the wind of its progenitor. While our previous results were most relevant to an object like Tycho's SNR (G120.1+1.4), our new simulations are more appropriate for an object like Cas~A SNR (G111.7-02.1).

\section{Model}
\label{sec:model}

We refer the reader to our previous papers for the details. In our approach we combine a hydrodynamic treatment of the blast wave with a kinetic treatment of particle acceleration. The  particles are injected at the shock front from the shocked ambient medium, and then are accelerated by the Fermi~I process. If acceleration is efficient, their pressure can be large enough that it modifies the structure of the shock wave. The diffusive shock acceleration mechanism relies on magnetic turbulence, that scatters particle off -- this effect is embedded inside the diffusion coefficient. Particles that stream in the upstream region can sustain the turbulence they need to keep being accelerated, hence a second back-reaction loop.

To study this complex system, we rely on numerical simulations. We start our simulations at a small age (here of 5~yr) using self-similar profiles from \cite{Chevalier1983a}. The SNR is then evolved (here up to 300~yr) using a custom version of the code RAMSES \citep{Teyssier2002a}, in a Cartesian grid that is comoving with the blast wave and adaptively refined. Particle acceleration at the forward shock is estimated at each simulation step using the  semi-analytical kinetic model from \cite{Blasi2004a} with extensions from \cite{Caprioli2009a}.

\subsection{The stellar wind}
\label{sec:model_wind}

We consider a fiducial CC SN with explosion energy of $10^{51}~{\rm erg}$ and ejecta mass of $3~M_\odot$, with the ejecta following a steep power-law $\propto r^{-9}$ as a function of radius. For the stellar wind of the progenitor, we adopt a mass loss rate of $\dot{M}_w = 10^{-5}~M_\odot\:\rm{yr^{-1}}$ and a speed of $v_w = 10~\rm{km~s^{-1}}$, parameters that are typical of the red super-giant (RSG) phase and thus appropriate for Cas~A. Conservation of mass implies that the wind profile goes as $r^{-2}$ in the inner region where it was expanding freely, up to the termination shock. We consider a SNR that is young enough that it is still propagating inside this un-shocked stellar wind. The structure of a wind bubble can be more complex, especially as there may be multiple wind phases during the lifetime of a star. We refer the reader to the work by \cite{Dwarkadas2005a,Dwarkadas2007b} for the 1D evolution of a SNR inside a more complex wind bubble (without particle acceleration).
For diffusive shock acceleration we also need a description of the magnetic field in the wind. We adopt a constant magnetization $\sigma = 0.1$ (see \citealt{Chevalier1994b} and \citealt{Lee2014b}), so that~B goes as $r^{-1}$. Upstream of the forward shock, B~varies over time from $44\:\mu$G to $1\:\mu$G. Other parameters are similar to our previous simulations.

\section{Results}
\label{sec:results}

We show here preliminary results for the CC SNR case, with an effective resolution of $256^3$. We reproduce the previous results for the TN SNR case at the same resolution for comparison.

\subsection{Thermodynamics and thermal emission}
\label{sec:results_TH}

\begin{figure}
\center
\includegraphics[width=7.6cm]{figures/L68_t0500_off0on0_cut_diag-np.png}
\includegraphics[width=7.6cm]{figures/L68_t0300_off0on0_cut_diag-np.png}
\includegraphics[width=7.6cm]{figures/L68_t0500_off0on0_cut_diag-Te.png}
\includegraphics[width=7.6cm]{figures/L68_t0300_off0on0_cut_diag-Te.png}
\caption{Slices in the shocked region. Top: mass density, bottom: electronic temperature. Left: TN SNR, right: CC SNR. Each plot compares the cases without (OFF, on the left) and with (ON, on the right) including the back-reaction of particle pressure.}
\label{fig:maps_hydro}
\end{figure}

\begin{figure}
\center
\includegraphics[width=7.6cm]{figures/L68_t0500_off0on0_spc_map_TH.png}
\includegraphics[width=7.6cm]{figures/L68_t0300_off0on0_spc_map_TH.png}
\caption{Integrated spectra: thermal emission of the plasma. Left: TN SNR, right: CC SNR. Each plot compares the cases without (OFF, dashed) and with (ON, solid) including the back-reaction of particle pressure. The three curves show the emission from the ejecta (in red), from the interstellar/circumstellar medium (in blue), and from both (in black).}
\label{fig:spectra_TH}
\end{figure}

The density in the shocked region is shown on the top of Figure~\ref{fig:maps_hydro}. Compared to the case of a TN SNR (left column), we see that for a CC SNR (right column) the Rayleigh-Taylor fingers are more marked and elongated, and can reach the shock front when the back-reaction is taken into account (``ON'' cases). In the latter case the post-shock protons temperature (not shown here) is greatly reduced as the energy is diverted into particles, and the effect is even more dramatic for a CC SNR. However the electrons are not expected to be heated as fast assuming Coulomb equilibration; we observe a reduction of the post-shock electronic temperature by a factor of about~2. This is illustrated on the bottom of Figure~\ref{fig:maps_hydro}.

The thermal emission of the plasma is computed with a code based on \cite{Mewe1985a}. It depends on the density and temperature, and on the ionization state of the plasma, that has to be computed out of equilibration. For the stellar wind we use solar abundances, for the stellar ejecta we use abundances from a nucleosynthesis model used by \cite{Nozawa2010a} for the modelling of Cas~A. Note that we use a spatially uniform distribution in our simulations, yet we obtain non-uniform thermal emission maps (not shown here) because of the varying plasma conditions. Integrated spectra are presented on Figure~\ref{fig:spectra_TH}, from ejecta-dominated regions, interstellar/circumstellar medium-dominated regions, and both. In both the TN and CC cases, with efficient acceleration the emissivity of the shocked ISM is reduced, all the more so as the photon energy gets higher. But for the CC SNR the total emission is completely dominated by the ejecta, so the effect would be barely detectable.

\subsection{Magnetic field and non-thermal emission}
\label{sec:results_NT}

\begin{figure}
\center
\includegraphics[width=7.6cm]{figures/L68_t0500_off0on0_prj_NTsy-Xsoft.png}
\includegraphics[width=7.6cm]{figures/L68_t0300_off0on0_prj_NTsy-Xsoft.png}
\includegraphics[width=7.6cm]{figures/L68_t0500_off0on0_prj_NTic-Ghard.png}
\includegraphics[width=7.6cm]{figures/L68_t0300_off0on0_prj_NTic-Ghard.png}
\includegraphics[width=7.6cm]{figures/L68_t0500_off0on0_prj_NTpi-Ghard.png}
\includegraphics[width=7.6cm]{figures/L68_t0300_off0on0_prj_NTpi-Ghard.png}
\caption{Projected maps of the non-thermal emission. Top: X-ray synchrotron, middle: $\gamma$-ray inverse Compton, bottom: $\gamma$-ray pion decay. Left: TN SNR, right: CC SNR. Each plot compares the cases without (OFF) and with (ON) including particle back-reaction.}
\label{fig:maps_NT}
\end{figure}

\begin{figure}
\center
\includegraphics[width=7.6cm]{figures/L68_t0500_offon10_spc_map_NT.png}
\includegraphics[width=7.6cm]{figures/L68_t0300_offon10_spc_map_NT.png}
\caption{Integrated spectra of the non-thermal emission: X-ray synchrotron (red), inverse Compton (green), pion decay (blue). Left: TN SNR, right: CC SNR. Each plot compares the cases without (OFF, dashed lines) and with (ON, solid lines) including the back-reaction of particle pressure, as well as the cases without ($\zeta=1$, thin lines) or with ($\zeta=0$, thick lines) efficient amplification of the magnetic field.}
\label{fig:spectra_NT}
\end{figure}

Particles accelerated at the shock are transported in the downstream region, taking into account losses. Their non-thermal emission is computed with the code AURA, a rewrite of COSMICP \citep{Edmon2011a}. Projected maps are shown on Figure~\ref{fig:maps_NT} in three different bands corresponding to different emission mechanisms, from top to bottom: synchrotron emission from electrons in X-rays, inverse Compton emission from electrons in $\gamma$-rays, and pion decay emission from protons in $\gamma$-rays. The emission from electrons critically depends on the value of the magnetic field downstream of the shock. All the cases presented here were obtained allowing for efficient amplification of the magnetic field in the shock precursor, by a factor of about a hundred according to the model (this corresponds to the parameter $\zeta=0$ in \citealt{Ferrand2014b}).
In X-rays the synchrotron emission is concentrated in thin rims, as observed. In $\gamma$-rays the inverse Compton leptonic emission is also concentrated in thin rims, although this cannot be observed with current instruments, and no structures are visible inside the remnant. In contrast the hadronic emission peaks behind the forward shock and is more spread out; it also reveals the imprint of the Rayleigh-Taylor fingers in the interior of the SNR. These main effects are qualitatively similar in the TN and CC cases.

With current $\gamma$-ray instruments the most useful information is in spectral signatures. The broad-band emission from the SNR is shown on Figure~\ref{fig:spectra_NT}. As previously, these plots compare the cases with (``ON'') or without (``OFF'') including the back-reaction of the particle pressure, and they also compare the cases with ($\zeta=0$) or without ($\zeta=1$) efficient amplification of the magnetic field in the shocked region. The most interesting parts of the spectra are in the emission cut-offs. Contrary to the TN case, the X-ray cut-off may not be loss-limited and therefore depend on the value of~B. Similar to the TN case, at TeV energies, magnetic field amplification helps separate hadronic and leptonic emissions by boosting the former and reducing the latter.

\section{Conclusion}
\label{sec:conc}

As in our previous simulations, the impact of particle acceleration is dependent on the photon energy observed as well as on the magnetic field evolution assumed. In our current model for a CC SNR it appears to be similar for the particles' emission and less visible for the plasma emission. Note that we have not considered here acceleration at the reverse shock.
We emphasize that the broad-band emission from a SNR is the result of an integration over space and time of the history of the shock strength, particle acceleration, and magnetic field amplification, which makes it difficult to match observations with a one-zone model.

\small
\section*{Acknowledgments}
We thank Takaya Nozawa for providing us with nucleosynthesis data.
This work has been supported by NSERC and CFI in Canada.
The numerical simulations were performed on the Nuit computing cluster at the University of Manitoba.

\def\rm{A\&A}{\rm{A\&A}}
\def\rm{A\&AS}{\rm{A\&AS}}
\def\rm{ApJ}{\rm{ApJ}}
\def\rm{ApJ}{\rm{ApJ}}
\def\rm{MNRAS}{\rm{MNRAS}}
\bibliographystyle{aj}
\small


\section{Introduction}

Telling two inputs apart is one of the simplest computational problems one can imagine. As usual, the inputs are thought of as two  finite words $u,v$
over a finite alphabet $\Sigma$. Both $u$ and $v$ are known in advance; then one of them is fed to the algorithm which should decide whether this is $u$ or $v$. For a powerful computational model, such as the RAM model, the problem can be solved with constant space (in the length of the words): we need just one register to scan the input word until we reach a position in which $u$ and $v$ differ and look at the symbol at this position to decide whether we see $u$ or $v$ (a word can be supposed to end with a unique sentinel symbol). However, if the computational model is weak, like the finite automaton, the situation changes drastically, and distinguishing two words can no longer be done with constant space. The problem of determining the minimal size of a finite automaton separating two given words is NP-hard, as follows from some known algebraic results (see the discussion below). Moreover, even if we look at the maximal possible size of such automaton for words of a given length, very little is known about the asymptotics of this value. To make it more precise, we need some definitions.

We use the array notation $w=w[1..n]$ to represent finite words over finite alphabet $\Sigma$ when appropriate, and also the standard notions of factors, prefixes, suffixes. We write $|w|$ for the length of $w$ and $|w|_x$ for the number of occurrences of the letter $x$ in $w$. We treat a deterministic finite automaton (dfa) as a quadruple $\mathcal{A}=\{\Sigma,Q,\delta,s\}$, consisting of a finite alphabet, a finite set of states, a transition function, and an initial state. We write $q.w$ for the state of $\mathcal{A}$ obtained by reading the word $w\in\Sigma^*$ starting in the state $q\in Q$. The dfa $\mathcal{A}$ \emph{separates} words $u,v\in\Sigma^*$ if $s.u\ne s.v$.
(Equivalently, there exists a set $T\subset Q$ of accepting states such that exactly one of the words $u,v$ is accepted.) Let ${\sf Sep}(u,v)$ be the minimum number of states in a dfa separating $u$ and $v$.

Let $T_k$ denote the semigroup of all selfmaps of the set $\{1,\ldots, k\}$ under the composition of maps; it is called the \emph{full transformation semigroup} on $k$ elements. An \emph{identity} in a semigroup $T$ is a pair of words $(u,v)$ such that the images of $u$ and $v$ under any map $\Sigma\to T$ are equal as the elements of $T$. By the \emph{length} of the identity $(u,v)$ we mean the maximum of $|u|,|v|$. We write $u\equiv_k v$ to indicate the fact that $(u,v)$ is an identity in $T_k$. The \emph{transition semigroup} of a dfa $\mathcal{A}$ is a subsemigroup of $T_{|Q|}$ consisting of all maps $w: q\to q.w$, where $w\in\Sigma^*$. The following simple fact connects identities and separation:

\begin{fact} \label{sep_ide}
For any words $u,v$, the identity $u\equiv_k v$ holds if and only if ${\sf Sep}(u,v)>k$.
\end{fact}

Indeed, if $u\equiv_k v$, then this identity holds for the transition semigroup of any $k$-state dfa $\mathcal{A}$, implying $q.u=q.v$ in it for any state $q$. If otherwise $\rho(u)\ne\rho(v)$ in $T_k$ for some map $\rho: \Sigma\to T_k$, then the transformations $\rho(a)$, $a\in\Sigma$ can be used to define transitions in the $k$-state dfa separating $u$ and $v$.

It is known that the problem of checking whether $u\equiv_k v$ is coNP-complete for any $k>2$ \cite{AVG09,Kli12}. So by Fact~\ref{sep_ide}, it is NP-complete to check whether ${\sf Sep}(u,v)\le k$.

Let ${\sf Sep}(n)=\max_{u,v\in\Sigma^{\le n}}{\sf Sep}(u,v)$. The problem of describing the asymptotics of ${\sf Sep}(n)$ was first posed by Goralcik and Koubek \cite{GoKo86}. Due to Fact~\ref{sep_ide}, this problem is equivalent to finding the asymptotics of the minimum length of an identity in $T_k$. For the existing results on the identities in $T_k$ see, e.g., \cite{PSSSV94} and the references therein. Up to now the shortest known identity in $T_k$ has been the unary identity
\begin{equation} \label{unary}
x^{k-1}=x^{k-1+{\sf lcm}(k)},
\end{equation}
where ${\sf lcm}(k)$ denotes the least common multiple of the integers $1,\ldots,k$. Hence, ${\sf Sep}(n)>k$ for $n\ge {\sf lcm}(k)+k-1$. Since $\log({\sf lcm}(k))=k+o(k)$ by the Prime Number Theorem\footnote{In this paper, (a) the notation $\log$ stands for the natural logarithm; (b) the small-$o$-expressions can have any sign, so we always write '$+$' before them.}, this inequality can be rewritten as ${\sf Sep}(n)\ge \log n+o(\log(n))$. The logarithmic lower bound was presented already in \cite{GoKo86}, while the best known upper bound for ${\sf Sep}(n)$, obtained by Robson \cite{Rob89}, is $O(n^{2/5}\log^{3/5} n)$. Such a huge gap suggests that any of these bounds can be very loose. In this paper we present a new series of identities in $T_k$. These identities are shorter than \eqref{unary} whenever $k$ is a prime or a power of an odd prime. (More precisely, if $k=p^i$ for a prime $p$, then our identities are approximately $p/2$ times shorter than \eqref{unary}.) As far as we know, this is the first example of identities in $T_k$ that are shorter than \eqref{unary}.

There are several variations of the words separation problem; see, e.g., \cite{DESW11}. One variation requires a separating dfa to be \emph{permutational}, which means that every letter acts on the set of states as a permutation (i.e., $|Q.a|=|Q|$ for any $a\in\Sigma$). We denote the analog of the function ${\sf Sep}$ for permutational automata by ${\sf Sepp}$. Similar to Fact~\ref{sep_ide}, ${\sf Sepp}(u,v)>k$ if and only if the pair $(u,v)$ is an identity of the symmetric group $S_k$. Such group identities in semigroup signature are called \emph{positive} and denoted below by $u \cong_k v$. The best known upper bound for ${\sf Sepp}(n)$ also belongs to Robson \cite{Rob96} and is $O(n^{1/2})$. To get reasonable lower bounds on ${\sf Sepp}(n)$, one should find positive identities in $S_k$ which are shorter than the unary identity $x^{{\sf lcm}(k)}=1$. In general, the problem of finding short identities in finite symmetric groups has drawn some attention in the literature. The existence of an identity of length $O(e^{\sqrt{n\log n}})$ was proved in \cite{BoMc11} based on Landau's bound on the maximum order of a permutation \cite{Lan03}. Very recently, the existence of identities of length $O(e^{\log^4 n \log\log n})$ was established by Kozma and Thom \cite{KoTh16} based on a new result on the diameter of the Cayley graph of $S_k$ \cite{HeSe14}. However, the method of finding short identities in $S_k$ uses chains of iterated commutators and thus cannot be translated to produce short positive identities. So the problem of the existence of short positive identities remains open. Here we present some series of such identities, showing that ${\sf Sepp}(n)\ge \frac32\log n+o(\log n)$. Besides this, we present the results of computer-assisted studies for small $k$, providing, in particular, some exact values for the functions ${\sf Sep}$ and ${\sf Sepp}$.

The rest of the paper consists of two sections. In Section~\ref{s:semi} we present our results on ${\sf Sep}$ and the identities in $T_k$, while in Section~\ref{s:grou} we consider ${\sf Sepp}$ and positive identities in $S_k$, together with the connection between ${\sf Sep}$ and ${\sf Sepp}$.

\section{Identities in $T_k$} \label{s:semi}

An identity $(u,v)$ of a semigroup $T$ is \emph{reducible} if there is an identity $(u',v')$ of $T$ and a nonempty word $w$ such that either $u=wu', v=wv'$, or $u=u'w, v=v'w$; otherwise, the identity is said to be \emph{irreducible}. Since we are interested in short identities, we will consider only irreducible ones. As was already observed, the  shortest irreducible unary identity of any semigroup $T_k$ is  identity \eqref{unary}. The following easy fact is well known; a proof can be found in \cite{DESW11}.

\begin{fact} \label{binary}
For any pair of non-unary words $(u,v)$ such that $u\equiv_k v$ there is a pair $(u',v')$ of \emph{binary} words such that $|u'|=|u|$, $|v'|=|v|$, and $u'\equiv_k v'$.
\end{fact}

Hence, in the quest for short non-unary identities in $T_k$ we restrict ourselves to identities and dfa's over the binary alphabet $\{x,y\}$. The following necessary conditions for an identity in $T_k$ are known from \cite{GoKo86,Rob89,DESW11}.

\begin{fact} \label{necessary}
If $u\equiv_k v$, then the words $u,v$ have (i) the same prefix of length $k{-}2$, (ii) the same suffix of length $k{-}1$, and (iii) the same set of factors of length $k{-}1$\footnote{This is related, but not equivalent, to the $(k{-}1)$-\emph{Abelian equivalence} of $u$ and $v$. The notion of $k$-Abelian equivalence is popular in modern combinatorics of words; see, e.g., \cite{KSZ13} and the references therein.}.
\end{fact}

We illustrate this fact with Fig.~\ref{f:nesessary}, showing the dfa's separating $u$ and $v$ in the case of violation of the conditions (i)--(iii).

\begin{figure}[!htb]
\centerline{
\begin{tabular}{ll}
a)&\includegraphics[page=1]{ShortIdentities-pics.pdf}\\
b)&\includegraphics[page=2]{ShortIdentities-pics.pdf}\\
c)&\includegraphics[page=3]{ShortIdentities-pics.pdf}
\end{tabular}
}
\caption{\footnotesize Separation by prefixes, suffixes, and factors: (a) such a dfa with with $l{+}3$ states separates two words having the common prefix of length exactly $l$; (b) this example of the \emph{Aho-Corasick automaton} finishes its work in the rightmost state if and only if the input word has the suffix $xyyxxy$; such a dfa can be built for any suffix; (c) this variation of the previous automaton reaches the rightmost state if and only if the input word contains the factor $xyyxxy$; again, such a dfa can be built for any factor.}
\label{f:nesessary}
\end{figure}

Recall that, given a word $w\in\Sigma^*$ and a dfa $\mathcal{A}$, $w$ can be viewed as a transformation of the set of states of $\mathcal{A}$. The digraph of this transformation has one or more cycles (see an example in Fig.~\ref{f:trans}). Each such sycle is referred to as a \emph{$w$-cycle}.

\begin{figure}[!htb]
\centerline{\includegraphics[page=4]{ShortIdentities-pics.pdf}}
\caption{\footnotesize An example of the transformation of the set of states by a word.}
\label{f:trans}
\end{figure}

An identity $(u,v)$ is \emph{uniform} if $|u|=|v|$. First consider non-uniform identities.
\begin{proposition} \label{p:nonuniform}
A unique shortest binary non-uniform irreducible identity is
\begin{equation} \label{nonuniform}
x^{k-2}yx^{k-1}\equiv_k x^{k-2+{\sf lcm}(k)}yx^{k-1}
\end{equation}
\end{proposition}
\begin{proof}
First we use Fact~\ref{sep_ide} to check that \eqref{nonuniform} is an identity. Consider any binary dfa $\mathcal{A}=(\{x,y\},Q,\delta,s)$, $|Q|=k$, and prove that $\mathcal{A}$ does not separate the parts of  \eqref{nonuniform}. To separate them, $\mathcal{A}$ should separate $x^{k-2}$ from $x^{k-2+{\sf lcm}(k)}$. If the state $s.x^{k-2}\in Q$ belongs to an $x$-cycle, no separation is possible, because the length of this cycle divides ${\sf lcm}(k)$. Hence $s.x^{k-2}$ does not belong to an $x$-cycle. Then $Q=\{s, s.x, \ldots, s.x^{k-1}\}$ and the only $x$-cycle is the loop on the state $s.x^{k-1}$. Therefore, $x^{k-1}$ acts on $Q$ as a constant, implying that $\mathcal{A}$ is unable to separate the parts of \eqref{nonuniform}.

Now assume that $u\equiv_k v$ and $|u|<|v|\le {\sf lcm}(k)+2k-2$ (this number is the length of identity \eqref{nonuniform}). By Fact~\ref{sep_ide}, ${\sf Sep}(u,v)>k$. Let $|u|_x=l$, $|v|_x=l+m$, and w.l.o.g. $m>0$.
If $m$ is not divisible by ${\sf lcm}(k)$, then some $i\le k$ does not divide $m$. In this case $u$ and $v$ are separated by the $i$-state dfa in which $y$ is the identity map and $x$ is a cyclic permutation. Therefore the restriction on the length of $v$ implies $m={\sf lcm}(k)$. By the same argument, $|u|_y=|v|_y$. So $|v|-|u|={\sf lcm}(k)$, as well as in \eqref{nonuniform}. In addition, $u$ and $v$ satisfy the conditions (i)--(iii) of Fact~\ref{necessary}. Let $|u|<2k-2$. Then $u$ is completely covered by its prefix from (i) and its suffix from (ii). Then all $y$'s in $v$ occur in this prefix and/or suffix. Hence $v$ contains $x^{k-1}$; by (iii), so does $u$. Let $u=zx^{k-1}w$  for some words $z,w$. Since $u$ is short, $z$ (resp., $v$) is a part of the common prefix (resp., suffix) of $u$ and $v$. So $v=zx^{k-1+{\sf lcm}(k)}w$. But this means that the identity $u\equiv_k v$ is reducible to \eqref{unary}. This contradiction proves the assumption $|u|<2k-2$ false.

Finally, let $|u|=2k-2$, $z=u[1..k{-}2]$, $a=u[k{-}1]$, $w=u[k..2k{-}2]$. Then $u=zaw$ and $v=zv'w$ for some word $v'$ of length ${\sf lcm}(k)+1$. The equality $|u|_y=|v|_y$ implies that $v'$ contains exactly one $y$ if $a=y$ and $v'=x^{{\sf lcm}(k)+1}$ otherwise. Either way, $v'$ is long enough to contain the factor $x^{k-1}$, so $u$ contains it as well. If this factor is not a suffix of $u$, then $u\equiv_k v$ is reducible to \eqref{unary} as in the previous paragraph. Hence $w=x^{k-1}$. If $v$ has the prefix $za$, then this prefix contains all $y$'s in $v$; so $u=zax^{k-1}$, $v=zax^{{\sf lcm}(k)+k-1}$, and again our identity is reducible to \eqref{unary}. Therefore $u$ begins with $zy$ and $v$ begins with $zx$ (the opposite case is impossible since $|u|_y=|v|_y$). Note that $zy$ is a factor of $v$ by Fact~\ref{necessary}(iii). Since $v$ has a unique $y$ outside its prefix $z$ (it is in $v'$), this $y$ is preceded by $z$. So $v$ has two occurrences of $z$, and they together contain the same number of $y$'s as the prefix $z$ of $u$. This is possible only if $z=x^{k{-}2}$. Thus, each of $u=x^{k-2}yx^{k-1}$ and $v$ contain a single occurrence of $y$; say, $v[l]=y$. We have $l>k-1$, because $v$ begins with $zx=x^{k-1}$. If $l$ and $k-1$ are distinct modulo $i$ for some $i\le k$, then a dfa separating $u$ and $v$ is easy to construct: an $x$-cycle of length $i$ contains the initial vertex, and the $y$-edges from $s.x^{k-1}$ and $s.x^l$ lead to the same vertex of this cycle, so that the remaining $x$'s will be read to different vertices. Therefore, $l=k-1+{\sf lcm}(k)$, implying that the identity $u\equiv_k v$ coincides with \eqref{nonuniform}.
\end{proof}

Next we switch to uniform identities. An identity $(u,v)$ is \emph{balanced} if $|u|_a=|v|_a$ for any letter $a$.

\begin{proposition} \label{p:unbal}
A unique shortest binary uniform unbalanced identity is
\begin{equation} \label{unbal}
x^{k-1+{\sf lcm}(k)}y^{k-1}\equiv_k x^{k-1}y^{k-1+{\sf lcm}(k)}
\end{equation}
\end{proposition}
\begin{proof}
Since \eqref{unbal} is obtained by multiplying two copies of \eqref{unary}, it is obviously an identity. Now consider any uniform unbalanced identity $u\equiv_k v$ of length at most ${\sf lcm}(k)+2k-2$, which is the length of  \eqref{unbal}. Similar to the proof of Proposition~\ref{p:nonuniform}, we obtain that $|u|_x>|v|_x$ implies $|u|_x=|v|_x+{\sf lcm}(k)$ and $|v|_y=|u|_y+{\sf lcm}(k)$. Let $u=zu'w$, $v=zv'w$, where $z$ (resp. $w$) is the longest common prefix (resp., suffix) of $u$ and $v$. By Fact~\ref{necessary} we have $|z|\ge k-2$, $|w|\ge k-1$, and thus $|u'|\le {\sf lcm}(k)+1$. If $|u'|={\sf lcm}(k)+1$, we can assume $u'=x^{{\sf lcm}(k)+1}$, $v'=y^ixy^j$, where $i,j>0$ (if $u'$ contains fewer $x$'s, then $v'=y^{{\sf lcm}(k)+1}$, so we get a symmetric case). Then $x^{k-1}$ is a factor of $v$ by Fact~\ref{necessary}, implying $w=x^{k-1}$. Now all factors of $u$ of length $k-1$ end with $x$, which is not the case for $v$; again by Fact~\ref{necessary}, $u$ and $v$ cannot form an identity. Hence, $|u'|\le {\sf lcm}(k)$. So we have $u'=x^{{\sf lcm}(k)}$, $v'=y^{{\sf lcm}(k)}$. Since $x^{k-1}$ is a factor of $v$, $y^{k-1}$ is a factor of $u$, we immediately get the identity \eqref{unbal} up to renaming the letters.
\end{proof}

\begin{proposition}
Every $T_k$ satisfies the binary uniform balanced identity
\begin{equation} \label{bal}
x^{k-2+{\sf lcm}(k)}yx^{k-1}\equiv_k x^{k-2}yx^{k-1+{\sf lcm}(k)}
\end{equation}
\end{proposition}
\begin{proof}
The same argument as in Proposition~\ref{p:nonuniform} works: for any dfa with $k$ states either $s.x^{k-2}=s.x^{k-2+{\sf lcm}(k)}$ or $x^{k-1}$ is a constant map.
\end{proof}

The summary of the proved statements is as follows: the shortest non-unary unbalanced identities in the semigroup $T_k$ have exactly the same length ${\sf lcm}(k)+2k-2$ as some binary balanced identity, and are slightly longer than the unary identity of this semigroup. The question is whether there exist shorter balanced binary identities.

\begin{remark} \label{search4}
An exhaustive computer search reveals that identities \eqref{bal} are the shortest binary identities in the semigroups $T_k$ for $k\le 4$. For $k=5$, such a search is beyond capabilities of any computer. However, below we show that $T_5$ does have a shorter identity as well as infinitely many other semigroups $T_k$.
\end{remark}
\begin{theorem}\label{th:sem}
Semigroup $T_k$ satisfies the following identity of length $2{\sf lcm}(k-1)+6(k-1)$:
\begin{equation} \label{shortsem}
(xy)^{k-2+{\sf lcm}(k-1)}(yx)^k(xy)^{k-1} \equiv_k (xy)^{k-2}(yx)^k(xy)^{k-1+{\sf lcm}(k-1)}
\end{equation}
\end{theorem}
\begin{corollary}
If $k\ge 5$ is either a prime or an odd prime power, the semigroup $T_k$ satisfies an identity which is shorter than the unary identity \eqref{unary}.
\end{corollary}
\begin{proof}[Proof of Theorem~\ref{th:sem}]
Let us take a dfa $\mathcal{A}$ and consider the transformation $xy$ in it. If the state $s.(xy)^{k-2}$ does not belong to any $(xy)$-cycle, then we see, similar to Proposition~\ref{p:nonuniform}, that $(xy)^{k-1}$ is a constant map. So in this case $\mathcal{A}$ does not separate the sides of \eqref{shortsem}. Assume that $s.(xy)^{k-2}$ belongs to a $(xy)$-cycle of length $m$. If $m<k$, then all $(xy)$-cycles in $\mathcal{A}$ have length $<k$. Since $q.(xy)^{k-1}$ belongs to some $(xy)$-cycle for any state $q$ and the lengths of all $(xy)$-cycles divide ${\sf lcm}(k{-}1)$, both sides of \eqref{shortsem} move $s$ to the same state. Finally, let $m=k$. Then $xy$ is a permutation (namely, a cycle of length $k$), and $(xy)^k=1$. Hence $x,y$ and $yx$ are permutations, and clearly $(yx)^k=1$. Deleting $(yx)^k$ from both sides of \eqref{shortsem}, we get a graphical equality, so once again we see that $\mathcal{A}$ is not separating.
\end{proof}

\begin{conjecture} \label{c:short5}
Identity \eqref{shortsem} for $k=5$ is the shortest identity of $T_5$.
\end{conjecture}

This conjecture is partially verified by the computations described in the next section.

\section{Positive Identities in $S_k$} \label{s:grou}

The symmetric group $S_k$ satisfies the positive identity $x^{{\sf lcm}(k)}=1$ and its binary counterpart $x^{{\sf lcm}(k)}=y^{{\sf lcm}(k)}$. By the same argument, as the one used in Propositions~\ref{p:nonuniform} and~\ref{p:unbal}, these are the shortest unbalanced identities in $S_k$, so all shorter positive identities are balanced. It is known that the shortest positive identity in $S_3$ is $x^2y^2=y^2x^2$ (folklore). The shortest such identity in $S_4$ has length 11: $x^6y^2xy^2=y^2xy^2x^6$ \cite{DESW11}. We ran a computer search for the positive identities in $S_5$. Using an optimized search based on hash functions, we checked all balanced pairs $(u,v)$ of length at most 33, arriving at the following result.

\begin{proposition} \label{search5}
The shortest positive identities in $S_5$ have length 32. Up to symmetry, there are two such identities of length 32:
\begin{subequations}\label{32}
\begin{align}
(xy)(xyyx)^3(yxxy)^2(yx)(yxxy)^2&=(yxxy)^2(xy)(yxxy)^2(xyyx)^3(yx)\label{32:1}\\
(xy)^4(yx)^5(xy)^6(yx)&=(yx)(xy)^6(yx)^5(xy)^4\label{32:2}
\end{align}
\end{subequations}
Also, $S_5$ satisfies no irreducible positive identity of length 33.
\end{proposition}

Further, we checked the identities \eqref{32} in $S_6$.

\begin{proposition}
A unique, up to symmetry, shortest positive identity of $S_6$ is \eqref{32:2}.
\end{proposition}

Naturally enough, \eqref{32:2} is not an identity in $S_7$: these words are separated by a dfa in which $xy$ and $yx$ are different cycles of length 7. Hence, the function ${\sf Sepp}(n)$ never takes the value 6:

\begin{proposition}
One has ${\sf Sepp}(1)=2,{\sf Sepp}(2)={\sf Sepp}(3)=3,{\sf Sepp}(4)=\ldots={\sf Sepp}(10)=4,{\sf Sepp}(11)=\ldots={\sf Sepp}(31)=5,{\sf Sepp}(32)={\sf Sepp}(33)=7$.
\end{proposition}

\begin{proposition}
One has ${\sf Sep}(1)={\sf Sep}(2)=2,{\sf Sep}(3)=\ldots={\sf Sep}(7)=3,{\sf Sep}(8)=\ldots={\sf Sep}(14)=4,{\sf Sep}(15)=\ldots={\sf Sep}(40)=5,{\sf Sep}(48)>5$.
\end{proposition}
\begin{proof}
Since identity \eqref{bal} is longer than \eqref{unary}, Remark~\ref{search4} implies the values of ${\sf Sep}$ up to $n=14$ and the fact that ${\sf Sep}(15)>4$.

Let $u\equiv_5 v$. Then $u\cong_5 v$ and, by Fact~\ref{necessary}, $u$ and $v$ have a common prefix of length 3 and a common suffix of length 4. A direct check shows that the identities \eqref{32} cannot produce an identity in $T_5$ of length 39 or 40, so ${\sf Sep}(n)$ equals 5 for $n=15,\ldots,40$ by Proposition~\ref{search5}. The last result follows from  Theorem~\ref{th:sem}.
\end{proof}

Identities \eqref{32} possess interesting properties. First, in both cases $u,v\in\{xy,yx\}^*$. Second, \eqref{32:1} is a palindrome ($v$ is the reversal of $u$), while \eqref{32:2} is a palindrome if considered over $\{xy,yx\}$. Having observed this, we performed a further search for identities in $S_5$ up to length 40, examining all pairs $(u,v)$ such that either $u,v\in\{xy,yx\}^*$ or $v$ is the reversal of $u$. The search revealed eight more identities; they are presented in Table~\ref{idS5}. Note that some of them hold in $S_6$ but none holds in $S_7$.

\begin{table}[!htb]
\caption{More short positive identities in $S_5$.}
\label{idS5}
\tabcolsep=2pt
\begin{tabular}{|c|c|c|c|c|}
\hline
no.&$|u|$&Identity&Type&Hold in $S_6$?\\
\hline
1&34&$(xy)^{12}(yx)^5 = (yx)^5(xy)^{12}$&$\{xy,yx\}$-pal.&Yes\\
2&38&$(xy)^4(yx)^5(xy)^6(yx)(xy)^2(yx) = (yx)(xy)^2(yx)(xy)^6(yx)^5(xy)^4$&$\{xy,yx\}$-pal.&Yes\\
3&38&$(xy)^2(yx)^3(xyyx)^2(xy)^2(yxxy)^2(xyyx)^2 = $&&\\
&&$(yxxy)^2(xyyx)^2(xy)^2(yxxy)^2(yx)^3(xy)^2$&$\{xy,yx\}$-pal.&No\\
4&39&$(x^2y^2)^2y(x^2y^2)^4x^2y(x^2y^2)^2x^2y = yx^2(y^2x^2)^2yx^2(y^2x^2)^4y(y^2x^2)^2$&palindrome&No\\
5&39&$(x^2y^2)^3y(x^2y^2)^4x^2y(x^2y^2)x^2y = yx^2(y^2x^2)yx^2(y^2x^2)^4y(y^2x^2)^3$&palindrome&No\\
6&40&$(xyyx)^3(yxxy)^5(xyyx)^2 = (yxxy)^2(xyyx)^5(yxxy)^3$&$\{xy,yx\}$-pal.&No\\
7&40&$(xy)^6(yx)^{10}(xy)^4 = (yx)^4(xy)^{10}(yx)^6$&palindrome&Yes\\
8&40&$(x^2y^2)^3(y^2x^2)^5(x^2y^2)^2 = (y^2x^2)^2(x^2y^2)^5(y^2x^2)^3$&palindrome&No\\
\hline
\end{tabular}
\end{table}

Note that if $zuw\equiv_k zvw$, where $z$ (resp., $w$) is the longest common prefix (resp., suffix) of both sides, then $u\cong_k v$. So, the search for the identities in $T_5$ can be performed by iterating over the identities of $S_5$, using an exhaustive search for the candidates for $z$ and $w$. Such a search, based on the identities listed in \eqref{32} and Table~\ref{idS5}, gave us exactly one identity of $T_5$, namely, the identity \eqref{shortsem} for $k=5$, that has length 48. The result of this search supports  Conjecture~\ref{c:short5}.

\medskip
The analisys of the identities listed in \eqref{32} and Table~\ref{idS5} results in finding some general classes of identities in $S_k$. The simplest class, described in the following proposition, allows us to move up the lower bound on the function ${\sf Sepp}$ by a multiplicative constant.

\begin{proposition} \label{p:ab}
Let $a,b$ be such that the order of any element of $S_k$ divides either $a$ or $b$. Then
\begin{equation} \label{e:ab}
(xy)^a(yx)^b\cong_k (yx)^b(xy)^a\,.
\end{equation}
\end{proposition}
\begin{proof}
For any $x,y\in S_k$ the elements $(xy)$ and $(yx)$ have the same order. Then by the choice of $a,b$ either $(xy)^a=1$ or $(yx)^b=1$, implying the result.
\end{proof}

\begin{theorem} \label{t:ab}
The symmetric group $S_k$ satisfies a positive identity \eqref{e:ab} of length $e^{\frac 23 k+O(\frac{k}{\log k})}$.
\end{theorem}

\begin{corollary} \label{seplow}
${\sf Sepp}(n)\ge \frac 32 \log n + O\big(\frac{\log n}{\log\log n}\big)$.
\end{corollary}

\begin{proof}[Proof of Theorem~\ref{t:ab}]
Take a number $\alpha$, $0<\alpha<1$. Let $m=\lfloor \alpha k\rfloor$ and $P(m)$ be the product of all primes and prime powers from the range $\{m+1,\ldots, k\}$. Choose $a={\sf lcm}(m)$, $b={\sf lcm}(k-m)\cdot P(m)$, and apply Proposition~\ref{p:ab}. Indeed, the order of a permutation is the least common multiple of the length of its cycles; if a permutation has no cycle of length greater than $m$, than its order divides $a$; if such a cycle exists, than all other cycles are shorter than $k-m$, so the order divides $b$. Thus we get an identity of type \eqref{e:ab} with the $a$ and $b$ chosen\footnote{It is easy to see that one can take a smaller number as $b$, replacing $k{-}m$ with $k{-}m{-}1$ and the product of ${\sf lcm}$ and $P$ with their least common multiple. However, such an improvement does not change the asymptotics: its effect is covered by the $O$-term in the asymptotic formula.}. Since the length of this identity is $2(a+b)$, we want to find the value of $\alpha$ which delivers the minimum to $a{+}b$. Clearly, $\alpha\ge 1/2$, implying $m\ge k/2$. We use standard asymptotic formulas (see, e.g., \cite{BaSh96}) ${\sf lcm}(t)=e^{t+O(\frac t{\log t})}$ and $\pi(t)=\frac t{\log t}+ O(\frac t{\log^2 t})$, where $\pi(t)$ is the number of primes smaller than $t$. To estimate $P(m)$, we note that the product of $i$ factors equals their geometric mean taken to the $i$th power. Since all factors are between $m$ and $k$, their mean is $k/\beta$ for some $\beta$ between 1 and 2. To compute the number of factors, we can use the asymptotics for $\pi(m)$ (the number of prime powers smaller than $t$ is $O(\pi(\sqrt{t}))$ and thus does not affect the asymptotics). So we have
\begin{align*}
a=&e^{m+O(\frac m{\log m})}=e^{m+O(\frac k{\log k})},\\
b=&e^{k-m+O(\frac {k-m}{\log (k-m)})}\cdot \Big(\frac k{\beta}\Big)^{\frac k{\log k}-\frac m{\log m}+ O(\frac k{\log^2 k})}=e^{2k-2m+O(\frac k{\log k})}
\end{align*}
Thus the minimum of $a{+}b$ is reached at $\alpha=2/3$ so that $m=2k/3$, and this minimum is $e^{\frac 23 k+O(\frac{k}{\log k})}$, as required.
\end{proof}

A more involved class of equations is defined in the following proposition. The corresponding conditions can be easily extended to get identities with any even number of blocks of the form $(xy)^{a}$ and $(yx)^{b}$, but it is not clear if it is possible to build short identities of this type for any $k$.

\begin{proposition} \label{p:abcd}
Let $a,b,c,d$ be such that every order $q$ of an element of $S_k$ satisfies at least one the following conditions or their counterparts obtained by swapping $b$ with $c$, and $a$ with $d$: (i) $q$ divides both $a$ and $c$, (ii) $q$ divides both $a+c$ and $b$, (iii) $q$ divides $a$ and $b\equiv d \pmod q$. Then $S_k$ satisfies the identity
\begin{equation} \label{e:abcd}
(xy)^a(yx)^b(xy)^c(yx)^d\cong_k (yx)^d(xy)^c(yx)^b(xy)^a\,.
\end{equation}
\end{proposition}

\begin{proof}
We again use the fact that for any $x,y\in S_k$ the elements $(xy)$ and $(yx)$ have the same order. It is easy to see that each of the conditions (i)--(iii) forces some terms to vanish from both sides of \eqref{e:abcd} in a way that the remaining words are graphically equal.
\end{proof}

We use Propositions~\ref{p:ab} and~\ref{p:abcd} to run further computer experiments; in Table~\ref{idSk} we present the parameters of the shortest identities of types \eqref{e:ab} and \eqref{e:abcd}, obtained by exhaustive search, and compare their lengths to the length ${\sf lcm}(k)$ of the unary identity. Note that the parameters $a$ and $b$ of the shortest identity of type \eqref{e:ab} in most cases are equal to those chosen by the rule described in the proof of Theorem~\ref{t:ab}. For example, for $k=23$ we have $a={\sf lcm}(16)$, $b={\sf lcm}(6)\cdot17\cdot19\cdot23$. So it looks probable that no other way of choosing the pair $(a,b)$ can improve the result of Theorem~\ref{t:ab}. The identities of type \eqref{e:abcd} for small $k$ are shorter than the identities of type \eqref{e:ab}, but it is unclear whether this is true for all $k$.

\begin{table}[!htb]
\caption{Parameters of the shortest positive identities of types \eqref{e:ab},\eqref{e:abcd}.}
\label{idSk}
\arraycolsep=2pt
$$
\begin{array}{|c||c|c|c|c|c||c|c|c||c|}
\hline
&\multicolumn{5}{|c||}{\text{Identities of type \eqref{e:abcd}}}&\multicolumn{3}{|c||}{\text{Identities of type \eqref{e:ab}}}&\\
\hline
k&a&b&c&d&\text{Len}&a&b&\text{Len}&{\sf lcm}(k)\\
\hline
5,6&1&6&5&4&32&12&5&34&60\\
7&2&14&12&10&76&60&7&134&420\\
8&23&60&7&24&228&60&56&232&840\\
9&18&60&42&24&288&180&56&472&2520\\
10&18&60&42&24&288&120&126&492&2520\\
11&48&180&132&84&888&840&198&2076&27720\\
12&24&222&420&198&1728&840&198&2076&27720\\
13&&&&&&2520&286&5612&360360\\
14&&&&&&2520&858&6756&360360\\
15&&&&&&2520&1716&8472&360360\\
16&&&&&&5040&8580&27240&720720\\
17&&&&&&27720&10608&76656&12252240\\
18&&&&&&55440&13260&137400&12252240\\
19&&&&&&55440&251940&614760&232792560\\
20&&&&&&360360&15504&751728&232792560\\
21&&&&&&360360&77520&875760&232792560\\
22&&&&&&360360&77520&875760&232792560\\
23&&&&&&720720&445740&2332920&5354228880\\
\hline
\end{array}
$$
\end{table}

\section{Conclusion}

In this paper, we did the very first step in improving the lower bound on words separation (or, from the other point of view, improving the upper bound on the shortest identity in full transformation semigroups and the shortest positive identity in symmetric groups). Apart from the experimentally obtained values of the separation functions ${\sf Sep}$ and ${\sf Sepp}$ for small arguments, we obtained two asymptotic results:
\begin{itemize}
\item the logarithmic lower bound for ${\sf Sep}(n)$ is improved by an additive sublogarithmic term for infinitely many values of $n$;
\item the logarithmic lower bound for ${\sf Sepp}(n)$ is improved by a factor of $3/2$.
\end{itemize}
The obvious next step should be an attempt to improve the function ${\sf Sep}$ by some factor and prove a superlogarithmic lower bound for ${\sf Sepp}$. Our general impression is that both such improvements are possible. On the other hand, we are not so optimistic about the existence of a superlogarithmic lower bound for ${\sf Sep}$.

\bibliographystyle{plain}


\section{Introduction}
This paper addresses two linguistic phenomena: translation and non-native language. Our main goal is to investigate the similarities and differences between these two phenomena, and contrast them with native language. In particular, we are interested in the reasons for the differences between translations and originals, on one hand, and native and non-native language, on the other. Do they reflect ``universal'' principles, or are they dependent on the source/native language?

Much research in translation studies indicates that translated texts
have unique characteristics. Translated texts (in any language)
constitute a sub-language of the target language, sometimes referred
to as \textit{translationese} \citep{Gellerstam:1986}.
The unique characteristics of translationese have been
traditionally classified into two categories: properties that stem
from \emph{interference} of the source language \citep{Toury:1979},
and universal traits resulting from the translation process itself,
independently of the specific source and target languages
\citep{Baker:1993,Toury:1995}.  The latter so-called \emph{translation
  universals} have triggered a continuous debate among translation studies
  researchers \citep{Universals:2004,house:2008,becher:2010}.

Similarly, over half a century of research on second language
acquisition (SLA) established the presence of \textit{cross-linguistic influences} (CLI)
in non-native utterances \citep{jarvis2008crosslinguistic}.
CLI is a cover term proposed by \citet{kellerman1986crosslinguistic} to denote various
phenomena that stem from language contact situations such as transfer,
interference, avoidance, borrowing, etc.\footnote{To avoid terminological conflicts,
we shall henceforth use CLI to denote any influence of one linguistic system over another,
w.r.t. both translations and non-native productions.}
In addition, universal traits resulting from the learning process itself have been noticed regardless of the native language, \text{L1}.%
\footnote{For simplicity, we will use \emph{\text{L1}} to refer
  both to the native language of a speaker and to the source language
  of a translated text. We use \emph{target language} to refer to
  second and translation languages (English in this paper).}
For example, similar developmental sequences have been observed for negation, question formation,
and other sentence structures in English \citep{dulay1974natural, odlin1989language} for both Chinese and Spanish natives.
Phenomena such as overgeneralization, strategies of learning
\citep{Selinker1972}, psychological factors \citep{ellis1985understanding},
and cultural distance \citep{Giles82} are also influential in the acquisition process.

There are clear similarities between translations and non-native
language: both are affected by the simultaneous presence of (at least) two linguistic systems, which
may result in a higher cognitive load \citep{shlesinger2003effects}. The presence of the L1
may also cause similar CLI effects on the target
language.

On the other hand, there are reasons to believe that translationese and
non-native language should differ from each other.
Translations are produced by
\emph{native} speakers of the target language.
Non-natives, in
contrast, arguably never attain native-like abilities
\citep{coppieters87,johnson1991critical}, however this hypothesis is strongly debated in the SLA community
\citep{birdsong92,lardiere2006ultimate}.

Our goal in this work is to investigate three language \emph{varieties}:
 the language of native speakers (N),
 the language of advanced, highly fluent non-native speakers (NN),
 and translationese (T). We use the term \emph{constrained language} to
refer to the latter two varieties.
We propose a unified computational umbrella for exploring
two related areas of research on bilingualism:
translation studies and second language acquisition.
 Specifically, we put forward three main
hypotheses: %
\begin{inparaenum}[(1)]
\item The three language varieties have unique characteristics that make them
  easily distinguishable.
\item Non-native language and translations are closer to each other
  than either of them is to native language.
\item Some of these characteristics are dependent on the specific
  \text{L1}, but many are not, and may reflect unified principles that
 similarly affect translations and non-native language.
\end{inparaenum}

We test these hypotheses using several corpus-based
computational methods. We use supervised and unsupervised
classification (Section~\ref{sec:classification}) to show that the
three language varieties are easily distinguishable. In particular, we show that
native and advanced non-native productions can be accurately separated. More pertinently, we
demonstrate that non-native utterances and translations comprise two distinct
linguistic systems.

In Section~\ref{sec:similarities}, we use statistical analysis to explore
the unique properties of each language variety. We show that the two varieties of
constrained language are much closer to
each other than they are to native language:
they exhibit poorer lexical richness, a tendency to
use more frequent words, a different distribution of idiomatic
expressions and pronouns, and excessive use of cohesive devices.
This is an unexpected finding, given that both natives and translators (in
contrast to non-natives) produce texts in their mother tongue.

Finally, in Section~\ref{sec:interference} we use language modeling to
show that translations and non-native language exhibit similar
statistical properties that clearly reflect cross-linguistic influences: experiments with
distinct language families reveal salient ties between the two varieties
of constrained language.

The main contribution of this work is thus theoretical:
it sheds light on some fundamental questions regarding
bilingualism, and we expect it to motivate and
drive future research in both SLA and translation
studies. Moreover, a better understanding of constrained language
may also have some practical import, as we briefly
mention in the following section.

\section{Related work}
\label{sec:related-work}

Corpus-based investigation of translationese has been a prolific field
of recent research, laying out an empirical foundation for the
theoretically motivated hypotheses on the characteristics of
translationese. More specifically, identification of translated texts
by means of automatic classification shed light on the manifestation
of translation universals and cross-linguistic influences as markers of translated texts
\citep{Baroni2006, Halteren08, gaspariBernardini, Kurokawa:etal:2009,
  koppel-ordan:2011:ACL-HLT2011, Ilisei:2012, vered:noam:shuly,
  TACL618, nisioi2015b}, while \cite{gaspariBernardini} introduced a dataset for investigation
  of potential common traits between translations and non-native texts.
Such studies prove to be important for
the development of parallel corpora \citep{resnik:smith:03}, the improvement
in quality of plagiarism detection \citep{potthast2011cross}, language modeling,
and statistical machine translation \citep{lembersky-ordan-wintner:CL2012,lembersky-ordan-wintner:CL2014}.

Computational approaches also proved
beneficial for theoretical research in second language
acquisition \citep{jarvis2008crosslinguistic}.
Numerous studies address linguistic processes attributed
to SLA, including automatic detection of highly competent non-native
writers \citep{tomokiyo2001you, bergsma2012stylometric},
identification of the mother tongue of English learners \citep{koppel2005determining,
  tetreault-blanchard-cahill:2013:BEA, tsvetkov-EtAl:2013:BEA8,
  nisioi2015a} and typology-driven error prediction in learners'
speech \citep{BerzakRK15}.
These studies are instrumental for language teaching and
student evaluation \citep{smith2001learner}, and can
improve NLP applications
such as authorship profiling \citep{estival2007author} or grammatical
error correction \citep{chodorow2010utility}.
Most of these studies utilize
techniques that are motivated by the same abstract principles
associated with L1 influences on the target language.

To the best of our knowledge, our work is the first to address both
translations and non-native language under a unifying computational framework, and
in particular to compare both with native language.

\section{Methodology and experimental setup}
\label{sec:exp-setup-class}

\subsection{Dataset}
Our dataset\footnote{The dataset is available at
\url{http://nlp.unibuc.ro/resources.html}}
is based on the highly homogeneous corpus of the European Parliament Proceedings
\citep{Koehn05Europarl}. Note that the proceedings are produced as follows:
\begin{inparaenum}[(1)]
\item the utterances of the speakers are transcribed;
\item the transcriptions are sent to the speaker who may suggest
  minimal editing without changing the content;
\item the edited version is then translated by native speakers. Note
  in particular that the texts are \emph{not} a product of
  simultaneous interpretation.
\end{inparaenum}

In this work we utilize a subset of Europarl in which each sentence is
manually annotated with speaker information, including
the EU state represented and the original language in which the sentence was uttered \citep{nnt-corpus}.
The texts in the corpus are uniform in terms of style, respecting the
European Parliament's formal standards. Translations are produced by native English speakers and all
non-native utterances are selected from members not representing UK or Ireland.
Europarl N consists of texts delivered by native speakers from England.

Table \ref{tbl:corpus-stats} depicts statistics of the dataset.%
\footnote{Appendix A provides details on the distribution of NN and T texts by various L1s.}
In contrast to other learner corpora such as ICLE \citep{icle}, EFCAMDAT \citep{efcamdat} or TOEFL-11 \citep{toefl}, this corpus
contains translations, native, and non-native English of high proficiency speakers.
Members of the European Parliament have the right to use any of the EU's 24 official
languages when speaking in Parliament, and the fact that some of them
prefer to use English suggests a high degree of
confidence in their language skills.

\begin{table}[hbt]
\centering
\resizebox{\columnwidth}{!}{
\begin{tabular}{l|rrr}
\textbf{sub-corpus} & \textbf{sentences} & \textbf{tokens} & \textbf{types} \\ \hline
native (N)  & 60,182 & 1,589,215 & 28,004 \\
non-native (NN) & 29,734 & 783,742 & 18,419 \\
translated (T) & 738,597 & 22,309,296 & 71,144 \\ \hline
total & 828,513 & 24,682,253 & 117,567
\end{tabular}
}%
\caption{Europarl corpus statistics: native, non-native and translated texts.}
\label{tbl:corpus-stats}
\end{table}

\subsection{Preprocessing}
All datasets were split by sentence, cleaned (text lowercased,
punctuation and empty lines removed) and tokenized using the Stanford
tools \citep{manning-EtAl:2014:P14-5}. For the classification
experiments we randomly shuffled the sentences within each language variety to
prevent interference of other artifacts (e.g., authorship, topic) into the
classification procedure. We divided the data into chunks of
approximately 2,000 tokens, respecting sentence boundaries, and
normalized the values of lexical features by the number of tokens in
each chunk. For classification we used Platt's sequential minimal
optimization algorithm \citep{Keerthi2001,weka} to train support vector
machine classifiers with the default linear kernel.

In all the experiments we used (the maximal) equal amount of data from
each category, thus we always randomly down-sampled the datasets in
order to have a comparable number of examples in each class;
specifically, 354 chunks were used for each language variety: N, NN and T.

\subsection{Features}
\label{sec:features}
The first feature set we utilized for the classification tasks
comprises \emph{function words} (FW), probably the most popular choice
ever since \citet{mostWallace} used it successfully for the Federalist
Papers. Function words proved to be suitable features for multiple
reasons:%
\begin{inparaenum}[(1)]
\item they abstract away from contents and are therefore less biased by topic;
\item their frequency is so high that by and large they are assumed to
  be selected unconsciously by authors;
\item although not easily interpretable, they are assumed to reflect
  grammar, and therefore facilitate the study of how structures are
  carried over from one language to another.
\end{inparaenum}
We used the list of approximately 400 function words provided in
\citet{koppel-ordan:2011:ACL-HLT2011}.

A more informative way to capture (admittedly shallow) syntax is to
use \emph{part-of-speech (POS) trigrams}. Triplets such as PP
(personal pronoun) + VHZ (\textsl{have}, 3sg present) + VBN
(\textsl{be}, past participle) reflect a complex tense form,
represented distinctively across languages. In Europarl, for example,
this triplet is highly frequent in translations from Finnish and
Danish and much rarer in translations from Portuguese and Greek. In
this work we used the top-3,000 most frequent POS trigrams in each
corpus.

We also used \emph{positional token frequency}
\citep{Grieve:2007}. The feature is defined as counts of words
occupying the first, second, third, penultimate and last positions in
a sentence. The motivation behind this feature is that sentences open
and close differently across languages, and it should be expected that
these opening and closing devices will be transferred from \text{L1}\ if
they do not violate the grammaticality of the target
language. Positional tokens were previously used for translationese
identification \citep{vered:noam:shuly} and for native language
detection \citep{nisioi2015a}.

Translations are assumed to exhibit \emph{explicitation}: the tendency
to render implicit utterances in the source text more explicit in the
translation product. For example, causality, even though not always
explicitly expressed in the source, is expressed in the target by the
introduction of cohesive markers such as \textsl{because}, \textsl{due
  to}, etc. \citep{Blum-Kulka:1986}. Similarly,
\citet{hinkel2001matters} conducted a comparative analysis of
\emph{explicit cohesive devices} in academic texts by non-native
English students, and found that cohesive markers are distributed
differently in non-native English productions, compared to their
native counterparts. To study this phenomenon, we used the set of over
100 cohesive markers introduced in \citet{hinkel2001matters}.

\section{The status of constrained language}
\label{sec:classification}
To establish the unique nature of each language variety in our dataset,
we perform multiple pairwise binary classifications between N, NN,
and T, as well as three-way classifications.
Table~\ref{tbl:classification} reports the results; the
figures reflect average ten-fold cross-validation accuracy (the best
result in each column is boldfaced).

In line with previous works
(see Section~\ref{sec:related-work}), classification of N--T, as well
as N--NN, yields excellent results with most features and feature
combinations. NN--T appears to be easily
distinguishable as well; specifically, FW+POS-trigrams combination
with/without positional tokens yields 99.57\% accuracy. The word
\textsl{maybe} is among the most discriminative feature for NN vs.\ T,
being overused in NN, as opposed to \textsl{perhaps}, which exhibits a
much higher frequency in T; this may indicate a certain degree of
formality, typical of translated texts \citep{Olohan:2003}. The words
\textsl{or}, \textsl{which} and \textsl{too} are considerably more
frequent in T, implying higher sentence complexity. This trait is also
reflected by shorter NN sentences, compared to T: the average sentence
length in Europarl is 26 tokens for NN vs.\ 30 for T. Certain
decisiveness devices (\textsl{sure}, \textsl{very}) are underused in
T, in accordance with \cite{Toury:1995}'s law of standardization
\citep{vanderauwera1985dutch}. The three-way classification yields
excellent results as well; the highest accuracy is obtained using
FW+positional tokens with/without POS-trigrams.

\begin{table}[hbt]
\centering
\resizebox{\columnwidth}{!}{
\begin{tabular}{@{}l|ccc|c}
feature / dataset   & N-NN & N-T & NN-T & 3-way\\
\hline
FW                  & 98.72 & 98.72 & 96.89 & 96.60 \\
POS (trigrams)      & 97.45 & 98.02 & 97.45 & 95.10 \\
pos. tok            & 99.01 & 99.01 & 98.30 & 98.11 \\
cohesive markers    & 85.59 & 87.14 & 82.06 & 74.19 \\
\hline
FW+POS              & 99.43 & 99.57 & \textbf{99.57} & 99.34 \\
FW+pos. tok         & 99.71 & 99.85 & 98.30 & \textbf{99.52} \\
POS+pos. tok        & 99.57 & 99.57 & 99.01 & 99.15 \\
FW+POS+pos. tok     & \textbf{99.85} & \textbf{99.85} & \textbf{99.57} & \textbf{99.52} \\
\end{tabular}
}
\caption{Pairwise and three-way classification results of N, NN and T texts.}
\label{tbl:classification}
\end{table}

A careful inspection of the results in Table~\ref{tbl:classification}
reveals that NN--T classification is a slightly yet systematically
harder task than N--T or N--NN; this implies that NN and T texts are
more similar to each other than either of them is to N.

To emphasize this last point, we analyze the separability of the three
language varieties by applying unsupervised classification. We perform \emph{bisecting KMeans}
clustering procedure previously used for unsupervised identification of translationese by \citet{TACL618}.
Clustering of N, NN and T using function words into three clusters
yields high accuracy, above 90\%. For the sake of clusters' visualization in a bidimensional plane,
we applied principal component analysis for dimensionality reduction.

\begin{figure}[hbt]
\vspace*{0.27em}
\centering
\begin{tabular}{cc}
\hspace{-0.75em}
\includegraphics[width=3.85cm]{clusters-3.png} &
 \hspace{-1.25em}
\includegraphics[width=3.85cm]{clusters-2.png}
\end{tabular}
\caption{Clustering of N, NN and T into three (a) and two (b) clusters using function words. Clusters'
centroids in (a) are marked by black circles; square sign stands for instances clustered wrongly.}
\label{fig:clustering}
\end{figure}

The results are depicted in Figure~\ref{fig:clustering}~(a). Evidently, NN and T exhibit higher
mutual proximity than either of them with N. Fixing the number of expected clusters
to~2 further highlights this observation, as demonstrated in
Figure~\ref{fig:clustering}~(b): both NN and T instances were assigned
to a single cluster, distinctively separable from the N cluster.

We conclude that the three language varieties (N, NN, and T) constitute three
different, distinguishable ontological categories, characterized by
various lexical, syntactic and grammatical properties; in particular,
the two varieties of constrained language (NN and T) represent two
distinct linguistic systems.
Nevertheless, we anticipate NN and T to share more common tendencies and regularities,
when compared to N.
In the following sections, we put this hypothesis to the test.

\section{\text{L1}-independent similarities}
\label{sec:similarities}

In this section we address \text{L1}-independent similarities between NN
and T, distinguishing them from N. We focus on characteristics which
are theoretically motivated by translation studies and which are
considered to be \text{L1}-independent, i.e., unrelated to cross-linguistic influences.
We hypothesize that linguistic devices over- or under-represented in
translation would behave similarly in highly competent non-native
productions, compared to native texts.

To test this hypothesis, we realized various linguistic phenomena as
properties that can be easily computed from N, NN and T texts. We
refer to the computed characteristics as \emph{metrics}.  Our
hypothesis is that NN metric values will be similar to T, and that
both will differ from N. We used equally-sized texts of 780K tokens
for N, NN and T; the exact computation is specified for each metric.

For the sake of visualization, the three values of each metric (for N, NN and T)
were zero-one scaled by total-sum
normalization. Figure~\ref{fig:universal} graphically depicts the
normalized metric values. We now describe and motivate each metric.
We analyze the results in Section~\ref{sec:universal-analysis} and
establish their statistical significance in
Section~\ref{sec:significance}.

\paragraph{Lexical richness}
Translated texts tend to exhibit less lexical diversity
\citep{Al-Shabab:1996}. \citet{Blum-Kulka:1986} suggested that
translated texts \textit{make do with less words}, which is reflected by
their lower type-to-token ratio (TTR) compared to that of native
productions. We computed the TTR metric by dividing the number of
unique (lemmatized) tokens by the total number of tokens.

\paragraph{Mean word rank}
\citet{Halverson:2003} claims that translators use more prototypical
language, i.e., \textit{they regress to the mean}
\citep{Shlesinger:1989}. We, therefore, hypothesize that rarer words are
used more often in native texts than in non-native productions and
translationese. To compute this metric we used a BNC-based ranked list
of 50K English words\footnote{\url{https://www.kilgarriff.co.uk} we used the list extracted from both
spoken and written text.},
excluding the list of function words (see
Section~\ref{sec:features}). The metric value was calculated by
averaging the rank of all tokens in a text; tokens that do not appear
in the list of 50K were excluded.

\begin{figure*}[hbt]
\centering
\begin{tikzpicture}[font=\small]
  \centering
  \begin{axis}[
        ybar, axis on top,
        height=4.75cm, width=15.5cm,
        bar width=0.6cm,
        yminorgrids, tick align=inside,

        ymin=0.290, ymax=0.400,
        axis x line*=bottom,
        axis y line*=right,
        y axis line style={opacity=0},
        tickwidth=0pt,
        enlarge x limits=true,
        legend style={
            at={(0.5,-0.2)},
            anchor=north,
            legend columns=-1,
            /tikz/every even column/.append style={column sep=0.5cm}
        },
        ylabel={zero-one scale normalized value},
        xticklabels={lexical richness$^*$, mean word rank$^*$, pronouns$^*$, collocation (types)$^*$,
        transitions},
        xticklabel style={anchor=base,yshift=-\baselineskip},
        xtick=data,
    ]

    \addplot [draw=none, fill=black!20] coordinates {
    (0,0.356)(1,0.334)(2,0.393)(3,0.382)(4,0.303)};

    \addplot [draw=none, fill=black!80] coordinates {
    (0,0.332)(1,0.332)(2,0.310)(3,0.311)(4,0.377)};

    \addplot [draw=none, fill=black!50] coordinates {
    (0,0.312)(1,0.332)(2,0.296)(3,0.307)(4,0.320)};
     \legend{native (N), translated (T), non-native (NN)}
  \end{axis}
  \end{tikzpicture}
\label{fig:universal-metrics}
\caption{Metric values in N, NN and T. Tree-way differences are significant in all metric categories and
``*'' indicates metrics with higher pairwise similarity of NN and T, compared individually to N.}
\label{fig:universal}
\end{figure*}

\paragraph{Collocations}
Collocations are distributed differently in translations and in
originals \citep{Toury:1980,Kenny:2001}. Common and frequent
collocations are used almost subconsciously by native speakers, but
will be subjected to a more careful choice by translators and,
presumably, by fluent non-native speakers
\citep{erman2014nativelike}. For example, the phrase \textsl{make
  sure} appears twice more often in native Europarl texts than in NN,
and five times more than in T; \textsl{bear in mind} has almost double
frequency in N, compared to NN and T. Expressions such as: \textsl{bring
  forward}, \textsl{figure out}, \textsl{in light of}, \textsl{food
  chain} and \textsl{red tape} appear dozens of times in N, as opposed
to zero occurrences in NN and T Europarl texts. This metric is defined
by computing the frequency of idiomatic expressions\footnote{Idioms
  were taken from
  \url{https://en.wiktionary.org/wiki/Category:English_idioms}. The
  list was minimally cleaned up.} in terms of types.

\paragraph{Cohesive markers}
Translations were proven to employ cohesion intensively
\citep{Blum-Kulka:1986,Overas:1990,koppel-ordan:2011:ACL-HLT2011}. Non-native
texts tend to use cohesive markers differently as well:
\emph{sentence transitions}, the major cohesion
category, was shown to be overused by non-native speakers regardless
of their native language \citep{hinkel2001matters}. The metric is
defined as the frequency of sentence transitions in the three
language varieties.

Qualitative comparison of various markers between NN and T
productions, compared to N in the Europarl texts, highlights this
phenomenon: \textsl{in addition} is twice as frequent in NN and T than
in N; \textsl{according}, \textsl{at the same time} and \textsl{thus}
occur three times more frequently in NN and T, compared to N;
\textsl{moreover} is used four times more frequently; and \textsl{to
  conclude} is almost six times more frequent.

\paragraph{Personal pronouns}
We expect both non-native speakers and translators to spell out
entities (both nouns and proper nouns) more frequently, as a means of
\emph{explicitation} \citep{olohan2002leave}, thus leading to
under-use of personal pronouns, in contrast to native texts.
As an example, \textsl{his} and \textsl{she} are twice more frequent in N than in NN and T.

We define this metric as the frequency of (all) personal and possessive pronouns used in the three language varieties.
The over-use of personal pronouns in N utterances, is indeed balanced out by lower frequency
of proper and regular nouns in these texts, compared to T and NN.\footnote{Normalized frequencies of nouns and proper nouns are
0.323, 0.331 and 0.345 for N, T, and NN, respectively.}

\subsection{Analysis}
\label{sec:universal-analysis}
Evidently (see Figure~\ref{fig:universal}), translationese and
non-native productions exhibit a consistent pattern in both datasets,
compared to native texts: NN and T systematically demonstrate lower
metric values than N for all characteristics (except sentence
transitions, where both NN and T expectedly share a higher value).
All metrics except mean word rank exhibit substantial (sometimes dramatic) differences between N, on the one hand,
and NN and T, on the other, thus corroborating our hypothesis.
Mean word rank exhibits a more moderate variability in the
three language varieties, yielding near identical value in NN and T;
yet, it shows excessive usage in N.

The differences between metric values are statistically significant
for all metrics (Section~\ref{sec:significance}). Moreover, in all
cases (except transitions), the difference between NN and T metrics is
significantly lower than the difference between either of them and N,
implying a higher proximity of NN and T distributions, compared
individually to N. This finding further emphasizes the common
tendencies between NN and T.

As shown in Figure~\ref{fig:universal}, NN and T are systematically
and significantly different from N. Additionally, we can see that T is
consistently positioned between N and NN (except for sentence transitions),
implying that translations produced
by native speakers tend to resemble native utterances to a higher degree
than non-native productions.

\subsection{Statistical significance}
\label{sec:significance}
Inspired by the results depicted in Figure~\ref{fig:universal}, we now put to test two statistical hypotheses:
\begin{inparaenum}[(1)]
\item N, NN and T productions do not represent identical underlying distributions, i.e., at least one  pair is distributed differently; and consequently,
\item NN and T productions exhibit higher similarity (in terms of \emph{distance}) than either of them with N.
\end{inparaenum}
We test these hypotheses by applying the \emph{bootstrapping} statistical analysis.

Bootstrapping is a statistical technique involving random re-sampling
(with replacement) from the original sample; it is often used to
assign a measure of accuracy (e.g., a confidence interval) to an
estimate. Specifically, let $\corpus_\textrm{N}$, $\corpus_\textrm{NN}$ and $\corpus_\textrm{T}$
denote native, non-native and translated sub-corpora of equal size
(780K tokens). Let $\corpus_\textrm{ALL}$ denote the concatenation of all three
sub-corpora, resulting in a total of 2,340M tokens. We further denote
a function computing a metric $m$ by $f^m$; when applied to
$C$, its value is $\fmetric(\corpus)$.  The sum of pairwise distances
between the three individual dataset metrics is denoted by
$D_\textrm{total}$:

\setlength\abovedisplayskip{0pt}
\begin{equation*}
\begin{split}
&D_\textrm{total} = |f^m(\corpus_\textrm{N})-f^m(\corpus_\textrm{NN})| + \\
&|f^m(\corpus_\textrm{N})-f^m(\corpus_\textrm{T})| + |f^m(\corpus_\textrm{NN})-f^m(\corpus_\textrm{T})|
\end{split}
\end{equation*}
\setlength\abovedisplayskip{0pt}

High values of $D_\textrm{total}$ indicate a difference between the three
language varieties. To examine whether the observed $D_\textrm{total}$ is high beyond
chance level, we use the bootstrap approach, and repeat the following
process 1,000 times:\footnote{This sample size is proven sufficient by
  the highly significant results (very low \textit{p}-value).} we
sample $\corpus_\textrm{ALL}$ with replacement (at sentence granularity),
generating in the j-th iteration equal-sized samples
$\widehat\corpus_\textrm{N}^{j}$, $\widehat\corpus_\textrm{NN}^{j}$,
$\widehat\corpus_\textrm{T}^{j}$. The corresponding distance estimate,
therefore, is:

\setlength\abovedisplayskip{0pt}
\begin{equation*}
\begin{split}
&\widehatD_\textrm{total}^{j} = |f^m(\widehat\corpus_\textrm{N}^{j})-f^m(\widehat\corpus_\textrm{NN}^{j})| + \\
&|f^m(\widehat\corpus_\textrm{N}^{j})-f^m(\widehat\corpus_\textrm{T}^{j})| + |f^m(\widehat\corpus_\textrm{NN}^{j})-f^m(\widehat\corpus_\textrm{T}^{j})|
\end{split}
\end{equation*}
\setlength\abovedisplayskip{0pt}

We repeat random re-sampling and computation of
$\widehatD_\textrm{total}^{j}$ 1,000 times, and estimate the \textit{p}-value
of $\widehatD_\textrm{total}$ by calculation of its percentile within the
series of (sorted) $\widehatD_\textrm{total}^{j}$ values, where
$j \in (1,\ldots,1000)$. In all our experiments the original distance
$D_\textrm{total}$ exceeds the maximum estimate in the series of
$\widehatD_\textrm{total}^{j}$, implying highly significant difference, with
\textit{p}-value\textless$0.001$ for all metrics.

In order to stress this outcome even further, we now test whether (the
constrained) NN and T exhibit higher pairwise similarity, as opposed
to N. We achieve this by assessment of the distance between NN and T
productions, compared to the distance between N and its closest
production (again, in terms of distance): either NN or T. We sample
$\corpus_\textrm{N}$, $\corpus_\textrm{NN}$ and $\corpus_\textrm{T}$ (with replacement)
separately, constructing $\widetilde\corpus_\textrm{N}$, $\widetilde\corpus_\textrm{NN}$
and $\widetilde\corpus_\textrm{T}$, respectively, and define the following
distance function:

\setlength\abovedisplayskip{0pt}
\begin{equation*}
\widetildeD_\textrm{dif}^{j}\!=\!|f^m(\widetilde\corpus_\textrm{N}^{j})\!-\!f^m(\widetildeC_{K}^{j})|\!-
\!|f^m(\widetilde\corpus_\textrm{NN}^{j})\!-\!f^m(\widetilde\corpus_\textrm{T}^{j})|
\end{equation*}
\setlength\abovedisplayskip{0pt}

\noindent where
\setlength\abovedisplayskip{0pt}
\begin{equation*}
K\!=\!
\begin{cases}
\mbox{NN} &\mbox{if}\;|f^m(\corpus_\textrm{N})-f^m(\corpus_\textrm{NN})|< \\
& |f^m(\corpus_\textrm{N})-f^m(\corpus_\textrm{T})| \\
\mbox{T} &\mbox{otherwise}
\end{cases}
\end{equation*}
\setlength\abovedisplayskip{0pt}

We repeat re-sampling and computation of $\widetildeD_\textrm{dif}^{j}$
1,000 times for each metric value in both datasets and sort the
results. The end points of the 95\% confidence interval are defined by
estimate values with 2.5\% deviation from the minimum
(\emph{min-end-point}) and the maximum (\emph{max-end-point})
estimates. We assess the \textit{p}-value of the test by inspecting
the estimate underlying the min-end-point; specifically, in case the
min-end-point is greater than $0$, we consider
\textit{p}\textless$0.05$. Metric categories exhibiting higher NN-T
similarity than either N-NN or N-T are marked with ``*'' in
Figure~\ref{fig:universal}.

\section{\text{L1}-related similarities}
\label{sec:interference}
We hypothesize that both varieties of constrained language exhibit similar
(lexical, grammatical, and structural) patterns due to the influence of
\text{L1}\ over the target language. Consequently, we anticipate that
non-native productions of speakers of a certain native language
(\text{L1}) will be closer to translations from \text{L1}\ than to
translations from other languages.

Limited by the amount of text available for each individual language,
we set out to test this hypothesis by inspection of two language
\emph{families}, Germanic and Romance. Specifically, the Germanic
family consists of NN texts delivered by speakers from Austria,
Germany, Netherlands and Sweden; and the Romance family includes NN
speakers from Portugal, Italy, Spain, France and Romania. The
respective T families comprise translations from Germanic and Romance
originals, corresponding to the same
countries. Table~\ref{tbl:families-stats} provides details on the
datasets.

\begin{table}[hbt]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{l|rrr}
 & \textbf{sentences} & \textbf{tokens} & \textbf{types} \\ \hline
Germanic NN & 5,384 & 132,880 & 7,841 \\
Germanic T & 269,222 & 7,145,930 & 43,931 \\ \hline
Romance NN & 6,384 & 180,416 & 9,838 \\
Romance T & 307,296 & 9,846,215 & 49,925 \\
\end{tabular}
}
\caption{Europarl Germanic and Romance families: NN and T.}
\label{tbl:families-stats}
\end{table}

We estimate \text{L1}-related traces in the two varieties of constrained
language by the fitness of a translationese-based \emph{language
  model} (LM) to utterances of non-native speakers from the same
language family. Attempting to trace structural and grammatical,
rather than content similarities, we compile five-gram \emph{POS}
language models from Germanic and Romance translationese (GerT and
RomT, respectively).\footnote{For building LMs we used the closed vocabulary of Penn Treebank POS tag set.}
We examine the prediction power of these models
on non-native productions of speakers with Germanic and Romance native
languages (GerNN and RomNN), hypothesizing that an LM compiled from
Germanic translationese will better predict non-native productions of
a Germanic speaker and vice versa. The fitness of a language model to
a set of sentences is estimated in terms of \emph{perplexity}
\citep{JelMerBahBak}.

For building and estimating language models we used the KenLM toolkit
\citep{heafield2011kenlm}, employing modified Kneser-Ney smoothing
without pruning. Compilation of language-family-specific models was
done using 7M tokens of Germanic and Romance translationese each; the
test data consisted of 5350 sentences of Germanic and Romance
non-native productions. Consequently, for perplexity experiments with
individual languages we utilized 500 sentences from each language. We
excluded OOVs from all perplexity computations.

Table~\ref{tbl:ppl-family} reports the results. Prediction of GerNN by
the GerT language model yields a slightly lower perplexity (i.e., a
better prediction) than prediction by RomT. Similarly, RomNN is much
better predicted by RomT than by GerT. These differences are
statistically significant: we divided the NN texts into 50 chunks of
100 sentences each, and computed perplexity values by the two LMs for
each chunk. Significance was then computed by a two-tailed paired
t-test, yielding p-values of 0.015 for GerNN and 6e-22 for RomNN.

\begin{table}[hbt]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{l|cccl|c}
LM / NN & GerNN & & & LM / NN & RomNN \\
\hline
GerT    & 8.77 & & & GerT  & 8.64 \\
RomT    & 8.79 & & & RomT  & 8.43 \\
\end{tabular} %
}
\caption{Perplexity: fitness of Germanic and Romance translationese LMs to Germanic and Romance NN test sets.}
\label{tbl:ppl-family}
\end{table}

As a further corroboration of the above result, we computed the
perplexity of the GerT and RomT language models with respect to the
language of NN speakers, this time distinguishing speakers by their
country of origin. We used the same language models and non-native
test chunks of 500 sentences each. Inspired by the outcome of the
previous experiment, we expect that NN productions by Germanic
speakers will be better predicted by GerT LM, and vice
versa. Figure~\ref{fig:ppl-language} presents a scatter plot with the
results.

\begin{figure}[hbt]
\centering
\hspace{-1em}
\begin{tikzpicture}
\begin{axis}[
    axis lines=middle,

    xlabel=Perplexity by GerT,
    ylabel=Perplexity by RomT,
    ylabel near ticks,
    xlabel near ticks,
    x label style={font=\footnotesize},
    y label style={font=\footnotesize},
    xmin=11.4, xmax=12.85,
    ymin=11.4, ymax=12.85,
    xtick=\empty, ytick=\empty

]
\addplot [
    mark=*,
    only marks,
    nodes near coords,
    mark options={fill=white},
    point meta=explicit symbolic,
    visualization depends on=\thisrow{alignment} \as \alignment,
    every node near coord/.style={anchor=\alignment,font=\footnotesize}
    ] table [meta index=2] {
x           y           label          alignment
11.6746	    11.9368     Austria         -90
12.2198	    12.3045     Netherlands     -90
11.8418	    11.8993     Sweden          50
11.9694	    11.9351     Germany         -90
};
\addplot [
    mark=*,
    only marks,
    nodes near coords,
    mark options={fill=black},
    point meta=explicit symbolic,
    visualization depends on=\thisrow{alignment} \as \alignment,
    every node near coord/.style={anchor=\alignment,font=\footnotesize}
    ] table [meta index=2] {
x           y           label          alignment
12.1342	    12.0846     France          -180
11.9573	    11.8859     Italy           -180
11.7082	    11.5707     Romania         -180
12.8399	    12.3847     Spain           50
11.5786	    11.4424     Portugal        -180
};
\addplot [domain=11.4:12.75,dashed] {x};
\end{axis}
\end{tikzpicture}
\vspace{-0.5em}
\caption{Perplexity of the GerT and RomT language models with respect to non-native utterances of speakers from various countries.}
\label{fig:ppl-language}
\end{figure}

A clear pattern, evident from the plot, reveals that all English texts
with underlying Romance native languages (under the diagonal) are
better predicted (i.e., obtain lower perplexity) by the RomT LM.
All Germanic native languages (except German), on the other
hand, are better predicted by the GerT LM. This finding
further supports the hypothesis that non-native productions and
translationese tend to exhibit similar \text{L1}-related traits.

\section{Conclusion}
\label{sec:conclusion}
We presented a unified computational approach for studying constrained
language, where many of the features were theoretically motivated. We
demonstrated that while translations and non-native productions are two
distinct language varieties, they share similarities that stem from lower
lexical richness, more careful choice of idiomatic expressions and
pronouns, and (presumably) subconscious excessive usage of
explicitation cohesive devices. More dramatically, the language
modeling experiments reveal salient ties between the native language
of non-native speakers and the source language of translationese,
highlighting the unified \text{L1}-related traces of \text{L1}\ in both
scenarios.  Our findings are intriguing: native speakers and
translators, in contrast to non-native speakers, use their native
language, yet translation seems to gravitate towards non-native
language use.

The main contribution of this work is empirical, establishing the
connection between these types of language production. While we
believe that these common tendencies are not incidental, more research
is needed in order to establish a theoretical explanation for the
empirical findings, presumably (at least partially) on the basis of
the cognitive load resulting from the simultaneous presence of two
linguistic systems. We are interested in expanding the
preliminary results of this work: we intend to replicate the
experiments with more languages and more domains, investigate
additional varieties of constrained language and employ more complex
lexical, syntactic and discourse features. We also plan to investigate
how the results vary when limited to specific \text{L1} s.

\section*{Acknowledgments}
This research was supported by the Israeli Ministry of Science and Technology.
We are immensely grateful to Yuval Nov for much advice and helpful suggestions.
We are also indebted to Roy Bar-Haim, Anca Bucur, Liviu P. Dinu, and Yosi Mass for their support and guidance
during the early stages of this work, and we thank our anonymous reviewers for their valuable insights.

\bibliographystyle{acl_natbib}