Context-Sensitive Dynamic Partial Order Reduction View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2017-07-13

AUTHORS

Elvira Albert , Puri Arenas , María García de la Banda , Miguel Gómez-Zamalloa , Peter J. Stuckey

ABSTRACT

Dynamic Partial Order Reduction (DPOR) is a powerful technique used in verification and testing to reduce the number of equivalent executions explored. Two executions are equivalent if they can be obtained from each other by swapping adjacent, non-conflicting (independent) execution steps. Existing DPOR algorithms rely on a notion of independence that is context-insensitive, i.e., the execution steps must be independent in all contexts. In practice, independence is often proved by just checking no execution step writes on a shared variable. We present context-sensitive DPOR, an extension of DPOR that uses context-sensitive independence, where two steps might be independent only in the particular context explored. We show theoretically and experimentally how context-sensitive DPOR can achieve exponential gains. More... »

PAGES

526-543

Book

TITLE

Computer Aided Verification

ISBN

978-3-319-63386-2
978-3-319-63387-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-63387-9_26

DOI

http://dx.doi.org/10.1007/978-3-319-63387-9_26

DIMENSIONS

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


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/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "DSIC, Complutense University of Madrid, Madrid, Spain", 
          "id": "http://www.grid.ac/institutes/grid.4795.f", 
          "name": [
            "DSIC, Complutense University of Madrid, Madrid, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Albert", 
        "givenName": "Elvira", 
        "id": "sg:person.011201007213.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011201007213.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DSIC, Complutense University of Madrid, Madrid, Spain", 
          "id": "http://www.grid.ac/institutes/grid.4795.f", 
          "name": [
            "DSIC, Complutense University of Madrid, Madrid, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Arenas", 
        "givenName": "Puri", 
        "id": "sg:person.015245434275.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015245434275.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IMDEA Software Institute, Madrid, Spain", 
          "id": "http://www.grid.ac/institutes/grid.482873.2", 
          "name": [
            "DCIS, University of Melbourne, Melbourne, Australia", 
            "IMDEA Software Institute, Madrid, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "de la Banda", 
        "givenName": "Mar\u00eda Garc\u00eda", 
        "id": "sg:person.016350443307.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DSIC, Complutense University of Madrid, Madrid, Spain", 
          "id": "http://www.grid.ac/institutes/grid.4795.f", 
          "name": [
            "DSIC, Complutense University of Madrid, Madrid, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "G\u00f3mez-Zamalloa", 
        "givenName": "Miguel", 
        "id": "sg:person.013203707605.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013203707605.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IMDEA Software Institute, Madrid, Spain", 
          "id": "http://www.grid.ac/institutes/grid.482873.2", 
          "name": [
            "Faculty of IT, Monash University, Melbourne, Australia", 
            "IMDEA Software Institute, Madrid, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stuckey", 
        "givenName": "Peter J.", 
        "id": "sg:person.012243374043.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2017-07-13", 
    "datePublishedReg": "2017-07-13", 
    "description": "Dynamic Partial Order Reduction (DPOR) is a powerful technique used in verification and testing to reduce the number of equivalent executions explored. Two executions are equivalent if they can be obtained from each other by swapping adjacent, non-conflicting (independent) execution steps. Existing DPOR algorithms rely on a notion of independence that is context-insensitive, i.e., the execution steps must be independent in all contexts. In practice, independence is often proved by just checking no execution step writes on a shared variable. We present context-sensitive DPOR, an extension of DPOR that uses context-sensitive independence, where two steps might be independent only in the particular context explored. We show theoretically and experimentally how context-sensitive DPOR can achieve exponential gains.", 
    "editor": [
      {
        "familyName": "Majumdar", 
        "givenName": "Rupak", 
        "type": "Person"
      }, 
      {
        "familyName": "Kun\u010dak", 
        "givenName": "Viktor", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-63387-9_26", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-63386-2", 
        "978-3-319-63387-9"
      ], 
      "name": "Computer Aided Verification", 
      "type": "Book"
    }, 
    "keywords": [
      "dynamic partial order reduction", 
      "partial order reduction", 
      "execution steps", 
      "equivalent executions", 
      "DPOR algorithm", 
      "particular context", 
      "execution", 
      "notion of independence", 
      "independence", 
      "context", 
      "order reduction", 
      "exponential gain", 
      "powerful technique", 
      "verification", 
      "algorithm", 
      "step", 
      "notion", 
      "variables", 
      "practice", 
      "technique", 
      "testing", 
      "extension", 
      "number", 
      "gain", 
      "reduction"
    ], 
    "name": "Context-Sensitive Dynamic Partial Order Reduction", 
    "pagination": "526-543", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1090658209"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-63387-9_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-63387-9_26", 
      "https://app.dimensions.ai/details/publication/pub.1090658209"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_441.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-63387-9_26"
  }
]
 

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-319-63387-9_26'

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-319-63387-9_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-63387-9_26'

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-319-63387-9_26'


 

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

123 TRIPLES      23 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-63387-9_26 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N5c421f94c4b940589c581915f12434eb
4 schema:datePublished 2017-07-13
5 schema:datePublishedReg 2017-07-13
6 schema:description Dynamic Partial Order Reduction (DPOR) is a powerful technique used in verification and testing to reduce the number of equivalent executions explored. Two executions are equivalent if they can be obtained from each other by swapping adjacent, non-conflicting (independent) execution steps. Existing DPOR algorithms rely on a notion of independence that is context-insensitive, i.e., the execution steps must be independent in all contexts. In practice, independence is often proved by just checking no execution step writes on a shared variable. We present context-sensitive DPOR, an extension of DPOR that uses context-sensitive independence, where two steps might be independent only in the particular context explored. We show theoretically and experimentally how context-sensitive DPOR can achieve exponential gains.
7 schema:editor N90e5be9f752f4422938740053bdfdd39
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N92a97732c7fa402484cd42331a16d492
12 schema:keywords DPOR algorithm
13 algorithm
14 context
15 dynamic partial order reduction
16 equivalent executions
17 execution
18 execution steps
19 exponential gain
20 extension
21 gain
22 independence
23 notion
24 notion of independence
25 number
26 order reduction
27 partial order reduction
28 particular context
29 powerful technique
30 practice
31 reduction
32 step
33 technique
34 testing
35 variables
36 verification
37 schema:name Context-Sensitive Dynamic Partial Order Reduction
38 schema:pagination 526-543
39 schema:productId N62178b8a6e3e49ba959533f34f58e3ff
40 N9fb77ab9c30548428752fc21e8f1c0cb
41 schema:publisher N029f22d3ec8c40b8aee15abeee3a4346
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090658209
43 https://doi.org/10.1007/978-3-319-63387-9_26
44 schema:sdDatePublished 2022-05-20T07:48
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher N0315637b3d784e7b8c0b201bc6b38aa1
47 schema:url https://doi.org/10.1007/978-3-319-63387-9_26
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N029f22d3ec8c40b8aee15abeee3a4346 schema:name Springer Nature
52 rdf:type schema:Organisation
53 N0315637b3d784e7b8c0b201bc6b38aa1 schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 N3c18c1f6bd4940f78acd15e03feb306b rdf:first N890ef3da35e245078dc96904912c5dff
56 rdf:rest rdf:nil
57 N5794a0f34dd54b39b49bd8ed23ade826 rdf:first sg:person.016350443307.93
58 rdf:rest Ncc2a7e4f940947a5890a3b18e8f21433
59 N5c421f94c4b940589c581915f12434eb rdf:first sg:person.011201007213.12
60 rdf:rest N67fb2cab223b419c9fbc0e8800f8f3a3
61 N62178b8a6e3e49ba959533f34f58e3ff schema:name dimensions_id
62 schema:value pub.1090658209
63 rdf:type schema:PropertyValue
64 N67fb2cab223b419c9fbc0e8800f8f3a3 rdf:first sg:person.015245434275.62
65 rdf:rest N5794a0f34dd54b39b49bd8ed23ade826
66 N6a5375cdb594457cb131ce244c2c6fcd schema:familyName Majumdar
67 schema:givenName Rupak
68 rdf:type schema:Person
69 N890ef3da35e245078dc96904912c5dff schema:familyName Kunčak
70 schema:givenName Viktor
71 rdf:type schema:Person
72 N90e5be9f752f4422938740053bdfdd39 rdf:first N6a5375cdb594457cb131ce244c2c6fcd
73 rdf:rest N3c18c1f6bd4940f78acd15e03feb306b
74 N92a97732c7fa402484cd42331a16d492 schema:isbn 978-3-319-63386-2
75 978-3-319-63387-9
76 schema:name Computer Aided Verification
77 rdf:type schema:Book
78 N9fb77ab9c30548428752fc21e8f1c0cb schema:name doi
79 schema:value 10.1007/978-3-319-63387-9_26
80 rdf:type schema:PropertyValue
81 Ncc2a7e4f940947a5890a3b18e8f21433 rdf:first sg:person.013203707605.59
82 rdf:rest Nde323d71f7754937b53b8664fbe24dd2
83 Nde323d71f7754937b53b8664fbe24dd2 rdf:first sg:person.012243374043.93
84 rdf:rest rdf:nil
85 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
86 schema:name Psychology and Cognitive Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
89 schema:name Psychology
90 rdf:type schema:DefinedTerm
91 sg:person.011201007213.12 schema:affiliation grid-institutes:grid.4795.f
92 schema:familyName Albert
93 schema:givenName Elvira
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011201007213.12
95 rdf:type schema:Person
96 sg:person.012243374043.93 schema:affiliation grid-institutes:grid.482873.2
97 schema:familyName Stuckey
98 schema:givenName Peter J.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93
100 rdf:type schema:Person
101 sg:person.013203707605.59 schema:affiliation grid-institutes:grid.4795.f
102 schema:familyName Gómez-Zamalloa
103 schema:givenName Miguel
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013203707605.59
105 rdf:type schema:Person
106 sg:person.015245434275.62 schema:affiliation grid-institutes:grid.4795.f
107 schema:familyName Arenas
108 schema:givenName Puri
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015245434275.62
110 rdf:type schema:Person
111 sg:person.016350443307.93 schema:affiliation grid-institutes:grid.482873.2
112 schema:familyName de la Banda
113 schema:givenName María García
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93
115 rdf:type schema:Person
116 grid-institutes:grid.4795.f schema:alternateName DSIC, Complutense University of Madrid, Madrid, Spain
117 schema:name DSIC, Complutense University of Madrid, Madrid, Spain
118 rdf:type schema:Organization
119 grid-institutes:grid.482873.2 schema:alternateName IMDEA Software Institute, Madrid, Spain
120 schema:name DCIS, University of Melbourne, Melbourne, Australia
121 Faculty of IT, Monash University, Melbourne, Australia
122 IMDEA Software Institute, Madrid, Spain
123 rdf:type schema:Organization
 




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


...