[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #72

Originator: Jean-Claude Raoult
Date: June 1993

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

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.

Remark

See [Cou94, Cou97].

Comment sent by Bruno Courcelle

Date: 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: [Cou94, Cou97, CK02]

References

[CK02]

Bruno Courcelle and Teodor Knapik. The evaluation of first-order substitution is monadic second-order compatible. Theoretical Computer Science, 281(1–2):177–206, June 2002.

[Cou94]

Bruno Courcelle. Monadic-second order graph transductions: A survey. Theoretical Computer Science, 126:53–75, 1994.

[Cou97]

Bruno Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. In G. Rozenberg, editor, Handbook of graph grammars and computing by graph transformations, vol. 1: Foundations, chapter 5, pages 313–400. World Scientific, New-Jersey, London, 1997.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]