研究定值约束满足问题,利用基本线性规划松弛和对称分数多项式的精确代数刻画,实现了多个类的问题的可处理性,包括在任意格上子模的问题,任意有限域上的 k - 子模问题,任意树上具有弱(hence 强)树子模的问题。
Nov, 2013
通过证明各种规约保持 Lasserre SDP 层次的精确可解性,我们展示了支持破坏有限宽度条件的一般值约束语言不能被静态程序快速求解。
Dec, 2016
研究了正 Datalog 上添加整数算术函数的扩展语言 Datalog_Z,并提出了两个限制子语言 limit Datalog_Z 和 stable Datalog_Z 以解决其不可判定性,并证明了相应的 NP 完全性和 ExpTime 完全性,最终表明稳定的 Datalog_Z 能够表达许多有用的数据分析任务,为先进信息系统的发展提供了一个坚实的基础。
May, 2017
研究了约束满足问题中基本关系具有小拼接性质的 CSP,提出了一种求解这类问题的算法,时间复杂度为 f (w)・n^{O (1)},并且不仅限于二元约束。
Jul, 2021
本研究旨在模型理论中建立存在规则语言的模型论特性,如嵌入依赖项,元组生成依赖项和线性依赖项,并确定它们的复杂度限制。
Jan, 2020
神经符号人工智能领域的主要挑战之一是在神经和符号数据的存在下进行逻辑推理。本文通过将模糊 Datalog 的存在性规则推广到模糊设置,允许使用任意 t - 范数,在保持计算复杂度结果和已建立的推理技术适用性的同时,允许对与不确定度相关的数据进行推理。
Mar, 2024
本文研究在一个规范上执行广泛的推断任务的可行性,通过将 IDP3 扩展到与动态规范相关的领域中使用的多种推断技术。
May, 2014
本文研究的是 epsilonE-logic 中关于有限模型的可满足性和有效性问题,特别是对于有理的 epsilon,结果为 Sigma^0_1 和 Pi^0_1 完备性,而对于 epsilon=0,结果为可判定,但对于可数模型的 εE 逻辑的可计算性仍然存在研究点;此外,还讨论了在计算学习理论,加权图和神经网络中的应用。
Oct, 2014
该研究通过引入 “有限团宽集合”(FCS)来寻求可决定本体论查询的一般性标准,FCS 是一种模型理论定义的规则集类,受到图论中团宽的启发,这一类规则集确保了一类子句共有查询(DaMSOQs)的蕴涵可决定性,它们吸收了合取查询(CQs)并且限制于元数为 2 的符号。
Sep, 2022
研究 CSP 实例的后门问题,提出了一种泛化后门概念,即面向具有高元数约束的 CSP,并介绍了 sidedoors 作为对二元约束不利的替代方案,降低了算法复杂度和提高了计算效率。
Nov, 2022