\documentclass{rtaloop}
\rtalabel{trees}
\begin{document}
\begin{solvedproblem}{Participants at Unif Val d'Ajol}{}{April 1991}
\begin{abstract}
What is the complexity of the first-order theory of trees?
\end{abstract}
The complexity of the theory of finite trees when there are finitely many
symbols is known to be PSPACE-hard \cite{M88:lics}. Is it in PSPACE? The same
question applies to infinite trees.
\begin{remark}
The problem is non-elementary \cite{Vorobyov:TreeComplexity96}.
\end{remark}
\end{solvedproblem}
\end{document}