Name
Abstract | ||
|---|---|---|
. We study the modal logic M L
r
of the countable random frame, which is contained in and `approximates' the modal logic of almost sure frame validity, i.e.
the logic of those modal principles which are valid with asymptotic probability 1 in a randomly chosen finite frame. We give
a sound and complete axiomatization of M L
r
and show that it is not finitely axiomatizable. Then we describe the finite frames of that logic and show that it has the
finite frame property and its satisfiability problem is in EXPTIME. All these results easily extend to temporal and other
multi-modal logics. Finally, we show that there are modal formulas which are almost surely valid in the finite, yet fail in
the countable random frame, and hence do not follow from the extension axioms. Therefore the analog of Fagin's transfer theorem
for almost sure validity in first-order logic fails for modal logic. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/s001530100135 | Arch. Math. Log. |
Keywords | Field | DocType |
completeness,modal logic,first order logic,satisfiability | Modal μ-calculus,Discrete mathematics,Normal modal logic,Accessibility relation,Multimodal logic,Modal logic,Dynamic logic (modal logic),Intermediate logic,Mathematics,S5 | Journal |
Volume | Issue | ISSN |
42 | 3 | 0933-5846 |
Citations | PageRank | References |
2 | 0.38 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Valentin Goranko | 1 | 1245 | 97.90 |
| Bruce M. Kapron | 2 | 308 | 26.02 |