𝔖 Bobbio Scriptorium
✦   LIBER   ✦

0–1 laws by preservation

✍ Scribed by Thierry Lacoste

Book ID
104326328
Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
612 KB
Volume
184
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Our central result asserts that a (logical) language preserved under extension of models has a O-l law under the uniform probability distribution. We then investigate some fragments of the first-order infinitary logic L,, and of second-order logic which are preserved under extension. This paper reveals new boundaries of O-1 laws for fragments of L,, and of second-order logic. The latter fragments are particularly interesting as they capture the prototypical complete problem for each level of the polynomial-time hierarchy.

📜 SIMILAR VOLUMES

0–1 laws for maps
0–1 laws for maps
✍ Edward A. Bender; Kevin J. Compton; L. Bruce Richmond 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB

A class of finite structures has a 0᎐1 law with respect to a logic if every property expressible in the logic has a probability approaching a limit of 0 or 1 as the Ž structure size grows. To formulate 0᎐1 laws for maps i.e., embeddings of graphs in a . surface , it is necessary to represent maps as

Submaps of maps. I. General 0–1 laws
Submaps of maps. I. General 0–1 laws
✍ Edward A Bender; Zhi-Cheng Gao; L.Bruce Richmond 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 756 KB