\batchmode
\documentclass{article}
\makeatletter
\usepackage{a4wide}

\sloppy

\title{Transducers from Rewrite Rules with Backreferences}
\author{\begin{tabular}{cc}
Dale Gerdemann & Gertjan van Noord\\
University of Tuebingen & Groningen University\\
Kl. Wilhelmstr. 113 & PO Box 716\\
D-72074 Tuebingen & NL 9700 AS Groningen\\
{\tt dg@sfs.nphil.uni-tuebingen.de} & {\tt vannoord@let.rug.nl}
\end{tabular}
}
\usepackage[dvips]{color}
\pagecolor[gray]{.7}


\makeatletter
\count@=\the\catcode`\_ \catcode`\_=8 
\newenvironment{tex2html_wrap}{}{} \catcode`\_=\count@
\makeatother
\let\mathon=$
\let\mathoff=$
\ifx\AtBeginDocument\undefined \newcommand{\AtBeginDocument}[1]{}\fi
\newbox\sizebox
\setlength{\hoffset}{0pt}\setlength{\voffset}{0pt}
\addtolength{\textheight}{\footskip}\setlength{\footskip}{0pt}
\addtolength{\textheight}{\topmargin}\setlength{\topmargin}{0pt}
\addtolength{\textheight}{\headheight}\setlength{\headheight}{0pt}
\addtolength{\textheight}{\headsep}\setlength{\headsep}{0pt}
\setlength{\textwidth}{451pt}
\newwrite\lthtmlwrite
\makeatletter
\let\realnormalsize=\normalsize
\global\topskip=2sp
\def\preveqno{}\let\real@float=\@float \let\realend@float=\end@float
\def\@float{\let\@savefreelist\@freelist\real@float}
\def\end@float{\realend@float\global\let\@freelist\@savefreelist}
\let\real@dbflt=\@dbflt \let\end@dblfloat=\end@float
\let\@largefloatcheck=\relax
\def\@dbflt{\let\@savefreelist\@freelist\real@dbflt}
\def\adjustnormalsize{\def\normalsize{\mathsurround=0pt \realnormalsize
 \parindent=0pt\abovedisplayskip=0pt\belowdisplayskip=0pt}\normalsize}%
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newcommand\lthtmlhboxmathA{\adjustnormalsize\setbox\sizebox=\hbox\bgroup}%
\newcommand\lthtmlvboxmathA{\adjustnormalsize\setbox\sizebox=\vbox\bgroup%
 \let\ifinner=\iffalse }%
\newcommand\lthtmlboxmathZ{\@next\next\@currlist{}{\def\next{\voidb@x}}%
 \expandafter\box\next\egroup}%
\newcommand\lthtmlmathtype[1]{\def\lthtmlmathenv{#1}}%
\newcommand\lthtmllogmath{\lthtmltypeout{l2hSize %
:\lthtmlmathenv:\the\ht\sizebox::\the\dp\sizebox::\the\wd\sizebox.\preveqno}}%
\newcommand\lthtmlfigureA[1]{\let\@savefreelist\@freelist
       \lthtmlmathtype{#1}\lthtmlvboxmathA}%
\newcommand\lthtmlfigureZ{\lthtmlboxmathZ\lthtmllogmath\copy\sizebox
       \global\let\@freelist\@savefreelist}%
\newcommand\lthtmldisplayA[1]{\lthtmlmathtype{#1}\lthtmlvboxmathA}%
\newcommand\lthtmldisplayB[1]{\edef\preveqno{(\theequation)}%
  \lthtmldisplayA{#1}\let\@eqnnum\relax}%
\newcommand\lthtmldisplayZ{\lthtmlboxmathZ\lthtmllogmath\lthtmlsetmath}%
\newcommand\lthtmlinlinemathA[1]{\lthtmlmathtype{#1}\lthtmlhboxmathA  \vrule height1.5ex width0pt }%
\newcommand\lthtmlinlineA[1]{\lthtmlmathtype{#1}\lthtmlhboxmathA}%
\newcommand\lthtmlinlineZ{\egroup\expandafter\ifdim\dp\sizebox>0pt %
  \expandafter\centerinlinemath\fi\lthtmllogmath\lthtmlsetinline}
\newcommand\lthtmlinlinemathZ{\egroup\expandafter\ifdim\dp\sizebox>0pt %
  \expandafter\centerinlinemath\fi\lthtmllogmath\lthtmlsetmath}
\def\lthtmlsetinline{\hbox{\vrule width.1em\vtop{\vbox{%
  \kern.1em\copy\sizebox}\ifdim\dp\sizebox>0pt\kern.1em\else\kern.3pt\fi
  \ifdim\hsize>\wd\sizebox \hrule depth1pt\fi}}}
\def\lthtmlsetmath{\hbox{\vrule width.1em\vtop{\vbox{%
  \kern.1em\kern0.8 pt\hbox{\hglue.17em\copy\sizebox\hglue0.8 pt}}\kern.3pt%
  \ifdim\dp\sizebox>0pt\kern.1em\fi \kern0.8 pt%
  \ifdim\hsize>\wd\sizebox \hrule depth1pt\fi}}}
\def\centerinlinemath{%\dimen1=\ht\sizebox
  \dimen1=\ifdim\ht\sizebox<\dp\sizebox \dp\sizebox\else\ht\sizebox\fi
  \advance\dimen1by.5pt \vrule width0pt height\dimen1 depth\dimen1 
 \dp\sizebox=\dimen1\ht\sizebox=\dimen1\relax}

\def\lthtmlcheckvsize{\ifdim\ht\sizebox<\vsize\expandafter\vfill
  \else\expandafter\vss\fi}%
\makeatletter \tracingstats = 1 
\providecommand{\Mu}{\textrm{M}}
\providecommand{\Nu}{\textrm{N}}
\providecommand{\Chi}{\textrm{X}}
\providecommand{\Zeta}{\textrm{Z}}
\providecommand{\Alpha}{\textrm{A}}
\providecommand{\Omicron}{\textrm{O}}
\providecommand{\omicron}{\textrm{o}}
\providecommand{\Rho}{\textrm{R}}
\providecommand{\Tau}{\textrm{T}}
\providecommand{\Epsilon}{\textrm{E}}
\providecommand{\Eta}{\textrm{H}}
\providecommand{\Beta}{\textrm{B}}
\providecommand{\Iota}{\textrm{J}}
\providecommand{\Kappa}{\textrm{K}}


\begin{document}
\pagestyle{empty}\thispagestyle{empty}%
\lthtmltypeout{latex2htmlLength hsize=\the\hsize}%
\lthtmltypeout{latex2htmlLength vsize=\the\vsize}%
\lthtmltypeout{latex2htmlLength hoffset=\the\hoffset}%
\lthtmltypeout{latex2htmlLength voffset=\the\voffset}%
\lthtmltypeout{latex2htmlLength topmargin=\the\topmargin}%
\lthtmltypeout{latex2htmlLength topskip=\the\topskip}%
\lthtmltypeout{latex2htmlLength headheight=\the\headheight}%
\lthtmltypeout{latex2htmlLength headsep=\the\headsep}%
\lthtmltypeout{latex2htmlLength parskip=\the\parskip}%
\lthtmltypeout{latex2htmlLength oddsidemargin=\the\oddsidemargin}%
\makeatletter
\if@twoside\lthtmltypeout{latex2htmlLength evensidemargin=\the\evensidemargin}%
\else\lthtmltypeout{latex2htmlLength evensidemargin=\the\oddsidemargin}\fi%
\makeatother
\stepcounter{section}
{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_indisplay1204}%
$\displaystyle \Rightarrow$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_indisplay1205}%
$\displaystyle \lambda$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_indisplay1206}%
$\displaystyle \rho$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath27}%
\begin{displaymath}
x\Rightarrow  T(x)/\lambda\mbox{\_\_}\rho
\end{displaymath}%
\lthtmldisplayZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1209}%
$ \lambda$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1211}%
$ \rho$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_indisplay1221}%
$\displaystyle \langle$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_indisplay1222}%
$\displaystyle \rangle$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath420}%
\begin{displaymath}x\Rightarrow T_{acr}(x)/\langle
\mbox{abbr}\rangle\mbox{\_\_}\langle /\mbox{abbr}\rangle\end{displaymath}%
\lthtmldisplayZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1229}%
$ \langle$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1231}%
$ \rangle$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_indisplay1235}%
$\displaystyle \phi$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_indisplay1237}%
$\displaystyle \psi$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath43}%
\begin{displaymath}
\phi\Rightarrow  \psi/\lambda\mbox{\_\_}\rho
\end{displaymath}%
\lthtmldisplayZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1241}%
$ \phi$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1243}%
$ \psi$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath47}%
\begin{displaymath}
x_1 x_2\ldots x_n \Rightarrow  T_1(x_1) T_2(x_2) \ldots
T_n(x_n)/\lambda\mbox{\_\_}\rho
\end{displaymath}%
\lthtmldisplayZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath51}%
\begin{displaymath}x\Rightarrow  (T_1 \cdot T_2 \cdot \ldots \cdot T_n)(x)/\lambda\mbox{\_\_}\rho
\end{displaymath}%
\lthtmldisplayZ
\hfill\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1294}%
$ \Sigma$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1299}%
$ \rightarrow$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline476}%
$x \rightarrow T(x)/\lambda\mbox{\_\_}\rho$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1303}%
$ \Rightarrow$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline478}%
$x_1 \ldots x_n \Rightarrow  T_1(x_1) \ldots
T_n(x_n)/\lambda\mbox{\_\_}\rho$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figurestar161}%
\begin{figure*}\begin{tex2html_preform}\begin{verbatim}macro(replace(T,Left,Right),
            non_markers             % introduce 0 after every symbol
                o                   % (a b c => a 0 b 0 c 0).
             r(Right)               % introduce rb2 before any string
                o                   % in Right.
            f(domain(T))            % introduce lb2 before any string in
                o                   % domain(T) followed by rb2.
       left_to_right(domain(T))     % lb2 ... rb2 around domain(T) optionally
                o                   % replaced by lb1 ... rb1
       longest_match(domain(T))     % filter out non-longest matches marked
                o                   % in previous step.
          aux_replace(T)            % perform T's transduction on regions marked
                o                   % off by b1's.
             l1(Left)               % ensure that lb1 must be preceded
                o                   % by a string in Left.
             l2(Left)               % ensure that lb2 must not occur preceded
                o                   % by a string in Left.
         inverse(non_markers)).     % remove the auxiliary 0's.\end{verbatim}\end{tex2html_preform}
\par
\end{figure*}%
\lthtmlfigureZ
\hfill\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figurestar249}%
\begin{figure*}\begin{tex2html_preform}\begin{verbatim}macro(lm_concat(Ts),mark_boundaries(Domains) o ConcatTs):-
   domains(Ts,Domains), concatT(Ts,ConcatTs).

domains([],[]).
domains([F|R0],[domain(F)|R]):- domains(R0,R).

concatT([],[]).
concatT([T|Ts], [inverse(non_markers) o T,lb1 x []|Rest]):- concatT(Ts,Rest).

%% macro(mark_boundaries(L),Exp): This is the central component of lm_concat. For our
%% "toplological" example we will have:
%% mark_boundaries([domain([{[t,o],[t,o,p]},[]: #]),
%%                  domain([{o,[p,o,l,o]},[]: #]),
%%                  domain({[g,i,c,a,l],[o^,l,o,g,i,c,a,l]})])
%% which simplifies to:
%% mark_boundaries([{[t,o],[t,o,p]}, {o,[p,o,l,o]}, {[g,i,c,a,l],[o^,l,o,g,i,c,a,l]}]).
%% Then by macro expansion, we get:
%% [{[t,o],[t,o,p]} o non_markers,[]x lb1,
%%  {o,[p,o,l,o]} o non_markers,[]x lb1,
%%  {[g,i,c,a,l],[o^,l,o,g,i,c,a,l]} o non_markers,[]x lb1]
%%              o
%% % Filter 1: {[t,o],[t,o,p]} gets longest match
%% ~ [ignx_1(non_markers({[t,o],[t,o,p]}),lb1),
%%    ign(non_markers({o,[p,o,l,o]}),lb1),
%%    ign(non_markers({[g,i,c,a,l],[o^,l,o,g,i,c,a,l]}),lb1)]
%%                   o
%% % Filter 2: {o,[p,o,l,o]} gets longest match
%% ~ [non_markers({[t,o],[t,o,p]}),lb1,
%%    ignx_1(non_markers({o,[p,o,l,o]}),lb1),
%%    ign(non_markers({[g,i,c,a,l],[o^,l,o,g,i,c,a,l]}),lb1)] 

macro(mark_boundaries(L),Exp):-
   boundaries(L,Exp0), % guess boundary positions 
   greed(L,Exp0,Exp).  % filter non-longest matches

boundaries([],[]).
boundaries([F|R0],[F o non_markers, [] x lb1 |R]):- boundaries(R0,R).

greed(L,Composed0,Composed) :-
   aux_greed(L,[],Filters), compose_list(Filters,Composed0,Composed).

aux_greed([H|T],Front,Filters):- aux_greed(T,H,Front,Filters,_CurrentFilter).

aux_greed([],F,_,[],[ign(non_markers(F),lb1)]).
aux_greed([H|R0],F,Front,[~L1|R],[ign(non_markers(F),lb1)|R1]) :-
   append(Front,[ignx_1(non_markers(F),lb1)|R1],L1),
   append(Front,[non_markers(F),lb1],NewFront),
   aux_greed(R0,H,NewFront,R,R1).

%% ignore at least one instance of E2 except at end
macro(ignx_1(E1,E2), range(E1 o [[? *,[] x E2]+,? +])).

compose_list([],SoFar,SoFar).
compose_list([F|R],SoFar,Composed):- compose_list(R,(SoFar o F),Composed).\end{verbatim}\end{tex2html_preform}

\end{figure*}%
\lthtmlfigureZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_indisplay1313}%
$\displaystyle \mbox{[t o $\mid$ t o p $\mid$\space o $\mid$\space p o l o ] $\rightarrow$\space ... \#}$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline498}%
$]/\lambda \mbox{\_\_}\rho$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline500}%
$\mbox{\it xy} \Rightarrow [_{NP}\, \mbox{\it RepairDet(x)
  RepairN(y)}\,]/\lambda \mbox{\_\_}\rho$%
\lthtmlinlinemathZ
\hfill\lthtmlcheckvsize\clearpage}


\end{document}