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

  • <error retrieving object. in <ERROR RETRIEVING OBJECT
  • 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-10-01T06:29", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_247.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 Nac8db2be0f6d40daad9fb6d121eb9c41
    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 Ndf079408b36e49539173f54c6d03ba50
    11 Ne8cbb6d12e044bba81e9292199c68cb2
    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 Nb189a97d0f0e492cabc2082d71fcb928
    34 Ndb61f0dbf07c4e4bb299b3c5ef9f72f7
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001435218
    36 https://doi.org/10.1007/bf01275672
    37 schema:sdDatePublished 2022-10-01T06:29
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher Nbd4af8a585514df1926b31b97a3c3e54
    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 N037fa70b247648aebd5c6b910991dc11 rdf:first N33650fa1a8944b0692fdb9a7f1c3b56d
    45 rdf:rest rdf:nil
    46 N33650fa1a8944b0692fdb9a7f1c3b56d schema:affiliation grid-institutes:grid.17635.36
    47 schema:familyName Werman
    48 schema:givenName Michael
    49 rdf:type schema:Person
    50 Nac8db2be0f6d40daad9fb6d121eb9c41 rdf:first sg:person.011520224512.05
    51 rdf:rest N037fa70b247648aebd5c6b910991dc11
    52 Nb189a97d0f0e492cabc2082d71fcb928 schema:name doi
    53 schema:value 10.1007/bf01275672
    54 rdf:type schema:PropertyValue
    55 Nbd4af8a585514df1926b31b97a3c3e54 schema:name Springer Nature - SN SciGraph project
    56 rdf:type schema:Organization
    57 Ndb61f0dbf07c4e4bb299b3c5ef9f72f7 schema:name dimensions_id
    58 schema:value pub.1001435218
    59 rdf:type schema:PropertyValue
    60 Ndf079408b36e49539173f54c6d03ba50 schema:issueNumber 4
    61 rdf:type schema:PublicationIssue
    62 Ne8cbb6d12e044bba81e9292199c68cb2 schema:volumeNumber 11
    63 rdf:type schema:PublicationVolume
    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)


    ...