Design a notion of automata for graphs.

The source page states the original problem together with its recorded qualifications and progress updates as follows.

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 [Raoult, 1993] on label rewriting.)

Recorded progress.

A well motivated notion of ``graph acceptor'' has been presented in [Raoult, 1993].

Recorded update.

Submitted by Bruno Courcelle on 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: [Raoult, 1993]