Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Logical properties of random graphs from small addable classes

Uproszczony widok
dc.abstract.enWe establish zero-one laws and convergence laws for monadic second-order logic (MSO) (and, a fortiori, first-order logic) on a number of interesting graph classes. In particular, we show that MSO obeys a zero-one law on the class of connected planar graphs, the class of connected graphs of tree-width at most k and the class of connected graphs excluding the k-clique as a minor. In each of these cases, dropping the connectivity requirement leads to a class where the zero-one law fails but a convergence law for MSO still holds.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorKopczyński, Eryk
dc.contributor.authorDawar, Anuj
dc.date.accessioned2024-01-25T05:13:43Z
dc.date.available2024-01-25T05:13:43Z
dc.date.issued2019
dc.description.financeNie dotyczy
dc.description.number3
dc.description.volume15
dc.identifier.doi10.23638/LMCS-15(3:4)2019
dc.identifier.issn1860-5974
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/111439
dc.identifier.weblinkhttps://lmcs.episciences.org/5644
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofLogical Methods in Computer Science
dc.relation.pages4:1–4:12
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleLogical properties of random graphs from small addable classes
dc.typeJournalArticle
dspace.entity.typePublication