论文标题
任何由Monadic二阶公式定义的套装家族的树木的增长率都是半计算的
The growth rate over trees of any family of set defined by a monadic second order formula is semi-computable
论文作者
论文摘要
Monadic二阶逻辑可用于表达图形顶点集的许多经典概念，例如：主导集，诱导的匹配，完美的代码，独立集或不冗余集。从组合的角度来看，任何此类集合的集合的集合数量都很有趣，并且具有算法应用。文献中已经提供了许多在不同类别的图表上不同类别的家族的界限。尤其是，死记硬背最近表明，在$ n $的树木中，最小的主导集数量最多为$ 95^{\ frac {n} {13}} $，并且该界限在渐近上是渐近的，达到多重常数。我们以他的工作为基础，以表明他为最小的主导套装所做的一切都可以为任何可以通过Monadic的二阶公式定义的家族来完成。 我们首先表明，对于表征其顶点的给定类型子集的任何单声道二阶公式，树中此类集合的最大数量可以表示为\ textit {双线性系统的增长率}。这主要取决于树木和树自动机和基本树自动机械操作之间的Monadic二阶逻辑之间的众所周知的链接。然后，我们表明，双线性系统的这种“增长率”可以从上方近似。然后，我们使用此结果的实现来提供独立的主导套装的数量，全部完美的统治集，诱导的匹配，最大诱导的匹配，最小的完美支配集，完美的代码，完美的代码，完美的代码和最大的不合格集合。我们还解决了D. Y. Kang等人的问题。关于$ r $ - 匹配，并改善了Górska和Skupień对树木上最大匹配的数量。请注意，这种方法很容易被推广到有界树宽度或集团宽度的图（或树自动机有意义的任何类似的图形）。
Monadic second order logic can be used to express many classical notions of sets of vertices of a graph as for instance: dominating sets, induced matchings, perfect codes, independent sets or irredundant sets. Bounds on the number of sets of any such family of sets are interesting from a combinatorial point of view and have algorithmic applications. Many such bounds on different families of sets over different classes of graphs are already provided in the literature. In particular, Rote recently showed that the number of minimal dominating sets in trees of order $n$ is at most $95^{\frac{n}{13}}$ and that this bound is asymptotically sharp up to a multiplicative constant. We build on his work to show that what he did for minimal dominating sets can be done for any family of sets definable by a monadic second order formula. We first show that, for any monadic second order formula over graphs that characterizes a given kind of subset of its vertices, the maximal number of such sets in a tree can be expressed as the \textit{growth rate of a bilinear system}. This mostly relies on well known links between monadic second order logic over trees and tree automata and basic tree automata manipulations. Then we show that this "growth rate" of a bilinear system can be approximated from above.We then use our implementation of this result to provide bounds on the number of independent dominating sets, total perfect dominating sets, induced matchings, maximal induced matchings, minimal perfect dominating sets, perfect codes and maximal irredundant sets on trees. We also solve a question from D. Y. Kang et al. regarding $r$-matchings and improve a bound from Górska and Skupień on the number of maximal matchings on trees. Remark that this approach is easily generalizable to graphs of bounded tree width or clique width (or any similar class of graphs where tree automata are meaningful).
