Zero-one laws for modal logic
type: Item
instance of: scholarly article
title: Zero-one laws for modal logic
zbMATH Open document ID: 0811.03012
author: Joseph Y. Halpern
author: Bruce M. Kapron
published in: Annals of Pure and Applied Logic
publication date: 1994-11-08T00:00:00Z
review text: It is shown that a 0-1 law holds for propositional modal logic, both for structure validity and frame validity. The problem of deciding whether a formula is almost-surely frame valid is \(\text{P}^{\text{NP}}\), the corresponding decision problem for frame validity is hard for deterministic exponential time. The relationship to 0-1 laws for fragments of second-order logic is discussed in detail.
reviewed by: Jörg Flum
Mathematics Subject Classification ID: 03B45
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B15
zbMATH DE Number: 683706
zbMATH Keywords: zero-one laws
zbMATH Keywords: propositional modal logic
zbMATH Keywords: structure validity
zbMATH Keywords: frame validity
zbMATH Keywords: fragments of second-order logic
MaRDI profile type: Publication
full work available at URL: 0168-0072(94)90084-1
OpenAlex ID: W2061689655
DOI: 10.1016/0168-0072(94)90084-1
DOI: 10.1016/S0168-0072(02)00111-2
Recommended article: Infinitary logics and 0-1 laws
Recommended article: A zero-one law for logic with a fixed-point operator
Recommended article: Post complete and 0-axiomatizable modal logics
Recommended article: Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
Recommended article: Zero-one law for an extension of first-order predicate language
Recommended article: Modal logic and invariance
Recommended article: Modal Fixed Point Logics
Recommended article: Q3762286
Recommended article: The zero-one law for the many-sorted logic of the first order predicates
Recommended article: Modal logic
description: scientific article; zbMATH DE number 683706