Give a definition of graph transduction that extends rational word transductions.

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

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.

Recorded progress.

See [Raoult, 1993].

Recorded update.

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