摘要翻译：
区间时态逻辑是一种用于对时间语句进行推理的逻辑，这些语句是在时间间隔（即时间周期）上表达的。到目前为止研究的最著名的ITL是Halpern和Shoham的HS，它是13个Allen区间关系的逻辑。不幸的是，HS及其大部分片段都存在一个不可判定的可满足性问题。这阻碍了这一领域的研究，直到最近才发现了一些重要的可判定的ITL。本文是对HS所有不同片段的完整分类的贡献。我们考虑区间关系的不同组合开始，之后，后来和他们的逆Abar，Bbar和lbar。我们从以前的工作中知道，组合ABBbarAbar只有当有限域被考虑时才是可判定的（在其他地方是不可判定的），并且ABBbar在自然数上是可判定的。我们推广了这些结果，证明了ABBar的可判定性可以进一步推广到捕获介于ABBar和ABBbarAbar之间的语言ABBbarLbar，并且在强离散线性阶（如有限阶、自然阶、整数阶）上具有最大的W.R.T可判定性。我们还证明了所提出的决策过程对于复杂度类是最优的。
---
英文标题：
《Begin, After, and Later: a Maximal Decidable Interval Temporal Logic》
---
作者：
Davide Bresolin (University of Verona, Verona, Italy), Pietro Sala
  (University of Verona, Verona, Italy), Guido Sciavicco (University of Murcia,
  Murcia, Spain)
---
最新提交年份：
2010
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Logic in Computer Science        计算机科学中的逻辑
分类描述：Covers all aspects of logic in computer science, including finite model theory, logics of programs, modal logic, and program verification. Programming language semantics should have Programming Languages as the primary subject area. Roughly includes material in ACM Subject Classes D.2.4, F.3.1, F.4.0, F.4.1, and F.4.2; some material in F.4.3 (formal languages) may also be appropriate here, although Computational Complexity is typically the more appropriate subject area.
涵盖计算机科学中逻辑的所有方面，包括有限模型理论，程序逻辑，模态逻辑和程序验证。程序设计语言语义学应该把程序设计语言作为主要的学科领域。大致包括ACM学科类D.2.4、F.3.1、F.4.0、F.4.1和F.4.2中的材料；F.4.3（形式语言）中的一些材料在这里也可能是合适的，尽管计算复杂性通常是更合适的主题领域。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  Interval temporal logics (ITLs) are logics for reasoning about temporal statements expressed over intervals, i.e., periods of time. The most famous ITL studied so far is Halpern and Shoham's HS, which is the logic of the thirteen Allen's interval relations. Unfortunately, HS and most of its fragments have an undecidable satisfiability problem. This discouraged the research in this area until recently, when a number non-trivial decidable ITLs have been discovered.   This paper is a contribution towards the complete classification of all different fragments of HS. We consider different combinations of the interval relations Begins, After, Later and their inverses Abar, Bbar, and Lbar. We know from previous works that the combination ABBbarAbar is decidable only when finite domains are considered (and undecidable elsewhere), and that ABBbar is decidable over the natural numbers. We extend these results by showing that decidability of ABBar can be further extended to capture the language ABBbarLbar, which lays in between ABBar and ABBbarAbar, and that turns out to be maximal w.r.t decidability over strongly discrete linear orders (e.g. finite orders, the naturals, the integers). We also prove that the proposed decision procedure is optimal with respect to the complexity class.
---
PDF链接：
https://arxiv.org/pdf/1006.1407