Algebraic techniques for timed systems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1998

AUTHORS

Albert Benveniste , Claude Jard , Stéphane Gaubert

ABSTRACT

Performance evaluation is a central issue in the design of complex real-time systems. In this work, we propose an extension of so-called “Max-Plus” algebraic techniques to handle more realistic types of real-time systems. In particular, our framework encompasses graph or partial order automata, and more generally abstract models of real-time computations (including synchronous programs running over distributed architectures). To achieve this, we introduce a new dioid of partially commutative power series (transductions), whose elements encode timed behaviors. This formalism extends the traditional representation of timed event graphs by (rational) commutative transfer series with coefficients in the Max-Plus semiring. We sketch how this framework can be used to symbolically solve several problems of interest, related to real-time systems. Then we illustrate the use of this framework to encode a nontrivial mixed formalism of dataflow diagrams and automata. More... »

PAGES

373-388

References to SciGraph publications

  • 1997-08. Verification of Real-Time Systems using Linear Relation Analysis in FORMAL METHODS IN SYSTEM DESIGN
  • Book

    TITLE

    CONCUR'98 Concurrency Theory

    ISBN

    978-3-540-64896-3
    978-3-540-68455-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bfb0055636

    DOI

    http://dx.doi.org/10.1007/bfb0055636

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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 Rennes 1", 
              "id": "https://www.grid.ac/institutes/grid.410368.8", 
              "name": [
                "IRISA/INRIA, Campus de Beaulieu, F-35042\u00a0Rennes Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Benveniste", 
            "givenName": "Albert", 
            "id": "sg:person.011174600625.42", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011174600625.42"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Rennes 1", 
              "id": "https://www.grid.ac/institutes/grid.410368.8", 
              "name": [
                "IRISA/CNRS, Campus de Beaulieu, F-35042\u00a0Rennes Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Jard", 
            "givenName": "Claude", 
            "id": "sg:person.015533423605.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015533423605.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French Institute for Research in Computer Science and Automation", 
              "id": "https://www.grid.ac/institutes/grid.5328.c", 
              "name": [
                "INRIA, BP 105, F-78153\u00a0Le Chesnay Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gaubert", 
            "givenName": "St\u00e9phane", 
            "id": "sg:person.012650053263.42", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012650053263.42"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1023/a:1008678014487", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003599261", 
              "https://doi.org/10.1023/a:1008678014487"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/9.545714", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061245116"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1998", 
        "datePublishedReg": "1998-01-01", 
        "description": "Performance evaluation is a central issue in the design of complex real-time systems. In this work, we propose an extension of so-called \u201cMax-Plus\u201d algebraic techniques to handle more realistic types of real-time systems. In particular, our framework encompasses graph or partial order automata, and more generally abstract models of real-time computations (including synchronous programs running over distributed architectures). To achieve this, we introduce a new dioid of partially commutative power series (transductions), whose elements encode timed behaviors. This formalism extends the traditional representation of timed event graphs by (rational) commutative transfer series with coefficients in the Max-Plus semiring. We sketch how this framework can be used to symbolically solve several problems of interest, related to real-time systems. Then we illustrate the use of this framework to encode a nontrivial mixed formalism of dataflow diagrams and automata.", 
        "editor": [
          {
            "familyName": "Sangiorgi", 
            "givenName": "Davide", 
            "type": "Person"
          }, 
          {
            "familyName": "de Simone", 
            "givenName": "Robert", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/bfb0055636", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-64896-3", 
            "978-3-540-68455-8"
          ], 
          "name": "CONCUR'98 Concurrency Theory", 
          "type": "Book"
        }, 
        "name": "Algebraic techniques for timed systems", 
        "pagination": "373-388", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bfb0055636"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e7de04bb8eac3c4a7e87b8a7742c5e48cef18a44af12ae7fb4d9c2b3249775f9"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1048672703"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/bfb0055636", 
          "https://app.dimensions.ai/details/publication/pub.1048672703"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T12:35", 
        "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_00000273.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/BFb0055636"
      }
    ]
     

    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/bfb0055636'

    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/bfb0055636'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0055636'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0055636'


     

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

    95 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bfb0055636 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N5ac66ac9757c41ef8f9592cec5ff8da9
    4 schema:citation sg:pub.10.1023/a:1008678014487
    5 https://doi.org/10.1109/9.545714
    6 schema:datePublished 1998
    7 schema:datePublishedReg 1998-01-01
    8 schema:description Performance evaluation is a central issue in the design of complex real-time systems. In this work, we propose an extension of so-called “Max-Plus” algebraic techniques to handle more realistic types of real-time systems. In particular, our framework encompasses graph or partial order automata, and more generally abstract models of real-time computations (including synchronous programs running over distributed architectures). To achieve this, we introduce a new dioid of partially commutative power series (transductions), whose elements encode timed behaviors. This formalism extends the traditional representation of timed event graphs by (rational) commutative transfer series with coefficients in the Max-Plus semiring. We sketch how this framework can be used to symbolically solve several problems of interest, related to real-time systems. Then we illustrate the use of this framework to encode a nontrivial mixed formalism of dataflow diagrams and automata.
    9 schema:editor N6bde2b12895546939168c2457a113f97
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree true
    13 schema:isPartOf N31c5904b16734670b2a8b68808c4cb1b
    14 schema:name Algebraic techniques for timed systems
    15 schema:pagination 373-388
    16 schema:productId N4fb16ba68e0b4c2b960e8e06ebe060ef
    17 N89dadcbbe67b4b15b03b1dedadf10b25
    18 Nac4fed5953214f338cdc8026230094de
    19 schema:publisher N8fcdb26e16d84e1281dcbd311d21c3c9
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048672703
    21 https://doi.org/10.1007/bfb0055636
    22 schema:sdDatePublished 2019-04-15T12:35
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher N52408fb79ae6458f84fc02a47f2dbc00
    25 schema:url http://link.springer.com/10.1007/BFb0055636
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset chapters
    28 rdf:type schema:Chapter
    29 N31c5904b16734670b2a8b68808c4cb1b schema:isbn 978-3-540-64896-3
    30 978-3-540-68455-8
    31 schema:name CONCUR'98 Concurrency Theory
    32 rdf:type schema:Book
    33 N478c6b0ef08c4c3a80648aaa088fd180 schema:familyName Sangiorgi
    34 schema:givenName Davide
    35 rdf:type schema:Person
    36 N4fb16ba68e0b4c2b960e8e06ebe060ef schema:name doi
    37 schema:value 10.1007/bfb0055636
    38 rdf:type schema:PropertyValue
    39 N52408fb79ae6458f84fc02a47f2dbc00 schema:name Springer Nature - SN SciGraph project
    40 rdf:type schema:Organization
    41 N5ac66ac9757c41ef8f9592cec5ff8da9 rdf:first sg:person.011174600625.42
    42 rdf:rest Naf3c2bab780e4b49960b81878acccdf2
    43 N6bde2b12895546939168c2457a113f97 rdf:first N478c6b0ef08c4c3a80648aaa088fd180
    44 rdf:rest Nd47570fb840346d4abee87946678fa33
    45 N89dadcbbe67b4b15b03b1dedadf10b25 schema:name readcube_id
    46 schema:value e7de04bb8eac3c4a7e87b8a7742c5e48cef18a44af12ae7fb4d9c2b3249775f9
    47 rdf:type schema:PropertyValue
    48 N8fcdb26e16d84e1281dcbd311d21c3c9 schema:location Berlin, Heidelberg
    49 schema:name Springer Berlin Heidelberg
    50 rdf:type schema:Organisation
    51 N9dd0423755fc47128c99e1e4256342ac schema:familyName de Simone
    52 schema:givenName Robert
    53 rdf:type schema:Person
    54 N9e8ea4ca960d44c9a56aab086ae98fce rdf:first sg:person.012650053263.42
    55 rdf:rest rdf:nil
    56 Nac4fed5953214f338cdc8026230094de schema:name dimensions_id
    57 schema:value pub.1048672703
    58 rdf:type schema:PropertyValue
    59 Naf3c2bab780e4b49960b81878acccdf2 rdf:first sg:person.015533423605.19
    60 rdf:rest N9e8ea4ca960d44c9a56aab086ae98fce
    61 Nd47570fb840346d4abee87946678fa33 rdf:first N9dd0423755fc47128c99e1e4256342ac
    62 rdf:rest rdf:nil
    63 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    64 schema:name Information and Computing Sciences
    65 rdf:type schema:DefinedTerm
    66 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Computation Theory and Mathematics
    68 rdf:type schema:DefinedTerm
    69 sg:person.011174600625.42 schema:affiliation https://www.grid.ac/institutes/grid.410368.8
    70 schema:familyName Benveniste
    71 schema:givenName Albert
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011174600625.42
    73 rdf:type schema:Person
    74 sg:person.012650053263.42 schema:affiliation https://www.grid.ac/institutes/grid.5328.c
    75 schema:familyName Gaubert
    76 schema:givenName Stéphane
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012650053263.42
    78 rdf:type schema:Person
    79 sg:person.015533423605.19 schema:affiliation https://www.grid.ac/institutes/grid.410368.8
    80 schema:familyName Jard
    81 schema:givenName Claude
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015533423605.19
    83 rdf:type schema:Person
    84 sg:pub.10.1023/a:1008678014487 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003599261
    85 https://doi.org/10.1023/a:1008678014487
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1109/9.545714 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061245116
    88 rdf:type schema:CreativeWork
    89 https://www.grid.ac/institutes/grid.410368.8 schema:alternateName University of Rennes 1
    90 schema:name IRISA/CNRS, Campus de Beaulieu, F-35042 Rennes Cedex, France
    91 IRISA/INRIA, Campus de Beaulieu, F-35042 Rennes Cedex, France
    92 rdf:type schema:Organization
    93 https://www.grid.ac/institutes/grid.5328.c schema:alternateName French Institute for Research in Computer Science and Automation
    94 schema:name INRIA, BP 105, F-78153 Le Chesnay Cedex, France
    95 rdf:type schema:Organization
     




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


    ...