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 N1099f83e6dc64291a26aaa1d20ce92aa
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 N406195638e7f48e7a5582802bc0a68ae
25 N4b1fde6980b740cd803c217908572d7f
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 N879e939865f242ffb98656df49883d36
30 N924aa28707974bab88bf532adbd3690e
31 Nd7880504b2ac48b7a26dda284cbb63a0
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 Ne8a376d2a731442a944dad6dc1f4611d
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 N1099f83e6dc64291a26aaa1d20ce92aa rdf:first sg:person.011152672013.96
42 rdf:rest Nf5f438e4a1d84ca2ac78e3432c2d1b55
43 N2410b7c474f0481c9796a9db594171f4 schema:affiliation https://www.grid.ac/institutes/grid.18763.3b
44 schema:familyName Sánchez
45 schema:givenName M. G.
46 rdf:type schema:Person
47 N406195638e7f48e7a5582802bc0a68ae schema:issueNumber 3
48 rdf:type schema:PublicationIssue
49 N4b1fde6980b740cd803c217908572d7f schema:volumeNumber 96
50 rdf:type schema:PublicationVolume
51 N879e939865f242ffb98656df49883d36 schema:name dimensions_id
52 schema:value pub.1100166290
53 rdf:type schema:PropertyValue
54 N924aa28707974bab88bf532adbd3690e schema:name doi
55 schema:value 10.1134/s1064562417060242
56 rdf:type schema:PropertyValue
57 Nd7880504b2ac48b7a26dda284cbb63a0 schema:name readcube_id
58 schema:value b99a7869722155c754a62b034d382f802dc66470096e400d2dfa92f88c2f00cf
59 rdf:type schema:PropertyValue
60 Ne8a376d2a731442a944dad6dc1f4611d schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 Nf5f438e4a1d84ca2ac78e3432c2d1b55 rdf:first N2410b7c474f0481c9796a9db594171f4
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)


...