[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |
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.)
A well motivated notion of “graph acceptor” has been presented in [Tho97].
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]
[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |