I/O Efficient Accepting Cycle Detection View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007-01-01

AUTHORS

Jiri Barnat , Lubos Brim , Pavel Šimeček

ABSTRACT

We show how to adapt an existing non-DFS-based accepting cycle detection algorithm OWCTY [10,15,29] to the I/O efficient setting and compare its I/O efficiency and practical performance to the existing I/O efficient LTL model checking approach of Edelkamp and Jabbar [14]. The new algorithm exhibits similar I/O complexity with respect to the size of the graph while it avoids quadratic increase in the size of the graph. Therefore, the number of I/O operations performed is significantly lower and the algorithm exhibits better practical performance. More... »

PAGES

281-293

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-73368-3_32

DOI

http://dx.doi.org/10.1007/978-3-540-73368-3_32

DIMENSIONS

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


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, Faculty of Informatics, Masaryk University Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Department of Computer Science, Faculty of Informatics, Masaryk University Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Barnat", 
        "givenName": "Jiri", 
        "id": "sg:person.011367557177.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011367557177.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Faculty of Informatics, Masaryk University Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Department of Computer Science, Faculty of Informatics, Masaryk University Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brim", 
        "givenName": "Lubos", 
        "id": "sg:person.0645117057.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0645117057.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Faculty of Informatics, Masaryk University Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Department of Computer Science, Faculty of Informatics, Masaryk University Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "\u0160ime\u010dek", 
        "givenName": "Pavel", 
        "id": "sg:person.016270033701.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016270033701.83"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "We show how to adapt an existing non-DFS-based accepting cycle detection algorithm OWCTY\u00a0[10,15,29] to the I/O efficient setting and compare its I/O efficiency and practical performance to the existing I/O efficient LTL model checking approach of Edelkamp and Jabbar\u00a0[14]. The new algorithm exhibits similar I/O complexity with respect to the size of the graph while it avoids quadratic increase in the size of the graph. Therefore, the number of I/O operations performed is significantly lower and the algorithm exhibits better practical performance.", 
    "editor": [
      {
        "familyName": "Damm", 
        "givenName": "Werner", 
        "type": "Person"
      }, 
      {
        "familyName": "Hermanns", 
        "givenName": "Holger", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-73368-3_32", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-73367-6", 
        "978-3-540-73368-3"
      ], 
      "name": "Computer Aided Verification", 
      "type": "Book"
    }, 
    "keywords": [
      "practical performance", 
      "LTL model", 
      "good practical performance", 
      "cycle detection", 
      "new algorithm", 
      "algorithm", 
      "efficient setting", 
      "graph", 
      "performance", 
      "complexity", 
      "Efficient", 
      "operation", 
      "detection", 
      "efficiency", 
      "model", 
      "quadratic increase", 
      "number", 
      "setting", 
      "approach", 
      "size", 
      "respect", 
      "DFS", 
      "increase", 
      "Jabbar"
    ], 
    "name": "I/O Efficient Accepting Cycle Detection", 
    "pagination": "281-293", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052161956"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-73368-3_32"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-73368-3_32", 
      "https://app.dimensions.ai/details/publication/pub.1052161956"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_365.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-73368-3_32"
  }
]
 

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-540-73368-3_32'

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-540-73368-3_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73368-3_32'

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-540-73368-3_32'


 

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

103 TRIPLES      23 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-73368-3_32 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc1b3ba8fa7cf4a2090d66e155fc85251
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description We show how to adapt an existing non-DFS-based accepting cycle detection algorithm OWCTY [10,15,29] to the I/O efficient setting and compare its I/O efficiency and practical performance to the existing I/O efficient LTL model checking approach of Edelkamp and Jabbar [14]. The new algorithm exhibits similar I/O complexity with respect to the size of the graph while it avoids quadratic increase in the size of the graph. Therefore, the number of I/O operations performed is significantly lower and the algorithm exhibits better practical performance.
7 schema:editor N0b810451585140dba793f85031c71c55
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nd8d0183b65c04e1b8e7b3ae61d558d92
12 schema:keywords DFS
13 Efficient
14 Jabbar
15 LTL model
16 algorithm
17 approach
18 complexity
19 cycle detection
20 detection
21 efficiency
22 efficient setting
23 good practical performance
24 graph
25 increase
26 model
27 new algorithm
28 number
29 operation
30 performance
31 practical performance
32 quadratic increase
33 respect
34 setting
35 size
36 schema:name I/O Efficient Accepting Cycle Detection
37 schema:pagination 281-293
38 schema:productId N8eb8817b1e7b44fa9feb706a65134d0c
39 Nf7db65ca98874337a1cafafe606aa0ce
40 schema:publisher N2cbbf31ef9e4469ca9f873415e66dd54
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052161956
42 https://doi.org/10.1007/978-3-540-73368-3_32
43 schema:sdDatePublished 2022-05-10T10:48
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher Nd88013319e614a95855bb52c189d9036
46 schema:url https://doi.org/10.1007/978-3-540-73368-3_32
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N0b810451585140dba793f85031c71c55 rdf:first Nc94de3839edf46efbb8faaf16888c36a
51 rdf:rest Nd0cf7011244d419484f42d6a4d37c073
52 N2cbbf31ef9e4469ca9f873415e66dd54 schema:name Springer Nature
53 rdf:type schema:Organisation
54 N7f67d0ae2a0c47bfb29ead348cf9cdff rdf:first sg:person.016270033701.83
55 rdf:rest rdf:nil
56 N8eb8817b1e7b44fa9feb706a65134d0c schema:name doi
57 schema:value 10.1007/978-3-540-73368-3_32
58 rdf:type schema:PropertyValue
59 Nbdc5d12c83c0494bafcce43888fbb873 rdf:first sg:person.0645117057.83
60 rdf:rest N7f67d0ae2a0c47bfb29ead348cf9cdff
61 Nc1b3ba8fa7cf4a2090d66e155fc85251 rdf:first sg:person.011367557177.46
62 rdf:rest Nbdc5d12c83c0494bafcce43888fbb873
63 Nc94de3839edf46efbb8faaf16888c36a schema:familyName Damm
64 schema:givenName Werner
65 rdf:type schema:Person
66 Nd0cf7011244d419484f42d6a4d37c073 rdf:first Nd883c5557869457f9428d98ad7f23a62
67 rdf:rest rdf:nil
68 Nd88013319e614a95855bb52c189d9036 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 Nd883c5557869457f9428d98ad7f23a62 schema:familyName Hermanns
71 schema:givenName Holger
72 rdf:type schema:Person
73 Nd8d0183b65c04e1b8e7b3ae61d558d92 schema:isbn 978-3-540-73367-6
74 978-3-540-73368-3
75 schema:name Computer Aided Verification
76 rdf:type schema:Book
77 Nf7db65ca98874337a1cafafe606aa0ce schema:name dimensions_id
78 schema:value pub.1052161956
79 rdf:type schema:PropertyValue
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.011367557177.46 schema:affiliation grid-institutes:grid.10267.32
87 schema:familyName Barnat
88 schema:givenName Jiri
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011367557177.46
90 rdf:type schema:Person
91 sg:person.016270033701.83 schema:affiliation grid-institutes:grid.10267.32
92 schema:familyName Šimeček
93 schema:givenName Pavel
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016270033701.83
95 rdf:type schema:Person
96 sg:person.0645117057.83 schema:affiliation grid-institutes:grid.10267.32
97 schema:familyName Brim
98 schema:givenName Lubos
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0645117057.83
100 rdf:type schema:Person
101 grid-institutes:grid.10267.32 schema:alternateName Department of Computer Science, Faculty of Informatics, Masaryk University Brno, Czech Republic
102 schema:name Department of Computer Science, Faculty of Informatics, Masaryk University Brno, Czech Republic
103 rdf:type schema:Organization
 




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


...