0-1 laws and decision problems for fragments of second-order logic
type: Item
instance of: scholarly article
title: 0-1 laws and decision problems for fragments of second-order logic
zbMATH Open document ID: 0708.03004
DOI: 10.1016/0890-5401(90)90065-P
author: Phokion G. Kolaitis
author: Moshe Y. Vardi
published in: Information and Computation
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4162851
zbMATH Keywords: complexity of decision problems
zbMATH Keywords: fragments of existential second-order logic
zbMATH Keywords: Ackermann class
zbMATH Keywords: 0-1 law
zbMATH Keywords: satisfiability problem
MaRDI profile type: Publication
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: A zero-one law for logic with a fixed-point operator
cites work: Q3682518
cites work: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
cites work: Structure and complexity of relational queries
cites work: Alternation
cites work: Q4918393
cites work: Q3905252
cites work: Q4058132
cites work: Probabilities on finite models
cites work: Alternation and the Ackermann case of the decision problem
cites work: Q4198056
cites work: On the Gödel class with identity
cites work: Complexity of the first-order theory of almost all finite structures
cites work: The decision problem for the logic of predicates and of operations
cites work: The decision problem for standard classes
cites work: Q3758820
cites work: Random models and the Gödel case of the decision problem
cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME
cites work: Relational queries computable in polynomial time
cites work: On random models of finite power and monadic logic
cites work: Q3856727
cites work: Complexity results for classes of quantificational formulas
cites work: Hamiltonian circuits in random graphs
cites work: Q5797034
full work available at URL: 0890-5401(90)90065-p
OpenAlex ID: W2170743240
description: scientific article; zbMATH DE number 4162851