\documentclass{rtaloop}
\rtalabel{graphs}


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

\begin{abstract}
Design a notion of \emph{automata} for graphs.
\end{abstract}

There exist finite automata for words, trees, and dags. No really good
comparable notion is available
for graphs. (Perhaps there is one akin to the ideas in
\cite{LMS:mst} on label rewriting.)

\begin{remark}
A well motivated notion of ``graph acceptor'' has been presented
in \cite{Thomas:tapsoft97}.
\end{remark}

\begin{submitted}{Bruno Courcelle}{Mon, 31 Jan 2005 10:20:21 +0100}
  In my opinion, there cannot exist graph automata yielding satisfactory
  results. There can only exist ad hoc definitions working for very special
  cases, giving no general theory. However, there is a well established notion
  of recognizability based on finite congruences. The reason why there cannot
  exist graph automata is that the "structure" of the graph, on which automata
  computations must be based (like on trees or words) is not given. Because
  graphs have far more complex structure than trees. There is no good notion
  of dag automaton. Of course, one can propose tools and claim "I have the
  good notion of an automaton".

  References: \cite{Courcelle:HB97}
\end{submitted}

\end{problem}
\end{document}