|
Abstract : |
Abstract. A graph language L is in the class C-edNCE of context-free edNCE graph languages if and only if L = f(T) where f is a function on graphs that can be defined in monadic second-order logic and T is the set of all trees over some ranked alphabet. This logical characterization implies a large number of closure and decidability properties of the context-free edNCE graph languages. Rather than context-free graph grammars we use regular path descriptions to define graph languages. 1, |
