paperbot · PL 论文追踪

全部论文 待读 收藏

P2 An Integrated First-Order Theory of Points and Intervals over Linear Orders (Part II)

线性序上的点与区间统一一阶理论（第二部分）
LMCS Volume 16, Issue 2(Logic for knowledge...)2020匹配度 1/10 · 该论文研究线性序上点-区间一阶语言的相对表达力分类，属于纯逻辑与形式语义/时序本体论方向，与用户关注的静态分析、LLM/Agent 改进形式化验证、浮点程序分析、贝叶斯程序分析均无直接交叉。引用 1 inbox
Willem Conradie, Salih Durhan, Guido Sciavicco
逻辑与自动机
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话：对线性序上的点-区间两类一阶语言进行相对表达力完全分类，并确定其本质不同的扩展。

该文第二部分研究时间本体与推理中基于点和基于区间两种视角。不同于将点视为零长区间的传统做法，作者采用点与区间地位平等的双类（two-sorted）一阶框架，允许在形式语言中同时谈论点、区间以及点间、区间间和跨类关系。工作对由这些关系构成的子语言按相对表达力进行完全分类，确定双类一阶逻辑在这些关系下有多少种、哪些本质不同的扩展，从而消除“区间语义是否必须包含点”的经典问题。第二部分具体处理所有稠密线性序和所有无界线性序的情形。

问题
研究问题：在基于线性序的双类一阶逻辑中，点与区间同时作为本体，加入点间、区间间及跨类关系后，各子语言的相对表达力如何分类，以及点是否必须被纳入区间语义。
方法
方法：定义基于点与区间的双类一阶语言及其关系子语言，通过模型论与表达力分析进行相对表达力分类。
评估
评估：对稠密线性序和无界线性序的所有情形给出完整分类，确定本质不同扩展的数量与具体形式。
原文摘要（Abstract）

There are two natural and well-studied approaches to temporal ontology and reasoning: point-based and interval-based. Usually, interval-based temporal reasoning deals with points as a particular case of duration-less intervals. A recent result by Balbiani, Goranko, and Sciavicco presented an explicit two-sorted point-interval temporal framework in which time instants (points) and time periods (intervals) are considered on a par, allowing the perspective to shift between these within the formal discourse. We consider here two-sorted first-order languages based on the same principle, and therefore including relations, as first studied by Reich, among others, between points, between intervals, and inter-sort. We give complete classifications of its sub-languages in terms of relative expressive power, thus determining how many, and which, are the intrinsically different extensions of two-sorted first-order logic with one or more such relations. This approach roots out the classical problem of whether or not points should be included in a interval-based semantics. In this Part II, we deal with the cases of all dense and the case of all unbounded linearly ordered sets.Comment: This is Part II of the paper `An Integrated First-Order Theory of Points and Intervals over Linear Orders' arXiv:1805.08425v2. Therefore the introduction, preliminaries and conclusions of the two papers are the same. This version implements a few minor corrections and an update to the affiliation of the second author

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@article{abs-1809-04468,
  title = {An Integrated First-Order Theory of Points and Intervals over Linear Orders (Part II)},
  author = {Willem Conradie and Salih Durhan and Guido Sciavicco},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 2},
  number = {Logic for knowledge...},
  year = {2020},
  doi = {10.23638/lmcs-16(2:1)2020}
}