0-1 laws and decision problems for fragments of second-order logic

DOI10.1016/0890-5401(90)90065-PzbMath0708.03004OpenAlexW2170743240MaRDI QIDQ920075

Phokion G. Kolaitis, Moshe Y. Vardi

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(90)90065-p

zbMATH Keywords

satisfiability problem0-1 lawcomplexity of decision problemsAckermann classfragments of existential second-order logic

Mathematics Subject Classification ID

Related Items (18)

Logical properties of random graphs from small addable classes ⋮ Finitistic proofs of 0-1 laws for fragments of second-order logic ⋮ Normal forms for second-order logic over finite structures, and classification of NP optimization problems ⋮ 0-1 laws by preservation ⋮ On the Decision Problem for Two-Variable First-Order Logic ⋮ Testable and untestable classes of first-order formulae ⋮ Satisfiability of formulae with one \(\forall\) is decidable in exponential time ⋮ Asymptotic conditional probabilities: The non-unary case ⋮ On the expressive power of counting ⋮ Infinitary logics and 0-1 laws ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ Finite-model theory -- A personal perspective ⋮ On the expressiveness of frame satisfiability and fragments of second-order logic ⋮ Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview ⋮ Zero-one law and definability of linear order ⋮ Strong extension axioms and Shelah's zero-one law for choiceless polynomial time ⋮ Relational Properties Expressible with One Universal Quantifier Are Testable ⋮ The 0-1 law fails for monadic existential second-order logic on undirected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On random models of finite power and monadic logic
• Complexity results for classes of quantificational formulas
• Alternation and the Ackermann case of the decision problem
• Hamiltonian circuits in random graphs
• Structure and complexity of relational queries
• The decision problem for the logic of predicates and of operations
• Random models and the Gödel case of the decision problem
• Complexity of the first-order theory of almost all finite structures
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• A zero-one law for logic with a fixed-point operator
• Relational queries computable in polynomial time
• On the Gödel class with identity
• Alternation
• The decision problem for standard classes
• Probabilities on finite models
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: 0-1 laws and decision problems for fragments of second-order logic