- 基于结构的约束学习马尔可夫网络
用约束条件的结构学习方法学习马尔可夫网络的理论限制与性能逐渐变好,并且对条件独立性测试的集合大小和测试数量进行了研究。
- AAAI同步动态系统的结构复杂性分析
研究了同步动态系统中的三个问题:系统从初始配置是否过渡到目标配置,系统从初始配置是否达到收敛,以及系统是否保证从所有可能的初始配置达到收敛,通过利用更细粒度的参数化复杂性范式,研究了网络的结构参数的确切可解性边界。对于常数树宽的实例,表明所 - 三台弱同步系统的图灵能力
在弱同步系统中,我们研究了有限状态机和异步消息传递分布式系统,特别是对于 p2p (FIFO) 通信,我们证明了三个进程的弱同步系统的配置可达性问题是不可判定的,并且其生成的消息序列图具有任意大的树宽。
- 利用树宽及其限制条件解决投影模型计数问题
本文介绍了一种新算法来解决投影模型计数(PMC)问题,该算法利用输入实例的原始图的小树宽,并在同时考虑了指标化的树宽有理论下限的情况下,提供固定参数可解,通过使用嵌套动态规划,并在数据库技术的帮助下,可以解决树宽上限超过 200 的实例的 - 逻辑程序结构硬度的表征:为什么对于树宽而言,环和可达性很难?
本文介绍了一种从 SAT 到 normal ASP 的新型减少方法,并通过建立依赖图的循环长度(SCC 大小)与树宽之间所需的功能依赖性,以一种细粒度的方式刻画了硬度。
- 反事实推理的复杂度
研究计算复杂性和结构因果模型条件下反事实推理的关系并指出,如果在完全指定的情况下关于结构因果模型的干预性推理是可行的,则反事实推理也是可行的。
- IJCAI阈值树宽和超树宽
介绍了树宽和超树宽的概念,并通过计算阈值树宽和超树宽,提出了一种固定参数算法,可在多项式时间内解决 CSP 问题。
- 基于树宽的 ASP 到 SAT 的归约 -- ASP 普通形式难度比 SAT 高吗?
本文提出了一种新的从 ASP 到 SAT 的规约(Reduction)方法,并证明了在考虑 Treewidth 时,一般 ASP 的难度比 SAT 稍微更高,同时还对新规约进行了实证研究。
- 基于树宽求解问题的高级工具和方法 - 扩展摘要
本文主要研究了基于逻辑的问题及基于 treewidth 的方法和工具,并提出了一种新类型的问题降解方法,其中问题为有界 treewidth 的量化布尔公式(QBF)。结果表明,treewidth 是设计现代求解器时应考虑的一项重要的测量标准 - 从基于宽度的模型检查到基于宽度的自动定理证明
该研究提出了一种通用框架,将基于宽度的模型检查算法转换为用于测试具有有限宽度图类的图论猜想的算法,并显示了在树宽度为 $k$ 的所有图上验证图论猜想的算法,时间为 $ k^{O (1)}$ 双指数级。
- AAAI存在结构侧信息条件下的贝叶斯网络学习
本研究开发了一种递归约束算法,能够高效地将结构性边缘信息引入学习贝叶斯网络 (BN) 的过程,并提供了该算法的理论保证,进一步表明有界树宽 BN 可以在不增加复杂度的情况下学习。
- MM利用树宽度进行认识逻辑程序的数量推理
本篇论文介绍了一种利用图形方法和动态规划结合已有的搜索求解器来解决定量推理问题的新系统,可以有效地处理 Answer Set Programming 方法中 epistemic logic programs 的复杂问题。
- AAAI利用拼块特性解决无限域 CSP 问题
研究了约束满足问题中基本关系具有小拼接性质的 CSP,提出了一种求解这类问题的算法,时间复杂度为 f (w)・n^{O (1)},并且不仅限于二元约束。
- 小树幅线性规划的近线性时间算法:健壮中心路径的多尺度表示
本文提出了一种基于内点法和树分解的线性规划问题求解算法,可以在近似相对误差为 ε 的情况下,在时间复杂度 Θ(n ⋅ tw² ⋅ log (1/ε)) 内求解给定的线性规划问题,其中 tw 是输入图的树宽,并且是第一个时间复杂度与子问题 A - MM利用数据库管理系统和树宽进行计数
本文提出了一种基于数据库管理系统的通用框架来解决具有小分解树宽度的问数问题,利用动态规划在分解树上进行计算,并将 DP 算法实现到了一个 DBMS (PostgreSQL) 中。这是我们的实验室采用 DBMS 进行处理 TDs 算法的第一次 - AAAI用于最优经典计划的高维势启发式
本研究尝试寻找一种比先前方法更有效的状态空间搜索算法,并通过构造新的图形结构来实现可行性和可解性的结果。
- AAAI抽象论证推理的计数复杂度
本文探讨抽象论证中关于扩展项的计数和投影模型计数,提出了一种基于动态规划的新算法,并建立了经典和参数化的复杂度结果,考虑到评估参数化问题的树宽度,最后针对有界树宽算法建立下界,得出复杂度分析结论。
- QBF 作为 Courcelle 定理的替代
本文采用量化布尔公式减少作为一种新的方法来展示固定参数线性算法,研究人工智能领域的几个已知问题,其中大部分问题已经通过使用 Courcelle 定理或动态规划证明了其固定参数线性,但作者认为采用 量化布尔公式 减少这种方法具有明显的优势。
- 从完整和不完整数据集中高效学习有界树宽贝叶斯网络
本文提出一种新的 k-MAX 算法用于学习具有有界三角形宽度的贝叶斯网络,改进了数据不完全的结构 EM 算法,进而实现了缺失数据的填充。该算法可以在短时间内获得和竞争者相同的缺失数据恢复精度,并且具有线性最坏时间复杂度和易于并行化等优点。
- 结合树宽和后门求解 CSP 问题
本研究论文表明,当以任何可转化为有限约束语言的可解 CSP 问题作为背景门限时,CSP 是固定参数可解的,这将结合了两个解决 CSP 可解性问题的突出方法:(i) 通过变量和约束之间交互的结构限制和 (ii) 通过内部约束所使用的关系的语言