Extended Dependency Graphs and Efficient Distributed Fixed-Point Computation View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2017-05-05

AUTHORS

Andreas E. Dalsgaard , Søren Enevoldsen , Peter Fogh , Lasse S. Jensen , Tobias S. Jepsen , Isabella Kaufmann , Kim G. Larsen , Søren M. Nielsen , Mads Chr. Olesen , Samuel Pastva , Jiří Srba

ABSTRACT

Equivalence and model checking problems can be encoded into computing fixed points on dependency graphs. Dependency graphs represent causal dependencies among the nodes of the graph by means of hyper-edges. We suggest to extend the model of dependency graphs with so-called negation edges in order to increase their applicability. The graphs (as well as the verification problems) suffer from the state space explosion problem. To combat this issue, we design an on-the-fly algorithm for efficiently computing fixed points on extended dependency graphs. Our algorithm supplements previous approaches with the possibility to back-propagate, in certain scenarios, the domain value 0, in addition to the standard back-propagation of the value 1. Finally, we design a distributed version of the algorithm, implement it in an open-source tool, and demonstrate the efficiency of our general approach on the benchmark of Petri net models and CTL queries from the Model Checking Contest 2016. More... »

PAGES

139-158

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-57861-3_10

DOI

http://dx.doi.org/10.1007/978-3-319-57861-3_10

DIMENSIONS

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


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": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dalsgaard", 
        "givenName": "Andreas E.", 
        "id": "sg:person.014315474147.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014315474147.82"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Enevoldsen", 
        "givenName": "S\u00f8ren", 
        "id": "sg:person.014121174364.65", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014121174364.65"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fogh", 
        "givenName": "Peter", 
        "id": "sg:person.015326142043.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015326142043.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jensen", 
        "givenName": "Lasse S.", 
        "id": "sg:person.015514135364.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015514135364.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jepsen", 
        "givenName": "Tobias S.", 
        "id": "sg:person.016311515764.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016311515764.16"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kaufmann", 
        "givenName": "Isabella", 
        "id": "sg:person.07606444564.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07606444564.86"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Larsen", 
        "givenName": "Kim G.", 
        "id": "sg:person.012135303667.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012135303667.82"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nielsen", 
        "givenName": "S\u00f8ren M.", 
        "id": "sg:person.011201405564.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011201405564.40"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Olesen", 
        "givenName": "Mads Chr.", 
        "id": "sg:person.012740662302.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012740662302.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pastva", 
        "givenName": "Samuel", 
        "id": "sg:person.016130263073.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016130263073.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aalborg University, Aalborg East, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5117.2", 
          "name": [
            "Department of Computer Science, Aalborg University, Aalborg East, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Srba", 
        "givenName": "Ji\u0159\u00ed", 
        "id": "sg:person.012316540623.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012316540623.98"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2017-05-05", 
    "datePublishedReg": "2017-05-05", 
    "description": "Equivalence and model checking problems can be encoded into computing fixed points on dependency graphs. Dependency graphs represent causal dependencies among the nodes of the graph by means of hyper-edges. We suggest to extend the model of dependency graphs with so-called negation edges in order to increase their applicability. The graphs (as well as the verification problems) suffer from the state space explosion problem. To combat this issue, we design an on-the-fly algorithm for efficiently computing fixed points on extended dependency graphs. Our algorithm supplements previous approaches with the possibility to back-propagate, in certain scenarios, the domain value 0, in addition to the standard back-propagation of the value 1. Finally, we design a distributed version of the algorithm, implement it in an open-source tool, and demonstrate the efficiency of our general approach on the benchmark of Petri net models and CTL queries from the Model Checking Contest 2016.", 
    "editor": [
      {
        "familyName": "van der Aalst", 
        "givenName": "Wil", 
        "type": "Person"
      }, 
      {
        "familyName": "Best", 
        "givenName": "Eike", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-57861-3_10", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-57860-6", 
        "978-3-319-57861-3"
      ], 
      "name": "Application and Theory of Petri Nets and Concurrency", 
      "type": "Book"
    }, 
    "keywords": [
      "dependency graph", 
      "open source tools", 
      "state space explosion problem", 
      "fixed-point computation", 
      "model checking problem", 
      "space explosion problem", 
      "Petri net model", 
      "Extended Dependency Graphs", 
      "CTL queries", 
      "checking problem", 
      "explosion problem", 
      "causal dependencies", 
      "fly algorithm", 
      "net model", 
      "previous approaches", 
      "algorithm", 
      "graph", 
      "certain scenarios", 
      "queries", 
      "general approach", 
      "computation", 
      "nodes", 
      "benchmarks", 
      "scenarios", 
      "model", 
      "tool", 
      "values 0", 
      "dependency", 
      "issues", 
      "version", 
      "applicability", 
      "point", 
      "efficiency", 
      "edge", 
      "order", 
      "value 1", 
      "means", 
      "equivalence", 
      "possibility", 
      "addition", 
      "problem", 
      "approach"
    ], 
    "name": "Extended Dependency Graphs and Efficient Distributed Fixed-Point Computation", 
    "pagination": "139-158", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1085127576"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-57861-3_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-57861-3_10", 
      "https://app.dimensions.ai/details/publication/pub.1085127576"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_135.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-57861-3_10"
  }
]
 

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-57861-3_10'

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-57861-3_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-57861-3_10'

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-57861-3_10'


 

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

180 TRIPLES      22 PREDICATES      66 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-57861-3_10 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na6f8efbe7cad436a91bbb73b11329f0d
4 schema:datePublished 2017-05-05
5 schema:datePublishedReg 2017-05-05
6 schema:description Equivalence and model checking problems can be encoded into computing fixed points on dependency graphs. Dependency graphs represent causal dependencies among the nodes of the graph by means of hyper-edges. We suggest to extend the model of dependency graphs with so-called negation edges in order to increase their applicability. The graphs (as well as the verification problems) suffer from the state space explosion problem. To combat this issue, we design an on-the-fly algorithm for efficiently computing fixed points on extended dependency graphs. Our algorithm supplements previous approaches with the possibility to back-propagate, in certain scenarios, the domain value 0, in addition to the standard back-propagation of the value 1. Finally, we design a distributed version of the algorithm, implement it in an open-source tool, and demonstrate the efficiency of our general approach on the benchmark of Petri net models and CTL queries from the Model Checking Contest 2016.
7 schema:editor Na15982690cf2403d84ff9db7e644e4bf
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N289bc53262854543b854bdeaae5e21be
11 schema:keywords CTL queries
12 Extended Dependency Graphs
13 Petri net model
14 addition
15 algorithm
16 applicability
17 approach
18 benchmarks
19 causal dependencies
20 certain scenarios
21 checking problem
22 computation
23 dependency
24 dependency graph
25 edge
26 efficiency
27 equivalence
28 explosion problem
29 fixed-point computation
30 fly algorithm
31 general approach
32 graph
33 issues
34 means
35 model
36 model checking problem
37 net model
38 nodes
39 open source tools
40 order
41 point
42 possibility
43 previous approaches
44 problem
45 queries
46 scenarios
47 space explosion problem
48 state space explosion problem
49 tool
50 value 1
51 values 0
52 version
53 schema:name Extended Dependency Graphs and Efficient Distributed Fixed-Point Computation
54 schema:pagination 139-158
55 schema:productId N4d714632e7ed45998d905adcc5be10f6
56 Nb14f34170234434ab4287dec8d55e76a
57 schema:publisher N8945c7ff1cdc4e16997a83f6b741ee87
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085127576
59 https://doi.org/10.1007/978-3-319-57861-3_10
60 schema:sdDatePublished 2022-08-04T17:14
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher Nb7018cc17efa4629af4da59c305a68d6
63 schema:url https://doi.org/10.1007/978-3-319-57861-3_10
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N01a975b9edc4461eb325b70e6360f771 schema:familyName Best
68 schema:givenName Eike
69 rdf:type schema:Person
70 N09037e94b8be4053949b636278340b65 rdf:first sg:person.014121174364.65
71 rdf:rest Nd4b031189b6d4e52b7d9a09051d5f22f
72 N289bc53262854543b854bdeaae5e21be schema:isbn 978-3-319-57860-6
73 978-3-319-57861-3
74 schema:name Application and Theory of Petri Nets and Concurrency
75 rdf:type schema:Book
76 N3c04346d723049aa94c0ade4872864f3 rdf:first sg:person.07606444564.86
77 rdf:rest Nfcc84db0bf65421bb813f92256ced5b8
78 N3f6b61e332884da6bf7f34d2b1c57d43 rdf:first sg:person.012316540623.98
79 rdf:rest rdf:nil
80 N4d714632e7ed45998d905adcc5be10f6 schema:name dimensions_id
81 schema:value pub.1085127576
82 rdf:type schema:PropertyValue
83 N8945c7ff1cdc4e16997a83f6b741ee87 schema:name Springer Nature
84 rdf:type schema:Organisation
85 N92db8d4d335a45598bcbb2cf4f27589c rdf:first sg:person.015514135364.54
86 rdf:rest Naafa789d61db4afd82fa9c31d9ed0fe7
87 N9636d3d80b16414e9ec60d81b500b1c2 rdf:first sg:person.012740662302.62
88 rdf:rest Nb26299b635ca43a49e0b3dfb4f03acb5
89 Na15982690cf2403d84ff9db7e644e4bf rdf:first Ndc7877122cd14a8895d56c0899e3de9c
90 rdf:rest Nb13df9978c5b4949a3d7c9fd0f1280f8
91 Na6f8efbe7cad436a91bbb73b11329f0d rdf:first sg:person.014315474147.82
92 rdf:rest N09037e94b8be4053949b636278340b65
93 Naafa789d61db4afd82fa9c31d9ed0fe7 rdf:first sg:person.016311515764.16
94 rdf:rest N3c04346d723049aa94c0ade4872864f3
95 Nb13df9978c5b4949a3d7c9fd0f1280f8 rdf:first N01a975b9edc4461eb325b70e6360f771
96 rdf:rest rdf:nil
97 Nb14f34170234434ab4287dec8d55e76a schema:name doi
98 schema:value 10.1007/978-3-319-57861-3_10
99 rdf:type schema:PropertyValue
100 Nb26299b635ca43a49e0b3dfb4f03acb5 rdf:first sg:person.016130263073.10
101 rdf:rest N3f6b61e332884da6bf7f34d2b1c57d43
102 Nb7018cc17efa4629af4da59c305a68d6 schema:name Springer Nature - SN SciGraph project
103 rdf:type schema:Organization
104 Nba9b7c169cd54583aaa4561f855438e7 rdf:first sg:person.011201405564.40
105 rdf:rest N9636d3d80b16414e9ec60d81b500b1c2
106 Nd4b031189b6d4e52b7d9a09051d5f22f rdf:first sg:person.015326142043.06
107 rdf:rest N92db8d4d335a45598bcbb2cf4f27589c
108 Ndc7877122cd14a8895d56c0899e3de9c schema:familyName van der Aalst
109 schema:givenName Wil
110 rdf:type schema:Person
111 Nfcc84db0bf65421bb813f92256ced5b8 rdf:first sg:person.012135303667.82
112 rdf:rest Nba9b7c169cd54583aaa4561f855438e7
113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
114 schema:name Information and Computing Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
117 schema:name Computation Theory and Mathematics
118 rdf:type schema:DefinedTerm
119 sg:person.011201405564.40 schema:affiliation grid-institutes:grid.5117.2
120 schema:familyName Nielsen
121 schema:givenName Søren M.
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011201405564.40
123 rdf:type schema:Person
124 sg:person.012135303667.82 schema:affiliation grid-institutes:grid.5117.2
125 schema:familyName Larsen
126 schema:givenName Kim G.
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012135303667.82
128 rdf:type schema:Person
129 sg:person.012316540623.98 schema:affiliation grid-institutes:grid.5117.2
130 schema:familyName Srba
131 schema:givenName Jiří
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012316540623.98
133 rdf:type schema:Person
134 sg:person.012740662302.62 schema:affiliation grid-institutes:grid.5117.2
135 schema:familyName Olesen
136 schema:givenName Mads Chr.
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012740662302.62
138 rdf:type schema:Person
139 sg:person.014121174364.65 schema:affiliation grid-institutes:grid.5117.2
140 schema:familyName Enevoldsen
141 schema:givenName Søren
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014121174364.65
143 rdf:type schema:Person
144 sg:person.014315474147.82 schema:affiliation grid-institutes:grid.5117.2
145 schema:familyName Dalsgaard
146 schema:givenName Andreas E.
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014315474147.82
148 rdf:type schema:Person
149 sg:person.015326142043.06 schema:affiliation grid-institutes:grid.5117.2
150 schema:familyName Fogh
151 schema:givenName Peter
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015326142043.06
153 rdf:type schema:Person
154 sg:person.015514135364.54 schema:affiliation grid-institutes:grid.5117.2
155 schema:familyName Jensen
156 schema:givenName Lasse S.
157 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015514135364.54
158 rdf:type schema:Person
159 sg:person.016130263073.10 schema:affiliation grid-institutes:grid.10267.32
160 schema:familyName Pastva
161 schema:givenName Samuel
162 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016130263073.10
163 rdf:type schema:Person
164 sg:person.016311515764.16 schema:affiliation grid-institutes:grid.5117.2
165 schema:familyName Jepsen
166 schema:givenName Tobias S.
167 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016311515764.16
168 rdf:type schema:Person
169 sg:person.07606444564.86 schema:affiliation grid-institutes:grid.5117.2
170 schema:familyName Kaufmann
171 schema:givenName Isabella
172 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07606444564.86
173 rdf:type schema:Person
174 grid-institutes:grid.10267.32 schema:alternateName Faculty of Informatics, Masaryk University, Brno, Czech Republic
175 schema:name Department of Computer Science, Aalborg University, Aalborg East, Denmark
176 Faculty of Informatics, Masaryk University, Brno, Czech Republic
177 rdf:type schema:Organization
178 grid-institutes:grid.5117.2 schema:alternateName Department of Computer Science, Aalborg University, Aalborg East, Denmark
179 schema:name Department of Computer Science, Aalborg University, Aalborg East, Denmark
180 rdf:type schema:Organization
 




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


...