[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #70

Originator: Jean-Claude Raoult
Date: June 1993

Summary: Design a notion of automata for graphs.

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 [LMSar] on label rewriting.)

Remark

A well motivated notion of “graph acceptor” has been presented in [Tho97].

Comment sent by Bruno Courcelle

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

References

[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.
[LMSar]
Igor Litovski, Yves Métivier, and Eric Sopena. Definitions and comparisons of local computations on graphs. Mathematical Systems Theory, to appear. Available as internal report 91-43 of LaBRI, University of Bordeaux 1.
[Tho97]
Wolfgang Thomas. Automata theory on trres and partial orders. In Theory and Practice of Software Development, volume 1214 of Lecture Notes in Computer Science, pages 20–38, 1997.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]