\documentclass{rtaloop}
\rtalabel{fintely-branching}


\begin{document}
\begin{problem}{Jean-Claude Raoult}{}{June 1993}

\begin{abstract}
  Give a definition of graph transduction that extends rational word
  transductions.
\end{abstract}
Graph rewritings, like term or word rewritings, are usually finitely
branching. There are relations that are not finitely branching, yet
satisfy good properties: rational transductions of words,
tree-transductions.  A good definition of graph transduction, that
extends rational word transductions is still lacking.

\begin{remark}
  See \cite{Courcelle:tcs94,Courcelle:HB97}.
\end{remark}

\begin{submitted}{Bruno Courcelle}{Mon, 31 Jan 2005 10:20:21 +0100}
  My notion of monadic second-order transduction of graphs, hypergraphs and
  relational structures is in my opinion the equivalent of tree and word
  transductions. However, if a graph is given with a tree-structure, then a
  transducer can be based on this tree: it can produce an algebraic expression
  defining, after evaluation, the desired object graph, hypergraph etc...
                                                                              
  References:  \cite{Courcelle:tcs94,Courcelle:HB97,CourcelleKnapik02tcs} 

\end{submitted}

\end{problem}
\end{document}