Skip to content
DraconiticResearch
Search Sources API
184,937 studies31 sourcesUpdated 59 min ago
PreprintCC BY 4.0arXiv

Most Properties are Undecidable for Transitive Tense Logics

  • Qian Chen
  • Tenyo Takahashi
Open at sourcePDFDOICite

Abstract

A logics' property is decidable in a class of logics if there exists an algorithm that decides whether a finitely axiomatizable logic in the class has the property. Many properties are undecidable for bimodal logics but decidable for linear tense logics, which leads to a general question on how the interactions of modalities affect the decidability of properties. In this paper, we study the decidability of properties for transitive tense logics and show that most properties are undecidable in the lattice NExt(K4t) of transitive tense logics, including Kripke completeness, the finite model property, and decidability. Our proof method adapts Chagrov's approach of constructing a reduction from an undecidable problem of Minsky machines to the decision problem for logics' properties, yielding a general scheme of proving the undecidability of these properties.

Versions

Related

  1. Most properties are undecidable even in mathopNExt Grzt
    Qian Chen, Tenyo Takahashi
    arXivPreprintCC BY-NC-SA 4.0Full textLogic & foundationsarXiv
  2. Tense Logic via Truth Degrees: An Algebraic Completeness Result for Kashima's Calculus
    Martín Figallo, Jonathan Sarmiento, Luis Pezzini
    arXivPreprintarXiv licenceFull textLogic & foundationsarXiv
  3. An undecidable problem in dynamics
    Jason Bell
    arXivPreprintarXiv licenceFull textAlgebra & number theoryDynamical systemsarXiv
  4. The Global Asymptotic Stability Problem for Linear MPC Is Undecidable
    Johan Löfberg
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Quantum n-coloring is undecidable for every n ≥ 3
    Christian Bo Kidmose-Frederiksen, Alfred Leth Nielsen
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026most,
  title = {{Most Properties are Undecidable for Transitive Tense Logics}},
  author = {Qian Chen and Tenyo Takahashi},
  howpublished = {arXiv},
  year = {2026},
  month = jun,
  doi = {10.48550/arxiv.2606.31863},
  eprint = {2606.31863},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.31863},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Most Properties are Undecidable for Transitive Tense Logics
AU  - Qian Chen
AU  - Tenyo Takahashi
PY  - 2026
DA  - 2026/06/30
PB  - arXiv
DO  - 10.48550/arxiv.2606.31863
UR  - https://arxiv.org/abs/2606.31863
AB  - A logics' property is decidable in a class of logics if there exists an algorithm that decides whether a finitely axiomatizable logic in the class has the property. Many properties are undecidable for bimodal logics but decidable for linear tense logics, which leads to a general question on how the interactions of modalities affect the decidability of properties. In this paper, we study the decidability of properties for transitive tense logics and show that most properties are undecidable in the lattice NExt(K4t) of transitive tense logics, including Kripke completeness, the finite model property, and decidability. Our proof method adapts Chagrov's approach of constructing a reduction from an undecidable problem of Minsky machines to the decision problem for logics' properties, yielding a general scheme of proving the undecidability of these properties.
ER  -