Describing Graphs: A First-Order Approach to Graph Canonization

Describing Graphs: A First-Order Approach to Graph Canonization
复制标题

描述图：图规范化的一阶方法

DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
E. Lander
E. Lander
中科院分区：
--
文献类型：
--
作者：
N. Immerman;E. Lander

文献摘要

被引文献

相似文献

在本文中，我们问的问题，“什么必须添加到一阶逻辑加上最小不动点，以获得确切的多项式时间性质的无序图？”我们认为语言L k组成的一阶逻辑限制到k个变量和C k组成的L k加上“计数量词”。我们给出了有效的标准化算法的特征在于Ck或Lk的图。它遵循从已知的结果，所有的树和几乎所有的图的特征在于C2。
In this paper we ask the question, “What must be added to first-order logic plus least-fixed point to obtain exactly the polynomial-time properties of unordered graphs?” We consider the languages L k consisting of first-order logic restricted to k variables and C k consisting of L k plus “counting quantifiers”. We give efficient canonization algorithms for graphs characterized by C k or L k . It follows from known results that all trees and almost all graphs are characterized by C 2.