The Expression of Graph Properties and Graph Transformations in Monadic Second-Order Logic
The Expression of Graph Properties and Graph Transformations in Monadic Second-Order Logic
复制标题
一元二阶逻辑中图性质和图变换的表达
DOI：
10.1142/9789812384720_0005
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
B. Courcelle
中科院分区：
文献类型：
--
作者：
B. Courcelle
通过把图看作逻辑结构，人们可以用逻辑公式形式化地表达它们的性质。我们回顾使用一元二阶逻辑表示图形属性，也，图形转换。我们回顾了一元二阶逻辑和上下文无关图文法的密切关系。我们还讨论了图类的禁止配置的定义。
By considering graphs as logical structures, one can express formally their properties by logical formulas. We review the use of monadic second-order logic for expressing graph properties, and also, graph transformations. We review the intimate relationships of monadic second-order logic and context-free graph grammars. We also discuss the definition of classes of graphs by forbidden configurations.