## 0-1 Laws and Decision Problems for Fragments of Second-order LogicComputer Research Laboratory, University of California, Santa Cruz, 1989 - Logic, Symbolic and mathematical - 33 pages |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Common terms and phrases

0-1 law holds Ackermann class arities asymptotic probabilities atom(<p atomic formulas Bernays-Schonfinkel binomial distribution bounded vocabularies class E}(Ackermann class without equality clause composite symbols configuration consistent with t0 contain t0 containing the restriction countable random structure decision problem denote the formula encode existential second-order existential type existentially quantified exponential exponential hierarchy extending the type Fagin fi(P finite graphs finite satisfiability problem finite structures first-order logic first-order quantifier first-order sentences follows fragments Godel class infinitary logic input head input tape input(y Lemma lower bound NEXPTIME nondeterministic nondeterministic Turing machine nonrejecting computation NP-complete number of elements partial types predicate symbols prefix classes probability space Proof properly extending Proposition PSPACE-complete quantified variable quantifier-free formula restriction of t0 S)-existential type S)-type S)-witness second-order logic second-order sentences string subset tape of length Theorem truth values type t'(x unary relation underlying vocabulary universal quantifiers upper bounds wm,wm+i wm+i worktape xjt,y