Complexity of Łukasiewicz Modal Probabilistic Logics

2025/11/27 by Kozhemiachenko, Daniil, Sedlár, Igor
Computer Science · #Advanced Algebra and Logic #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Rough Sets and Fuzzy Logic

paper · doi:10.48550/arxiv.2511.22389

openalex publication_date 2025/11/27 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28

Abstract

Modal probabilistic logics provide a framework for reasoning about probability in modal contexts, involving notions such as knowledge, belief, time, and action. In this paper, we study a particular family of these logics, extending the modal Łukasiewicz many-valued logic. These logics are shown to be capable of expressing nuanced probabilistic concepts, including upper and lower probabilities. Our main contribution is a PSPACE-completeness result for two variants of the local consequence problem, providing a precise computational characterisation.

Citations

• Undecidability and non-axiomatizability of modal many-valued logics
• On Transitive modal many-valued logics
• Rational Lukasiewicz logic and DMV-algebras
• A Logic for Reasoning about Upper Probabilities
• Reasoning about Noisy Sensors and Effectors in the Situation Calculus
• Fuzzy Logic and Probability

Related

• Encoding de Finetti's coherence within Lukasiewicz logic and MV-algebras
• The Complexity of Probabilistic Justification Logic
• Reasoning Under the Principle of Maximum Entropy for Modal Logics K45,\n KD45, and S5
• Probabilistic Logic: Many-valuedness and Intensionality
• Modal Semantics for Reasoning with Probability and Uncertainty