FO Model Checking on Map Graphs
FO Model Checking on Map Graphs
复制标题
地图上的 FO 模型检查
DOI：
10.1007/978-3-662-55751-8_17
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
K. Kawarabayashi
中科院分区：
文献类型：
--
作者：
K. Eickmeyer;K. Kawarabayashi
对于单调图类上的一阶逻辑模型检验，易处理和难处理之间的分界线被很好地画出：它在所有无处密集的图类上都是可处理的，这本质上是极限。与此形成鲜明对比的是，对于一般图类的模型检测，即不一定是单调的，很少有关于模型检测的结果.我们证明了当以输入公式的大小为参数时，映射图上一阶逻辑的模型检测是固定参数可处理的.映射图是一类几何定义的图，类似于平面图，但在这里，图的每个顶点都被画成与平面上的闭圆盘同胚，当且仅当相应的圆盘相交时，两个顶点是相邻的。映射图可以包含任意大的团，并且在边去除的情况下不是闭合的，我们的算法将给定的映射图有效地转换为一个无处稠密图，其中的原始图是一阶可解释的。作为该技术的一个副产品，我们还得到了树正方形上FO的一个模型检验算法。
For first-order logic model checking on monotone graph classes the borderline between tractable and intractable is well charted: it is tractable on all nowhere dense classes of graphs, and this is essentially the limit. In contrast to this, there are few results concerning the tractability of model checking on general, i.e. not necessarily monotone, graph classes.We show that model checking for first-order logic on map graphs is fixed-parameter tractable, when parameterised by the size of the input formula. Map graphs are a geometrically defined class of graphs similar to planar graphs, but here each vertex of a graph is drawn homeomorphic to a closed disk in the plane in such a way that two vertices are adjacent if, and only if, the corresponding disks intersect. Map graphs may contain arbitrarily large cliques, and are not closed under edge removal.Our algorithm works by efficiently transforming a given map graph into a nowhere dense graph in which the original graph is first-order interpretable. As a by-product of this technique we also obtain a model checking algorithm for FO on squares of trees.
登录
查看更多内容
DOI：
10.1137/s089548019120016x
发表时间：
1991
期刊：
ArXiv
影响因子：
--
作者：
Yaw;S. Skiena
通讯作者：
S. Skiena
DOI：
10.1007/10692760_1
发表时间：
1998-06
期刊：
--
影响因子：
--
作者：
B. Courcelle;J. Makowsky;Udi Rotics
通讯作者：
B. Courcelle;J. Makowsky;Udi Rotics
有向图的平方根
DOI：
--
发表时间：
1968
期刊：
影响因子：
--
作者：
D. Geller
通讯作者：
D. Geller
区间图的 FO 模型检验
DOI：
--
发表时间：
2013
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
R. Ganian;Petr Hliněný;D. Král;J. Obdržálek;Jarett Schwartz;Jakub Teska
通讯作者：
Jakub Teska
DOI：
--
发表时间：
2011
期刊：
JACM
影响因子：
--
作者：
Zdenek Dvorák;D. Král;R. Thomas
通讯作者：
R. Thomas