Abstract
One can add the machinery of relation symbols and terms to a propositional modal logic without adding quantifiers. Ordinarily this is no extension beyond the propositional. But if terms are allowed to be non-rigid, a scoping mechanism (usually written using lambda abstraction) must also be introduced to avoid ambiguity. Since quantifiers are not present, this is not really a first-order logic, but it is not exactly propositional either. I will show that for propositional logics such as K, T and D, adding such machinery produces a decidable logic, but adding it to logics between K4 and S5 produces an undecidable one. (Transitivity is the villain here.) The proof of undecidability consists of showing that classical first-order logic can be embedded.

ASTEC seminar
January 12, 2001, 10.30

Place: Information technology, Uppsala University
Room: 1510
Time: 10.30

Help on how to find ASTEC seminars.