Stay Informed:
Baskin Engineering COVID-19 Information and Resources
Campus Roadmap to Recovery
Zoom Links: Zoom Help | Teaching with Zoom | Zoom Quick Guide

UCSC-CRL-90-06: 0-1 LAWS FOR INFINITARY LOGICS

03/01/1990 09:00 AM
Computer Science
We investigate asymptotic probabilities of properties expressible in the infinitary logic L^omega_{infinity omega} on finite structures. Sentences in this logic may have arbitrary disjunctions and conjunctions, but they involve only a finite number of distinct variables. We show that the 0-1 law holds for L^omega_{infinity omega}, i.e., the asymptotic probability of every sentence in this logic exists and is equal to either 0 or 1. This result subsumes earlier work on asymptotic probabilities for various fixpoint logics and reveals the boundary of 0-1 laws for infinitary logics.

This report is not available for download at this time.