Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
复制标题
更快地确定固定高度树木的 MSO 特性以及一些后果
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Petr Hliněný
中科院分区：
文献类型：
--
作者：
Jakub Gajarský;Petr Hliněný
我们证明，在宇宙中的树的有界高度，任何MSO公式与$m$变量存在一组内核，使这些内核的大小可以有界的一个初等函数的m。这产生了一个更快的MSO模型检测算法的树的有界高度比一般的树。
由此，通过解释，我们得到了有界树深（MSO_2）和有界灌木深（MSO_1）的图类的相应结果，从而我们给出了Lampis（ESA 2010）和Ganian（IPEC 2011）结果的广泛推广.在本文的第二部分中，我们使用这种核结构，以表明FO具有相同的表达能力MSO_1上的有界灌木深度的图类。这使得有界灌木深度成为表征FO和MSO_1重合的图的遗传类的一个很好的候选者，这是Elberfeld，Grohe和Tantau最近提出的一个问题（LICS 2012）。
We prove, in the universe of trees of bounded height, that for any MSO formula with $m$ variables there exists a set of kernels such that the size of each of these kernels can be bounded by an elementary function of m. This yields a faster MSO model checking algorithm for trees of bounded height than the one for general trees.
From that we obtain, by means of interpretation, corresponding results for the classes of graphs of bounded tree-depth (MSO_2) and shrub-depth (MSO_1), and thus we give wide generalizations of Lampis' (ESA 2010) and Ganian's (IPEC 2011) results. In the second part of the paper we use this kernel structure to show that FO has the same expressive power as MSO_1 on the graph classes of bounded shrub-depth. This makes bounded shrub-depth a good candidate for characterization of the hereditary classes of graphs on which FO and MSO_1 coincide, a problem recently posed by Elberfeld, Grohe, and Tantau (LICS 2012).