arXiv:2304.06348v5 通报类型: replace-cross 摘要: 我们提出了一种通用框架，用于确定广泛范围的逻辑蕴含问题（简称为查询）的可判定性，基于存在结构简单（根据某些类型的标准测量宽度，例如知名的 treewidth 和 cliquewidth）的反模型。我们框架的一个重要特殊情况是，我们确定了具有宽度有限有限完全模型集的逻辑，这导致广泛的同态闭查询具有可判定的蕴含，涵盖了许多实际相关的查询语言。作为强有力的宽度测量，我们建议采用 Blumensath 的分区宽度，它涵盖了其他许多常见的宽度测量，并且具有非常有利的计算和结构属性。我们以存在规则这一流行的展示形式为例，解释了有限分区宽度规则集如何涵盖了其他已知的抽象可判定类，同时借助现有分层概念涵盖了更广泛的规则集。我们揭示了将有限统一集类纳入我们框架中的自然局限性，并提出了几种补救措施。