Convergence Laws for Very Sparse Random Structures with Generalized Quantifiers

✍ Scribed by Risto Kaila

• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 303 KB
• Volume: 48
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/1521-3870(200202)48:2<301::aid-malq301>3.0.co;2-z

✦ Synopsis

We prove convergence laws for logics of the form L ω ∞ω (Q), where Q is a properly chosen collection of generalized quantifiers, on very sparse finite random structures. We also study probabilistic collapsing of the logics L k ∞ω (Q), where Q is a collection of generalized quantifiers and k ∈ N+, under arbitrary probability measures of finite structures.