Quantifier Alternation in First-Order Formulas with Infinite Spectra View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2017-04-15

AUTHORS

M. E. Zhukovskii

ABSTRACT

The spectrum of a first-order formula is the set of numbers α such that for a random graph in a binomial model where the edge probability is a power function of the number of graph vertices with exponent −α the truth probability of this formula does not tend to either zero or one. In 1990 J. Spenser proved that there exists a first-order formula with an infinite spectrum. We have proved that the minimum quantifier depth of a first-order formula with an infinite spectrum is either 4 or 5. In the present paper we find a wide class of first-order formulas of depth 4 with finite spectra and also prove that the minimum quantifier alternation number for a first-order formula with an infinite spectrum is 3. More... »

PAGES

391-403

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0805", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Distributed Computing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Communications Technologies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Derzhavin Tambov State University, Tambov, Russia", 
          "id": "http://www.grid.ac/institutes/grid.446191.f", 
          "name": [
            "Derzhavin Tambov State University, Tambov, 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"
      }
    ], 
    "citation": [
      {
        "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/bf02122699", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004686170", 
          "https://doi.org/10.1007/bf02122699"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2017-04-15", 
    "datePublishedReg": "2017-04-15", 
    "description": "The spectrum of a first-order formula is the set of numbers \u03b1 such that for a random graph in a binomial model where the edge probability is a power function of the number of graph vertices with exponent \u2212\u03b1 the truth probability of this formula does not tend to either zero or one. In 1990 J. Spenser proved that there exists a first-order formula with an infinite spectrum. We have proved that the minimum quantifier depth of a first-order formula with an infinite spectrum is either 4 or 5. In the present paper we find a wide class of first-order formulas of depth 4 with finite spectra and also prove that the minimum quantifier alternation number for a first-order formula with an infinite spectrum is 3.", 
    "genre": "article", 
    "id": "sg:pub.10.1134/s003294601704007x", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136386", 
        "issn": [
          "0555-2923", 
          "0032-9460"
        ], 
        "name": "Problems of Information Transmission", 
        "publisher": "Pleiades Publishing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "53"
      }
    ], 
    "keywords": [
      "infinite spectrum", 
      "first-order formulas", 
      "edge probability", 
      "minimum quantifier depth", 
      "random graphs", 
      "wide class", 
      "finite spectrum", 
      "number \u03b1", 
      "binomial model", 
      "graph vertices", 
      "order formulas", 
      "truth probability", 
      "formula", 
      "power function", 
      "quantifier depth", 
      "probability", 
      "present paper", 
      "quantifier alternations", 
      "graph", 
      "exponent", 
      "class", 
      "set", 
      "vertices", 
      "model", 
      "number", 
      "function", 
      "depth 4", 
      "spectra", 
      "alternation", 
      "depth", 
      "paper", 
      "Spenser", 
      "minimum quantifier alternation number", 
      "quantifier alternation number", 
      "alternation number"
    ], 
    "name": "Quantifier Alternation in First-Order Formulas with Infinite Spectra", 
    "pagination": "391-403", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1100858900"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1134/s003294601704007x"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1134/s003294601704007x", 
      "https://app.dimensions.ai/details/publication/pub.1100858900"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-12-01T19:38", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_723.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1134/s003294601704007x"
  }
]
 

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/s003294601704007x'

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/s003294601704007x'

Turtle is a human-readable linked data format.

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

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

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


 

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

113 TRIPLES      22 PREDICATES      65 URIs      52 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1134/s003294601704007x schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0805
4 anzsrc-for:10
5 anzsrc-for:1005
6 schema:author N21e1aa6291ae458c86be4977406d47f2
7 schema:citation sg:pub.10.1007/978-3-662-04538-1
8 sg:pub.10.1007/bf02122699
9 schema:datePublished 2017-04-15
10 schema:datePublishedReg 2017-04-15
11 schema:description The spectrum of a first-order formula is the set of numbers α such that for a random graph in a binomial model where the edge probability is a power function of the number of graph vertices with exponent −α the truth probability of this formula does not tend to either zero or one. In 1990 J. Spenser proved that there exists a first-order formula with an infinite spectrum. We have proved that the minimum quantifier depth of a first-order formula with an infinite spectrum is either 4 or 5. In the present paper we find a wide class of first-order formulas of depth 4 with finite spectra and also prove that the minimum quantifier alternation number for a first-order formula with an infinite spectrum is 3.
12 schema:genre article
13 schema:inLanguage en
14 schema:isAccessibleForFree false
15 schema:isPartOf N0aae22e2a2cc45f596e16ab89a712d89
16 N373b409b686a407792d65f692e31611e
17 sg:journal.1136386
18 schema:keywords Spenser
19 alternation
20 alternation number
21 binomial model
22 class
23 depth
24 depth 4
25 edge probability
26 exponent
27 finite spectrum
28 first-order formulas
29 formula
30 function
31 graph
32 graph vertices
33 infinite spectrum
34 minimum quantifier alternation number
35 minimum quantifier depth
36 model
37 number
38 number α
39 order formulas
40 paper
41 power function
42 present paper
43 probability
44 quantifier alternation number
45 quantifier alternations
46 quantifier depth
47 random graphs
48 set
49 spectra
50 truth probability
51 vertices
52 wide class
53 schema:name Quantifier Alternation in First-Order Formulas with Infinite Spectra
54 schema:pagination 391-403
55 schema:productId N07004081395844cab1b1b57b9401c517
56 Ndc6daa2de62e494e89b786c8b8145975
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100858900
58 https://doi.org/10.1134/s003294601704007x
59 schema:sdDatePublished 2021-12-01T19:38
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N13de9a3800b14cfda71978ab9a6e2b92
62 schema:url https://doi.org/10.1134/s003294601704007x
63 sgo:license sg:explorer/license/
64 sgo:sdDataset articles
65 rdf:type schema:ScholarlyArticle
66 N07004081395844cab1b1b57b9401c517 schema:name dimensions_id
67 schema:value pub.1100858900
68 rdf:type schema:PropertyValue
69 N0aae22e2a2cc45f596e16ab89a712d89 schema:issueNumber 4
70 rdf:type schema:PublicationIssue
71 N13de9a3800b14cfda71978ab9a6e2b92 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N21e1aa6291ae458c86be4977406d47f2 rdf:first sg:person.011152672013.96
74 rdf:rest rdf:nil
75 N373b409b686a407792d65f692e31611e schema:volumeNumber 53
76 rdf:type schema:PublicationVolume
77 Ndc6daa2de62e494e89b786c8b8145975 schema:name doi
78 schema:value 10.1134/s003294601704007x
79 rdf:type schema:PropertyValue
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
87 schema:name Distributed Computing
88 rdf:type schema:DefinedTerm
89 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
90 schema:name Technology
91 rdf:type schema:DefinedTerm
92 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
93 schema:name Communications Technologies
94 rdf:type schema:DefinedTerm
95 sg:journal.1136386 schema:issn 0032-9460
96 0555-2923
97 schema:name Problems of Information Transmission
98 schema:publisher Pleiades Publishing
99 rdf:type schema:Periodical
100 sg:person.011152672013.96 schema:affiliation grid-institutes:grid.446191.f
101 schema:familyName Zhukovskii
102 schema:givenName M. E.
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
104 rdf:type schema:Person
105 sg:pub.10.1007/978-3-662-04538-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020409190
106 https://doi.org/10.1007/978-3-662-04538-1
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/bf02122699 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004686170
109 https://doi.org/10.1007/bf02122699
110 rdf:type schema:CreativeWork
111 grid-institutes:grid.446191.f schema:alternateName Derzhavin Tambov State University, Tambov, Russia
112 schema:name Derzhavin Tambov State University, Tambov, Russia
113 rdf:type schema:Organization
 




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


...