Decomposition in Asynchronous Circuit Design View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002

AUTHORS

Walter Vogler , Ralf Wollowski

ABSTRACT

Signal Transition Graphs (STGs) are a version of Petri nets for the specification of asynchronous circuit behaviour. It has been suggested to decompose such a specification as a first step; this leads to a modular implementation, which can support circuit synthesis by possibly avoiding state explosion or allowing the use of library elements. We present a decomposition algorithm and formally prove it correct, where an interesting aspect is the use of a bisimulation with angelic nondeterminism. In contrast to similar approaches in the literature, our algorithm is very generally applicable. We show that transition contraction - the main operation in the algorithm - can be applied with fewer restrictions than known so far. We also prove that deletion of redundant places can be used in the algorithm, which turns out to be very useful in examples. More... »

PAGES

152-190

References to SciGraph publications

  • 1996-11. On the models for asynchronous circuit behaviour with OR causality in FORMAL METHODS IN SYSTEM DESIGN
  • Book

    TITLE

    Concurrency and Hardware Design

    ISBN

    978-3-540-00199-7
    978-3-540-36190-9

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-36190-1_5

    DOI

    http://dx.doi.org/10.1007/3-540-36190-1_5

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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": "University of Augsburg", 
              "id": "https://www.grid.ac/institutes/grid.7307.3", 
              "name": [
                "Institut f\u00fcr Informatik, Universit\u00e4t Augsburg, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vogler", 
            "givenName": "Walter", 
            "id": "sg:person.013274500660.84", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013274500660.84"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Kaiserslautern", 
              "id": "https://www.grid.ac/institutes/grid.7645.0", 
              "name": [
                "FB Elektro- und Informationstechnik, Universit\u00e4t Kaiserlautern, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wollowski", 
            "givenName": "Ralf", 
            "id": "sg:person.013666313531.32", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013666313531.32"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/s0167-9260(86)80002-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025503275"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00122082", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027185802", 
              "https://doi.org/10.1007/bf00122082"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00122082", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027185802", 
              "https://doi.org/10.1007/bf00122082"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-6423(92)90017-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043787727"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002", 
        "datePublishedReg": "2002-01-01", 
        "description": "Signal Transition Graphs (STGs) are a version of Petri nets for the specification of asynchronous circuit behaviour. It has been suggested to decompose such a specification as a first step; this leads to a modular implementation, which can support circuit synthesis by possibly avoiding state explosion or allowing the use of library elements. We present a decomposition algorithm and formally prove it correct, where an interesting aspect is the use of a bisimulation with angelic nondeterminism. In contrast to similar approaches in the literature, our algorithm is very generally applicable. We show that transition contraction - the main operation in the algorithm - can be applied with fewer restrictions than known so far. We also prove that deletion of redundant places can be used in the algorithm, which turns out to be very useful in examples.", 
        "editor": [
          {
            "familyName": "Cortadella", 
            "givenName": "Jordi", 
            "type": "Person"
          }, 
          {
            "familyName": "Yakovlev", 
            "givenName": "Alex", 
            "type": "Person"
          }, 
          {
            "familyName": "Rozenberg", 
            "givenName": "Grzegorz", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-36190-1_5", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-00199-7", 
            "978-3-540-36190-9"
          ], 
          "name": "Concurrency and Hardware Design", 
          "type": "Book"
        }, 
        "name": "Decomposition in Asynchronous Circuit Design", 
        "pagination": "152-190", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-36190-1_5"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "285d46a1f4054cf3c54011c3e6aa2aeb5d47ddb0dcbdedaa66e525aebc1e64c4"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1008472703"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-36190-1_5", 
          "https://app.dimensions.ai/details/publication/pub.1008472703"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T12:29", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8663_00000248.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-36190-1_5"
      }
    ]
     

    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/3-540-36190-1_5'

    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/3-540-36190-1_5'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-36190-1_5'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-36190-1_5'


     

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

    95 TRIPLES      23 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-36190-1_5 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N21a9db0899604c4e82ce092a7345f012
    4 schema:citation sg:pub.10.1007/bf00122082
    5 https://doi.org/10.1016/0167-6423(92)90017-6
    6 https://doi.org/10.1016/s0167-9260(86)80002-5
    7 schema:datePublished 2002
    8 schema:datePublishedReg 2002-01-01
    9 schema:description Signal Transition Graphs (STGs) are a version of Petri nets for the specification of asynchronous circuit behaviour. It has been suggested to decompose such a specification as a first step; this leads to a modular implementation, which can support circuit synthesis by possibly avoiding state explosion or allowing the use of library elements. We present a decomposition algorithm and formally prove it correct, where an interesting aspect is the use of a bisimulation with angelic nondeterminism. In contrast to similar approaches in the literature, our algorithm is very generally applicable. We show that transition contraction - the main operation in the algorithm - can be applied with fewer restrictions than known so far. We also prove that deletion of redundant places can be used in the algorithm, which turns out to be very useful in examples.
    10 schema:editor N42a892fe8b2e4390a77da159968dc40d
    11 schema:genre chapter
    12 schema:inLanguage en
    13 schema:isAccessibleForFree true
    14 schema:isPartOf N0d7669bb6cc74718881b1c6001690a36
    15 schema:name Decomposition in Asynchronous Circuit Design
    16 schema:pagination 152-190
    17 schema:productId N20737bf2c4d4401b8749fb517a4995cc
    18 N42550cde979e40e6b49e10f5ce280c65
    19 N8355e535953941da8695f46a26f7007c
    20 schema:publisher Ne394d8020c854bfca1f046d3b86f7918
    21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008472703
    22 https://doi.org/10.1007/3-540-36190-1_5
    23 schema:sdDatePublished 2019-04-15T12:29
    24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    25 schema:sdPublisher Ndc3c9043c6e949deb3b110ef9eff7550
    26 schema:url http://link.springer.com/10.1007/3-540-36190-1_5
    27 sgo:license sg:explorer/license/
    28 sgo:sdDataset chapters
    29 rdf:type schema:Chapter
    30 N0d7669bb6cc74718881b1c6001690a36 schema:isbn 978-3-540-00199-7
    31 978-3-540-36190-9
    32 schema:name Concurrency and Hardware Design
    33 rdf:type schema:Book
    34 N20737bf2c4d4401b8749fb517a4995cc schema:name readcube_id
    35 schema:value 285d46a1f4054cf3c54011c3e6aa2aeb5d47ddb0dcbdedaa66e525aebc1e64c4
    36 rdf:type schema:PropertyValue
    37 N21a9db0899604c4e82ce092a7345f012 rdf:first sg:person.013274500660.84
    38 rdf:rest N71b36c0327454f44a4e0a4464fcf93bf
    39 N42550cde979e40e6b49e10f5ce280c65 schema:name doi
    40 schema:value 10.1007/3-540-36190-1_5
    41 rdf:type schema:PropertyValue
    42 N42a892fe8b2e4390a77da159968dc40d rdf:first Ndd882c799b1642f0a996d13949c6bcc8
    43 rdf:rest Nbe0838408450413eb8d46cbc3a31c581
    44 N71b36c0327454f44a4e0a4464fcf93bf rdf:first sg:person.013666313531.32
    45 rdf:rest rdf:nil
    46 N8355e535953941da8695f46a26f7007c schema:name dimensions_id
    47 schema:value pub.1008472703
    48 rdf:type schema:PropertyValue
    49 N98333262bf98406f9d49a138fd6a5b39 schema:familyName Rozenberg
    50 schema:givenName Grzegorz
    51 rdf:type schema:Person
    52 N9c19157a88084320b5028fa40c2c44eb schema:familyName Yakovlev
    53 schema:givenName Alex
    54 rdf:type schema:Person
    55 Nb346b5f86ade4ed8a52eec46f0d1c209 rdf:first N98333262bf98406f9d49a138fd6a5b39
    56 rdf:rest rdf:nil
    57 Nbe0838408450413eb8d46cbc3a31c581 rdf:first N9c19157a88084320b5028fa40c2c44eb
    58 rdf:rest Nb346b5f86ade4ed8a52eec46f0d1c209
    59 Ndc3c9043c6e949deb3b110ef9eff7550 schema:name Springer Nature - SN SciGraph project
    60 rdf:type schema:Organization
    61 Ndd882c799b1642f0a996d13949c6bcc8 schema:familyName Cortadella
    62 schema:givenName Jordi
    63 rdf:type schema:Person
    64 Ne394d8020c854bfca1f046d3b86f7918 schema:location Berlin, Heidelberg
    65 schema:name Springer Berlin Heidelberg
    66 rdf:type schema:Organisation
    67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Information and Computing Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Artificial Intelligence and Image Processing
    72 rdf:type schema:DefinedTerm
    73 sg:person.013274500660.84 schema:affiliation https://www.grid.ac/institutes/grid.7307.3
    74 schema:familyName Vogler
    75 schema:givenName Walter
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013274500660.84
    77 rdf:type schema:Person
    78 sg:person.013666313531.32 schema:affiliation https://www.grid.ac/institutes/grid.7645.0
    79 schema:familyName Wollowski
    80 schema:givenName Ralf
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013666313531.32
    82 rdf:type schema:Person
    83 sg:pub.10.1007/bf00122082 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027185802
    84 https://doi.org/10.1007/bf00122082
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/0167-6423(92)90017-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043787727
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1016/s0167-9260(86)80002-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025503275
    89 rdf:type schema:CreativeWork
    90 https://www.grid.ac/institutes/grid.7307.3 schema:alternateName University of Augsburg
    91 schema:name Institut für Informatik, Universität Augsburg, Germany
    92 rdf:type schema:Organization
    93 https://www.grid.ac/institutes/grid.7645.0 schema:alternateName University of Kaiserslautern
    94 schema:name FB Elektro- und Informationstechnik, Universität Kaiserlautern, Germany
    95 rdf:type schema:Organization
     




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


    ...