Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/6685
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | PODDER, MOUMANTI | en_US |
dc.contributor.author | Zhukovskii, Maksim | en_US |
dc.date.accessioned | 2022-03-30T10:13:28Z | |
dc.date.available | 2022-03-30T10:13:28Z | |
dc.date.issued | 2022-04 | en_US |
dc.identifier.citation | ACM Transactions on Computational Logic, 23(2), 1-27. | en_US |
dc.identifier.issn | 1529-3785 | en_US |
dc.identifier.issn | 557-945X | en_US |
dc.identifier.uri | https://doi.org/10.1145/3489466 | en_US |
dc.identifier.uri | http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/6685 | |
dc.description.abstract | For any fixed positive integer k, let αk denote the smallest α ∈ (0,1) such that the random graph sequence {G(n, n-α)}n does not satisfy the zero-one law for the set εk of all existential first-order sentences that are of quantifier depth at most k. This article finds upper and lower bounds on αk, showing that as k → ∞, we have α k = (k - 2 - t(k))-1 for some function t(k) = Θ (k-2). We also establish the precise value of αk when k = 4. | en_US |
dc.language.iso | en | en_US |
dc.publisher | Association for Computing Machinery | en_US |
dc.subject | Existential first-order logic | en_US |
dc.subject | Zero-one laws | en_US |
dc.subject | Ehrenfeucht games | en_US |
dc.subject | Strictly balanced graphs | en_US |
dc.subject | Alpha-safe pairs | en_US |
dc.subject | Graph extension properties | en_US |
dc.subject | 2022-MAR-WEEK3 | en_US |
dc.subject | TOC-MAR-2022 | en_US |
dc.subject | 2022 | en_US |
dc.title | Zero-One Laws for Existential First-Order Sentences of Bounded Quantifier Depth | en_US |
dc.type | Article | en_US |
dc.contributor.department | Dept. of Mathematics | en_US |
dc.identifier.sourcetitle | ACM Transactions on Computational Logic | en_US |
dc.publication.originofpublisher | Foreign | en_US |
Appears in Collections: | JOURNAL ARTICLES |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.