On the Decidability of Intuitionistic Tense Logic without Disjunction

Fei Liang, Zhe LinIJCAI 2020 · DOI

TL;DR

This paper tackles the decidability of a specific fragment of intuitionistic tense logic, which is crucial for reasoning about dynamic systems. By developing a novel algebraic framework and employing proof-theoretic techniques, the authors prove that this logic has the finite model property, directly leading to its decidability.

What Problem Does This Paper Address?

Intuitionistic logic and its extensions are fundamental in areas like computer science and artificial intelligence, particularly for modeling dynamic processes and knowledge representation. Tense logics, which deal with temporal aspects, are extensions of these logics. While intuitionistic tense logic itself is a complex area of study, researchers are also interested in its fragments, especially those that simplify reasoning without losing essential expressive power. This paper focuses on the disjunction-free fragment of intuitionistic tense logic. The core problem is to determine if this fragment is decidable, meaning there's an algorithm to decide whether any given formula is a theorem. Decidability is a key property for practical applications, as it guarantees that automated reasoning systems can terminate. The paper builds upon existing work on implicative semi-lattices (a generalization of Heyting algebras) and their connection to intuitionistic logic.

Methods

The authors employ a combination of algebraic and proof-theoretic methods.

  • Algebraic Semantics: They introduce "tense implicative semi-lattices" (ISt-algebras) as the algebraic models for the disjunction-free fragment of intuitionistic tense logic. These algebras are built upon implicative semi-lattices by adding tense operators.
  • Gentzen Sequent Calculus: A sequent calculus, GIKt, is defined for intuitionistic tense logic, and a related calculus, GISt, is defined for the ISt-algebras (specifically, for the disjunction-free fragment). These calculi are designed to enjoy cut-elimination and the subformula property, which are crucial for proving decidability.
  • Finite Model Property (FMP): The central technical contribution is proving that the logic of ISt-algebras has the finite model property. This means that if a formula is valid in the logic, it is also valid in some finite ISt-algebra. The proof strategy involves constructing finite quotient algebras from sets of formulas.
  • Decidability: The paper leverages the established connection between the finite model property, finite axiomatizability (which is inherited from intuitionistic tense logic), and decidability.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Algebra and Proof Theory: The paper effectively bridges the gap between abstract algebraic structures (ISt-algebras) and formal proof systems (sequent calculus) to establish logical properties.
  • The Power of Disjunction-Free Fragments: By focusing on the disjunction-free fragment, the authors simplify the problem while retaining significant expressive power for temporal reasoning. This suggests that many temporal reasoning tasks might be solvable even without explicit disjunction.
  • Constructing Finite Models: The method of constructing finite quotient algebras from sets of formulas is a key technique for proving the finite model property. This constructive approach is valuable for understanding the structure of these logics.
  • Decidability as a Consequence: The paper demonstrates that decidability isn't just an abstract property but a direct consequence of having the finite model property and finite axiomatizability.

Key Results

  • The logic of tense implicative semi-lattices (ISt) has the finite model property.
  • This implies that the disjunction-free fragment of intuitionistic tense logic is decidable.
  • The paper provides a sound and complete sequent calculus (GISt) for ISt.
  • It also shows that GIKt is a conservative extension of GISt.

Limitations and Future Work

  • Extension to Full Intuitionistic Tense Logic: The authors note that their results for the disjunction-free fragment do not straightforwardly extend to the full intuitionistic tense logic (IKt) because certain lemmas (like Lemma 16 and 19) do not hold when disjunction is present. Proving the FMP for IKt remains an open question.
  • Computational Complexity: While decidability is established, the computational complexity of the logic of ISt is unknown. The authors suggest that their sequent system might help in finding upper bounds for this complexity.
  • Applications: The paper highlights potential applications in temporal extensions of logic programming and modeling dynamic processes in AI, suggesting these as avenues for future research.

Summary updated

BibTeX
@inproceedings{liang2020decidability,
  author = {Fei Liang and Zhe Lin},
  title = {{On the Decidability of Intuitionistic Tense Logic without Disjunction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/249},
}
Figure