Logical laws for existential monadic second-order sentences with infinite first-order parts View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2017-11

AUTHORS

M. E. Zhukovskii, M. G. Sánchez

ABSTRACT

We consider existential monadic second-order sentences ∃X φ(X) about undirected graphs, where ∃X is a finite sequence of monadic quantifiers and φ(X) ∈ +∞ωω is an infinite first-order formula. We prove that there exists a sentence (in the considered logic) with two monadic variables and two first-order variables such that the probability that it is true on G(n, p) does not converge. Moreover, such an example is also obtained for one monadic variable and three first-order variables. More... »

PAGES

598-600

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1134/s1064562417060242

DOI

http://dx.doi.org/10.1134/s1064562417060242

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1100166290


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Peoples' Friendship University of Russia", 
          "id": "https://www.grid.ac/institutes/grid.77642.30", 
          "name": [
            "Moscow Institute of Physics and Technology (State University), 141700, Dolgoprudnyi, Moscow oblast, Russia", 
            "RUDN University, 117198, Moscow, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhukovskii", 
        "givenName": "M. E.", 
        "id": "sg:person.011152672013.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Moscow Institute of Physics and Technology", 
          "id": "https://www.grid.ac/institutes/grid.18763.3b", 
          "name": [
            "Moscow Institute of Physics and Technology (State University), 141700, Dolgoprudnyi, Moscow oblast, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "S\u00e1nchez", 
        "givenName": "M. G.", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0012-365x(85)90112-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001660461"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(85)90112-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001660461"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0020-0190(00)00149-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005361722"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0890-5401(92)90021-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015733979"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(91)90048-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016519488"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-04538-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020409190", 
          "https://doi.org/10.1007/978-3-662-04538-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-04538-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020409190", 
          "https://doi.org/10.1007/978-3-662-04538-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0022481200051756", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033388216"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2012.01.018", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034255554"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-07003-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046929489", 
          "https://doi.org/10.1007/978-3-662-07003-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-07003-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046929489", 
          "https://doi.org/10.1007/978-3-662-07003-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1070/rm2015v070n01abeh004936", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1058198484"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1134/s1064562417010227", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084938833", 
          "https://doi.org/10.1134/s1064562417010227"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/dimacs/033", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1097022566"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511814068", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098699402"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1106884102", 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/9781118032718", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1106884102"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2017-11", 
    "datePublishedReg": "2017-11-01", 
    "description": "We consider existential monadic second-order sentences \u2203X \u03c6(X) about undirected graphs, where \u2203X is a finite sequence of monadic quantifiers and \u03c6(X) \u2208 +\u221e\u03c9\u03c9 is an infinite first-order formula. We prove that there exists a sentence (in the considered logic) with two monadic variables and two first-order variables such that the probability that it is true on G(n, p) does not converge. Moreover, such an example is also obtained for one monadic variable and three first-order variables.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1134/s1064562417060242", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136704", 
        "issn": [
          "1064-5624", 
          "1531-8362"
        ], 
        "name": "Doklady Mathematics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "96"
      }
    ], 
    "name": "Logical laws for existential monadic second-order sentences with infinite first-order parts", 
    "pagination": "598-600", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b99a7869722155c754a62b034d382f802dc66470096e400d2dfa92f88c2f00cf"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1134/s1064562417060242"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1100166290"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1134/s1064562417060242", 
      "https://app.dimensions.ai/details/publication/pub.1100166290"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T17:44", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8672_00000603.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1134/S1064562417060242"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1134/s1064562417060242'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1134/s1064562417060242'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1134/s1064562417060242'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1134/s1064562417060242'


 

This table displays all metadata directly associated to this object as RDF triples.

115 TRIPLES      21 PREDICATES      41 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1134/s1064562417060242 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N67215b3f15e74f73a1c420da4614dc4f
4 schema:citation sg:pub.10.1007/978-3-662-04538-1
5 sg:pub.10.1007/978-3-662-07003-1
6 sg:pub.10.1134/s1064562417010227
7 https://app.dimensions.ai/details/publication/pub.1106884102
8 https://doi.org/10.1002/9781118032718
9 https://doi.org/10.1016/0012-365x(85)90112-8
10 https://doi.org/10.1016/0166-218x(91)90048-2
11 https://doi.org/10.1016/0890-5401(92)90021-7
12 https://doi.org/10.1016/j.disc.2012.01.018
13 https://doi.org/10.1016/s0020-0190(00)00149-6
14 https://doi.org/10.1017/cbo9780511814068
15 https://doi.org/10.1017/s0022481200051756
16 https://doi.org/10.1070/rm2015v070n01abeh004936
17 https://doi.org/10.1090/dimacs/033
18 schema:datePublished 2017-11
19 schema:datePublishedReg 2017-11-01
20 schema:description We consider existential monadic second-order sentences ∃X φ(X) about undirected graphs, where ∃X is a finite sequence of monadic quantifiers and φ(X) ∈ +∞ωω is an infinite first-order formula. We prove that there exists a sentence (in the considered logic) with two monadic variables and two first-order variables such that the probability that it is true on G(n, p) does not converge. Moreover, such an example is also obtained for one monadic variable and three first-order variables.
21 schema:genre research_article
22 schema:inLanguage en
23 schema:isAccessibleForFree false
24 schema:isPartOf N144635ccc4c14271a3a6ac9e03b9d514
25 Nbd81714b8d6b4b27b07dc501e5e283c6
26 sg:journal.1136704
27 schema:name Logical laws for existential monadic second-order sentences with infinite first-order parts
28 schema:pagination 598-600
29 schema:productId N07ece9dd05c243729df1c0acb845ccf6
30 N39ca9de686f04c1b9f151e0a72f0acba
31 N61cc48577ef0489b95294652ff8f3cc9
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100166290
33 https://doi.org/10.1134/s1064562417060242
34 schema:sdDatePublished 2019-04-10T17:44
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher Nc9b64522912640dbacf6f2170d878339
37 schema:url http://link.springer.com/10.1134/S1064562417060242
38 sgo:license sg:explorer/license/
39 sgo:sdDataset articles
40 rdf:type schema:ScholarlyArticle
41 N07ece9dd05c243729df1c0acb845ccf6 schema:name doi
42 schema:value 10.1134/s1064562417060242
43 rdf:type schema:PropertyValue
44 N144635ccc4c14271a3a6ac9e03b9d514 schema:issueNumber 3
45 rdf:type schema:PublicationIssue
46 N39ca9de686f04c1b9f151e0a72f0acba schema:name readcube_id
47 schema:value b99a7869722155c754a62b034d382f802dc66470096e400d2dfa92f88c2f00cf
48 rdf:type schema:PropertyValue
49 N61cc48577ef0489b95294652ff8f3cc9 schema:name dimensions_id
50 schema:value pub.1100166290
51 rdf:type schema:PropertyValue
52 N67215b3f15e74f73a1c420da4614dc4f rdf:first sg:person.011152672013.96
53 rdf:rest Nda7e7a1b9eb34d169aff305d2732724b
54 Nbd81714b8d6b4b27b07dc501e5e283c6 schema:volumeNumber 96
55 rdf:type schema:PublicationVolume
56 Nc9b64522912640dbacf6f2170d878339 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 Nd2b3a030d80a40beb1efcc3e6758d2a7 schema:affiliation https://www.grid.ac/institutes/grid.18763.3b
59 schema:familyName Sánchez
60 schema:givenName M. G.
61 rdf:type schema:Person
62 Nda7e7a1b9eb34d169aff305d2732724b rdf:first Nd2b3a030d80a40beb1efcc3e6758d2a7
63 rdf:rest rdf:nil
64 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
65 schema:name Mathematical Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
68 schema:name Pure Mathematics
69 rdf:type schema:DefinedTerm
70 sg:journal.1136704 schema:issn 1064-5624
71 1531-8362
72 schema:name Doklady Mathematics
73 rdf:type schema:Periodical
74 sg:person.011152672013.96 schema:affiliation https://www.grid.ac/institutes/grid.77642.30
75 schema:familyName Zhukovskii
76 schema:givenName M. E.
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
78 rdf:type schema:Person
79 sg:pub.10.1007/978-3-662-04538-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020409190
80 https://doi.org/10.1007/978-3-662-04538-1
81 rdf:type schema:CreativeWork
82 sg:pub.10.1007/978-3-662-07003-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046929489
83 https://doi.org/10.1007/978-3-662-07003-1
84 rdf:type schema:CreativeWork
85 sg:pub.10.1134/s1064562417010227 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084938833
86 https://doi.org/10.1134/s1064562417010227
87 rdf:type schema:CreativeWork
88 https://app.dimensions.ai/details/publication/pub.1106884102 schema:CreativeWork
89 https://doi.org/10.1002/9781118032718 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106884102
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1016/0012-365x(85)90112-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001660461
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1016/0166-218x(91)90048-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016519488
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1016/0890-5401(92)90021-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015733979
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/j.disc.2012.01.018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034255554
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/s0020-0190(00)00149-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005361722
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1017/cbo9780511814068 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098699402
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1017/s0022481200051756 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033388216
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1070/rm2015v070n01abeh004936 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058198484
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1090/dimacs/033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1097022566
108 rdf:type schema:CreativeWork
109 https://www.grid.ac/institutes/grid.18763.3b schema:alternateName Moscow Institute of Physics and Technology
110 schema:name Moscow Institute of Physics and Technology (State University), 141700, Dolgoprudnyi, Moscow oblast, Russia
111 rdf:type schema:Organization
112 https://www.grid.ac/institutes/grid.77642.30 schema:alternateName Peoples' Friendship University of Russia
113 schema:name Moscow Institute of Physics and Technology (State University), 141700, Dolgoprudnyi, Moscow oblast, Russia
114 RUDN University, 117198, Moscow, Russia
115 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...