Logical Description of Context-free Graph Languages

摘要

A graph languageLis in the class C-edNCE of context-free edNCE graph languages if and only ifL=f(T) wherefis a partial function on graphs that can be defined in monadic second-order logic andTis 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.