...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Monadic second-order model-checking on decomposable matroids
【24h】

Monadic second-order model-checking on decomposable matroids

机译：可分解拟阵的单阶二阶模型检验

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A notion of branch-width, which generalizes the one known for graphs, can be defined for matroids. We first give a proof of the polynomial time model-checking of monadic second-order formulas on representable matroids of bounded branch-width, by reduction to monadic second-order formulas on trees. This proof is much simpler than the one previously known. We also provide a link between our logical approach and a grammar that allows one to build matroids of bounded branch-width. Finally, we introduce a new class of non-necessarily representable matroids, described by a grammar and on which monadic second-order formulas can be checked in linear time.
机译：可以为拟阵定义定义分支宽度的概念，该概念概括了已知的图形。我们首先通过对树上的一阶二阶公式进行简化，证明了可表示的有界分支宽度的拟阵上的一阶二阶公式的多项式时间模型检查。这个证明比以前已知的要简单得多。我们还提供了一种逻辑方法与一种语法之间的联系，该语法允许人们建立边界分支宽度的拟阵。最后，我们介绍了一类新的不必要的拟阵拟阵，用语法描述，可在线性时间上检查其二阶二阶公式。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号