一阶模型计数的递归函数合成:挑战、进展和猜想
本研究提出了一种Skolem化算法来解决模型计数问题,扩展了一阶模型计数器的适用范围,使其能够用于概率逻辑程序等有向模型,同时还简化了抬升模型计数算法的设计。
Dec, 2013
本文研究了解析式权重一阶模型计数问题的Lifted Inference问题,通过提供一些结论,针对解析式的约束进行了分析讨论,并探讨了在对称概率性数据库中采用Lifted Inference的局限性和复杂性。
May, 2014
本文研究了使用稳定模型语义进行推理的问题,提出了两种基于未建立的集合检测的实现技术,扩展了命题模型计数器到稳定模型计数器,可以在时间和空间使用方面显著优于现有的解决方案。
Nov, 2014
在本文中,我们研究了对称加权有限模型计数问题的复杂性,旨在解决知识库推理中的软约束问题。我们证明了特定情况下该问题的数据复杂度可在多项式时间内计算,但在一般情况下该问题在#P中是完全的复杂度。
Dec, 2014
本文介绍了一种新的 lifted interpretations 工具,用于重构 Beame et al. 提出的多项式时间 FOMC 的闭合式公式,并将其扩展以涵盖基数约束、存在量词和计数量词(C2),同时仍然保持 domain-liftability。最后,我们展示了所获得的闭合形式促进了一种权重函数家族的自然定义,严格大于对称权重函数。
Oct, 2021
本文研究了最近由Wang等人提出的一阶逻辑采样问题——如何在有限域上高效地采样给定一阶句子的模型?我们将他们对于双变量逻辑FO^2的普遍量化子片段UFO^2的结果扩展到整个FO^2片段。具体来说,我们证明了FO^2在采样下的域可扩展性,即存在一种能在域大小多项式时间下运行的FO^2采样算法。然后,我们进一步表明,即使存在像所有x存在= ky: φ(x,y)和存在= kx为所有y的数量约束,如φ(x,y)的量化器公式,我们的方法也可以保持运作。我们的提出的方法是具有建设性的,由此产生的采样算法在各个领域都有潜在的应用,包括在组合结构和统计关系模型的均匀生成方面以及如Markov逻辑网络和概率逻辑程序的采样方面。
Feb, 2023
该论文研究的是加权一阶模型计数问题(WFOMC),主要关注于能够在多项式时间内进行WFOMC的逻辑片段,其中包括经过拓展的两变量一阶逻辑碎片及其衍生的包含计数量词的逻辑碎片,通过在关系上添加定向无环图(DAG)公理,这篇论文对子领域进行了扩展。
Feb, 2023
据我们展开的C²的领域扩展,任何C²句子在其关系受限于表示有向无环图、连通图、树(或有向树)、森林(或有向森林)时仍保持领域可提升,这提供了一个计算组合结构的通用框架。
Aug, 2023