非确定性代数重写为伴随
本文提出了一种多值扩展的逻辑程序,基于可靠模型语义,其中模型中的每个真实原子都与一组证明关联,在一个证明树的集合中类似,我们将证明捕捉到一个真值的代数中,该代数具有三个内部操作:加号表示公式的替代证明,可交换乘积表示导致的联合交互以及非交换积表示证明构造器。使用这种多值语义,我们得到了标准(非因果)逻辑程序的语法证明树与模型中每个真实原子的解释之间的一一对应关系,并且由于这种代数特征,我们可以检测到获得的证明的冗余性和相关性。我们还确定了此代数的基于格的特征,定义了直接后果算子,证明了其连续性,并证明其最小修复点可以在有限次迭代后计算。最后,我们通过引入类似于Gelfond和Lifschitz的程序削减的变换来定义因果稳定模型的概念。
Dec, 2013
我们提出了一种新的线性代数方法来计算逻辑中的Tarskian语义。通过将M的实体映射到N维独热向量和k元关系映射到k阶邻接张量,我们在具有N个实体的N维欧几里得空间R ^ N中嵌入了一个有限模型M。在此框架基础上,我们还提出了一种在线性空间中计算Datalog程序定义的最小模型的前所未有的方法,并通过矩阵方程表明其与现有方法相比的有效性。
Mar, 2017
本文探讨了语法组合性的各种概念,思考其在自然语言和人工语言领域中的作用,并提出了这些组合性原则对于满足其条件的语言的表达能力应具有非平凡的组合要求。在例子中,我们展示了一种形式化分析,证明了一类能适应 'salva vertitate substitutions' 的语言,这是一种特别强的组合原则,必须满足本文所确定的一种非常自然的组合约束条件。
Jan, 2022
本文研究了使用拼接查询组成的联合响应(UCQs)答案问题,有“或型存在规则和映射”。本文首先提出了一个完整的查询重写操作符,并使用广度优先查询重写算法来输出最小的UCQ重写副本。其次,我们证明,在任何真正的“分离”递归规则中,存在一种联合查询,不需要UCQ重写。最后,本文研究了通过“或型映射”决定UCQ是否有UCQ重写的问题,结果是不可判定的。
Jun, 2023
我们提出了一种新的高阶DisCoCat(分类组合分布)模型的定义,其中词的意义不是一个图表,而是一个图表值的高阶函数。我们的模型可以看作是基于lambda演算的Montague语义的变体,其中的原始操作作用于字符串图表而不是逻辑公式。作为特例,我们展示了如何从Lambek演算翻译为一阶逻辑中的Peirce系统贝塔。这使我们能够在自然语言语义中以纯图表的方式处理高阶和非线性过程:副词、介词、否定和量词。这篇文章中提出的理论定义带有DisCoPy的概念验证实现,这是用于字符串图表的Python库。
Nov, 2023
该研究介绍了使用语法宏对有限形式语言进行重写的问题,提出了多项式时间算法来解决该问题的变体,并展示了其正确性。通过将算法应用于OWL编写的生物医学本体论,证明了该问题的实际相关性以及算法的可行性和有效性。此方法在提升本体质量和理解方面提供了有价值的帮助,并以系统的方式分析和评估重写系统的特性,包括语法宏、模板或其他形式的重写规则对计算问题的影响。
Dec, 2023
提出了一种新的范畴语法家族,通过丰富基本的范畴语法,引入了一个连接操作。证明了这种方式得到的形式与带有连接的上下文无关文法具有相同的表达能力。还证明了带有连接的范畴语法可以自然地嵌入到带有连接和析取操作的Lambek演算中。这进一步意味着可以在带有连接的Lambek演算中定义一个特定的NP完全集。还展示了如何处理与空字符串相关的一些微妙问题。最后,证明了由连词语法生成的语言可以由不带有连接但具有析取的Lambek语法描述。
May, 2024