\documentclass{rtaloop}
\rtalabel{reduction-graph}


\begin{document}
\begin{problem}{M. Venturini-Zilli}{}{December 1991}

\begin{abstract}
Which ordinals correspond to reduction graphs in the $\lambda$-calculus?
\end{abstract}

Some reduction graphs in $\lambda$-calculus \cite{V84:tcs} are isomorphic to
ordinals. For example, the reduction graph of $(\lambda x.y)((\lambda
z.zzz)(\lambda z.zzz))$ is isomorphic to $\omega + 1$. Which ordinals appear
in this way as reduction graphs? It is known that all ordinals less than
$\epsilon_0$ can be so represented.

\end{problem}
\end{document}
