Progress on Certifying Algorithms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Kurt Mehlhorn , Pascal Schweitzer

ABSTRACT

A certifying algorithm is an algorithm that produces with each output, a certificate or witness (easy-to-verify proof) that the particular output has not been compromised by a bug. A user of a certifying program P (= the implementation of a certifying algorithm) inputs x, receives an output y and a certificate w, and then checks, either manually or by use of a checking program, that w proves that y is a correct output for input x. In this way, he/she can be sure of the correctness of the output without having to trust P. We refer the reader to the recent survey paper [9] for a detailed discussion of certifying algorithms. More... »

PAGES

1-5

Book

TITLE

Frontiers in Algorithmics

ISBN

978-3-642-14552-0
978-3-642-14553-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14553-7_1

DOI

http://dx.doi.org/10.1007/978-3-642-14553-7_1

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schweitzer", 
        "givenName": "Pascal", 
        "id": "sg:person.010731762606.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010731762606.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "A certifying algorithm is an algorithm that produces with each output, a certificate or witness (easy-to-verify proof) that the particular output has not been compromised by a bug. A user of a certifying program P (= the implementation of a certifying algorithm) inputs x, receives an output y and a certificate w, and then checks, either manually or by use of a checking program, that w proves that y is a correct output for input x. In this way, he/she can be sure of the correctness of the output without having to trust P. We refer the reader to the recent survey paper\u00a0[9] for a detailed discussion of certifying algorithms.", 
    "editor": [
      {
        "familyName": "Lee", 
        "givenName": "Der-Tsai", 
        "type": "Person"
      }, 
      {
        "familyName": "Chen", 
        "givenName": "Danny Z.", 
        "type": "Person"
      }, 
      {
        "familyName": "Ying", 
        "givenName": "Shi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14553-7_1", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14552-0", 
        "978-3-642-14553-7"
      ], 
      "name": "Frontiers in Algorithmics", 
      "type": "Book"
    }, 
    "keywords": [
      "recent survey paper", 
      "survey paper", 
      "correct output", 
      "algorithm", 
      "input x", 
      "input x.", 
      "particular output", 
      "users", 
      "bugs", 
      "output y", 
      "correctness", 
      "output", 
      "certificates", 
      "detailed discussion", 
      "way", 
      "readers", 
      "use", 
      "program", 
      "progress", 
      "discussion", 
      "witness", 
      "paper"
    ], 
    "name": "Progress on Certifying Algorithms", 
    "pagination": "1-5", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024943971"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14553-7_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14553-7_1", 
      "https://app.dimensions.ai/details/publication/pub.1024943971"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T07:00", 
    "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/chapter/chapter_467.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-14553-7_1"
  }
]
 

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/978-3-642-14553-7_1'

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/978-3-642-14553-7_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14553-7_1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14553-7_1'


 

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

98 TRIPLES      22 PREDICATES      47 URIs      40 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14553-7_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N7d45fde95d634202aa748bc8b1abe602
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description A certifying algorithm is an algorithm that produces with each output, a certificate or witness (easy-to-verify proof) that the particular output has not been compromised by a bug. A user of a certifying program P (= the implementation of a certifying algorithm) inputs x, receives an output y and a certificate w, and then checks, either manually or by use of a checking program, that w proves that y is a correct output for input x. In this way, he/she can be sure of the correctness of the output without having to trust P. We refer the reader to the recent survey paper [9] for a detailed discussion of certifying algorithms.
7 schema:editor N7521954f155c42fdb224d7200c5e2280
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N1c4b5f61ddde40bd987e9685bbf19d5a
11 schema:keywords algorithm
12 bugs
13 certificates
14 correct output
15 correctness
16 detailed discussion
17 discussion
18 input x
19 input x.
20 output
21 output y
22 paper
23 particular output
24 program
25 progress
26 readers
27 recent survey paper
28 survey paper
29 use
30 users
31 way
32 witness
33 schema:name Progress on Certifying Algorithms
34 schema:pagination 1-5
35 schema:productId N71e54d33216b42c78c6b5918e0273220
36 N7da9926b5c67455d930b98dff607aea4
37 schema:publisher Nc8eda119fee548dca38885d20399b968
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024943971
39 https://doi.org/10.1007/978-3-642-14553-7_1
40 schema:sdDatePublished 2022-10-01T07:00
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher Ndea71f0ab3a94736940e535ecc3ce401
43 schema:url https://doi.org/10.1007/978-3-642-14553-7_1
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N1c4b5f61ddde40bd987e9685bbf19d5a schema:isbn 978-3-642-14552-0
48 978-3-642-14553-7
49 schema:name Frontiers in Algorithmics
50 rdf:type schema:Book
51 N3911d162291a4a50a5b825592305057e schema:familyName Ying
52 schema:givenName Shi
53 rdf:type schema:Person
54 N478aedaf71044e0e8641012c45f84ae0 rdf:first sg:person.010731762606.52
55 rdf:rest rdf:nil
56 N55d2294cd86b48aea499bcb0bdc03d7a rdf:first Ne52ff70c6fe24020860fc56792a31aae
57 rdf:rest N7dd69dd0ed9344168daa8fe4d2e651e6
58 N71e54d33216b42c78c6b5918e0273220 schema:name dimensions_id
59 schema:value pub.1024943971
60 rdf:type schema:PropertyValue
61 N7521954f155c42fdb224d7200c5e2280 rdf:first N8915ea8b67134ee18e80b785baf2e7d2
62 rdf:rest N55d2294cd86b48aea499bcb0bdc03d7a
63 N7d45fde95d634202aa748bc8b1abe602 rdf:first sg:person.011757371347.43
64 rdf:rest N478aedaf71044e0e8641012c45f84ae0
65 N7da9926b5c67455d930b98dff607aea4 schema:name doi
66 schema:value 10.1007/978-3-642-14553-7_1
67 rdf:type schema:PropertyValue
68 N7dd69dd0ed9344168daa8fe4d2e651e6 rdf:first N3911d162291a4a50a5b825592305057e
69 rdf:rest rdf:nil
70 N8915ea8b67134ee18e80b785baf2e7d2 schema:familyName Lee
71 schema:givenName Der-Tsai
72 rdf:type schema:Person
73 Nc8eda119fee548dca38885d20399b968 schema:name Springer Nature
74 rdf:type schema:Organisation
75 Ndea71f0ab3a94736940e535ecc3ce401 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 Ne52ff70c6fe24020860fc56792a31aae schema:familyName Chen
78 schema:givenName Danny Z.
79 rdf:type schema:Person
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 sg:person.010731762606.52 schema:affiliation grid-institutes:grid.419528.3
87 schema:familyName Schweitzer
88 schema:givenName Pascal
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010731762606.52
90 rdf:type schema:Person
91 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
92 schema:familyName Mehlhorn
93 schema:givenName Kurt
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
95 rdf:type schema:Person
96 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
97 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
98 rdf:type schema:Organization
 




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


...