KIAM Main page Web Library  •  Publication Searh  Русский 

Article collection "Mathematical Problems of Cybernetics" №2, Moscow, 1989
Authors: Raţă M.F.
The undecidability of modal logic expressibility problem
The article deals with the expressibility problem in modal logics. We prove that there is no algorithm that can solve the expressibility problem for the S4 logic or the D* logic or any other modal logic that lies between those two. This implies that the logic S4, the logic D* and all intermediate modal logics are expressibility-wise undecidable. Also no extension of the S4 logic, besides locally tabular logics, is expressibility-wise decidable. Another major result of the article is the proof that a finitely axiomizable extension of the S4 logic is decidable if and only if it is a locally tabular logic.
mathematical logic, modal logics, expressibility problem, S4 logic, tabular logic
Publication language: russian,  pages: 29 (p. 71-99)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Raţă Metodie Fedorovich,  Институт математики и информатики АН Республики Молдова