Logical Description of Contex-Free Graph Languages
Logical Description of Contex-Free Graph Languages
复制标题
无上下文图语言的逻辑描述
DOI：
10.1006/jcss.1997.1510
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
V. V. Oostrom
中科院分区：
文献类型：
--
作者：
J. Engelfriet;V. V. Oostrom
图语言L属于上下文无关edNCE图语言的类C-edNCE当且仅当L= f（T），其中f是可以用一元二阶逻辑定义的图上的部分函数，T是某个排序字母表上的所有树的集合。这种逻辑特征意味着大量的封闭性和可判定性属性的上下文无关的edNCE图语言。我们使用常规路径描述来定义图形语言，而不是上下文无关的图形语法。1997年学术出版社
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 partial 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. ] 1997 Academic Press