On computing majority by comparisons View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1991-12

AUTHORS

Michael E. Saks, Michael Werman

ABSTRACT

The elements of a finite setX (of odd cardinalityn) are divided into two (as yet unknown) classes and a member of the larger class is to be identified. The basic operation is to test whether two objects are in the same class. We show thatn-B(n) comparisons are necessary and sufficient in worst case, whereB(n) is the number of 1's in the binary expansion ofn. More... »

PAGES

383-387

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01275672

DOI

http://dx.doi.org/10.1007/bf01275672

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Bell Communications Research, 07960, Morristown, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.432790.b", 
          "name": [
            "Department of Mathematics and RUTCOR, Rutgers University, 08903, New Brunswick, NJ", 
            "Bell Communications Research, 07960, Morristown, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael E.", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute for Mathematics and its Applications, University of Minnesota, 55455, Minneapolis, Minn, USA", 
          "id": "http://www.grid.ac/institutes/grid.17635.36", 
          "name": [
            "Institute for Mathematics and its Applications, University of Minnesota, 55455, Minneapolis, Minn, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Werman", 
        "givenName": "Michael", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-1-4612-9967-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042660971", 
          "https://doi.org/10.1007/978-1-4612-9967-7"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1991-12", 
    "datePublishedReg": "1991-12-01", 
    "description": "The elements of a finite setX (of odd cardinalityn) are divided into two (as yet unknown) classes and a member of the larger class is to be identified. The basic operation is to test whether two objects are in the same class. We show thatn-B(n) comparisons are necessary and sufficient in worst case, whereB(n) is the number of 1's in the binary expansion ofn.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01275672", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "11"
      }
    ], 
    "keywords": [
      "majority", 
      "cases", 
      "comparison", 
      "members", 
      "SETX", 
      "number", 
      "class", 
      "same class", 
      "operation", 
      "expansion", 
      "thatn", 
      "finite setX", 
      "elements", 
      "binary expansion", 
      "objects", 
      "worst case", 
      "large class", 
      "basic operations"
    ], 
    "name": "On computing majority by comparisons", 
    "pagination": "383-387", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001435218"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01275672"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01275672", 
      "https://app.dimensions.ai/details/publication/pub.1001435218"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-11-24T20:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_244.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01275672"
  }
]
 

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.1007/bf01275672'

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.1007/bf01275672'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01275672'

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

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


 

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

89 TRIPLES      21 PREDICATES      44 URIs      35 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01275672 schema:about anzsrc-for:01
2 anzsrc-for:08
3 schema:author Nc272319e15bb4cc683477bb1a8cbf9b5
4 schema:citation sg:pub.10.1007/978-1-4612-9967-7
5 schema:datePublished 1991-12
6 schema:datePublishedReg 1991-12-01
7 schema:description The elements of a finite setX (of odd cardinalityn) are divided into two (as yet unknown) classes and a member of the larger class is to be identified. The basic operation is to test whether two objects are in the same class. We show thatn-B(n) comparisons are necessary and sufficient in worst case, whereB(n) is the number of 1's in the binary expansion ofn.
8 schema:genre article
9 schema:isAccessibleForFree false
10 schema:isPartOf N4623023312bf4a9595877c8c813bb65c
11 N633c2068ad704df899a324a0b62a5e50
12 sg:journal.1136493
13 schema:keywords SETX
14 basic operations
15 binary expansion
16 cases
17 class
18 comparison
19 elements
20 expansion
21 finite setX
22 large class
23 majority
24 members
25 number
26 objects
27 operation
28 same class
29 thatn
30 worst case
31 schema:name On computing majority by comparisons
32 schema:pagination 383-387
33 schema:productId N29d6acaa426f4181b2c318a8baf7f61e
34 Nc2f92d814bab4b7e8a2e06baaef0bce8
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001435218
36 https://doi.org/10.1007/bf01275672
37 schema:sdDatePublished 2022-11-24T20:47
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N4b87d07caeb646499e720e8e4fb741a3
40 schema:url https://doi.org/10.1007/bf01275672
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N29d6acaa426f4181b2c318a8baf7f61e schema:name dimensions_id
45 schema:value pub.1001435218
46 rdf:type schema:PropertyValue
47 N4623023312bf4a9595877c8c813bb65c schema:volumeNumber 11
48 rdf:type schema:PublicationVolume
49 N488bd4ffbd2b4df5b63b3720a81b3f93 rdf:first Nc9d07c5d95fe453cab081c9529ce3800
50 rdf:rest rdf:nil
51 N4b87d07caeb646499e720e8e4fb741a3 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 N633c2068ad704df899a324a0b62a5e50 schema:issueNumber 4
54 rdf:type schema:PublicationIssue
55 Nc272319e15bb4cc683477bb1a8cbf9b5 rdf:first sg:person.011520224512.05
56 rdf:rest N488bd4ffbd2b4df5b63b3720a81b3f93
57 Nc2f92d814bab4b7e8a2e06baaef0bce8 schema:name doi
58 schema:value 10.1007/bf01275672
59 rdf:type schema:PropertyValue
60 Nc9d07c5d95fe453cab081c9529ce3800 schema:affiliation grid-institutes:grid.17635.36
61 schema:familyName Werman
62 schema:givenName Michael
63 rdf:type schema:Person
64 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
65 schema:name Mathematical Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
68 schema:name Information and Computing Sciences
69 rdf:type schema:DefinedTerm
70 sg:journal.1136493 schema:issn 0209-9683
71 1439-6912
72 schema:name Combinatorica
73 schema:publisher Springer Nature
74 rdf:type schema:Periodical
75 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.432790.b
76 schema:familyName Saks
77 schema:givenName Michael E.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
79 rdf:type schema:Person
80 sg:pub.10.1007/978-1-4612-9967-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042660971
81 https://doi.org/10.1007/978-1-4612-9967-7
82 rdf:type schema:CreativeWork
83 grid-institutes:grid.17635.36 schema:alternateName Institute for Mathematics and its Applications, University of Minnesota, 55455, Minneapolis, Minn, USA
84 schema:name Institute for Mathematics and its Applications, University of Minnesota, 55455, Minneapolis, Minn, USA
85 rdf:type schema:Organization
86 grid-institutes:grid.432790.b schema:alternateName Bell Communications Research, 07960, Morristown, NJ, USA
87 schema:name Bell Communications Research, 07960, Morristown, NJ, USA
88 Department of Mathematics and RUTCOR, Rutgers University, 08903, New Brunswick, NJ
89 rdf:type schema:Organization
 




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


...