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 Ne8a675495be64916b82f0a9006826e48
    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 Nebf90fefa21d4f3e8c35c2ad339125b2
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree true
    13 schema:isPartOf N3865ada045fe4e64b03f17a346b05b64
    14 schema:name Algebraic techniques for timed systems
    15 schema:pagination 373-388
    16 schema:productId N73671aa46fb8442a853c4b60d2b964c9
    17 Nb42f7775ca71423abed6113a64fae26a
    18 Ncccc03efe77b4065ac8fda36b35b97ce
    19 schema:publisher Nf1a2295a40164ffe8484e13edf0cc871
    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 N43ce888134594a39b16b472bd523a31d
    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 N3865ada045fe4e64b03f17a346b05b64 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 N43ce888134594a39b16b472bd523a31d schema:name Springer Nature - SN SciGraph project
    34 rdf:type schema:Organization
    35 N55df50e7bd24464b9d9f295fb36fd047 rdf:first sg:person.012650053263.42
    36 rdf:rest rdf:nil
    37 N62401048081d4f9884fa5793140abfb0 schema:familyName de Simone
    38 schema:givenName Robert
    39 rdf:type schema:Person
    40 N73671aa46fb8442a853c4b60d2b964c9 schema:name readcube_id
    41 schema:value e7de04bb8eac3c4a7e87b8a7742c5e48cef18a44af12ae7fb4d9c2b3249775f9
    42 rdf:type schema:PropertyValue
    43 Na796b79ce2fd4ca4bd844190469b5f31 rdf:first sg:person.015533423605.19
    44 rdf:rest N55df50e7bd24464b9d9f295fb36fd047
    45 Nb42f7775ca71423abed6113a64fae26a schema:name dimensions_id
    46 schema:value pub.1048672703
    47 rdf:type schema:PropertyValue
    48 Nc344fc6f0aea4eb695fff2888c7c001f schema:familyName Sangiorgi
    49 schema:givenName Davide
    50 rdf:type schema:Person
    51 Ncccc03efe77b4065ac8fda36b35b97ce schema:name doi
    52 schema:value 10.1007/bfb0055636
    53 rdf:type schema:PropertyValue
    54 Ne8a675495be64916b82f0a9006826e48 rdf:first sg:person.011174600625.42
    55 rdf:rest Na796b79ce2fd4ca4bd844190469b5f31
    56 Nebf90fefa21d4f3e8c35c2ad339125b2 rdf:first Nc344fc6f0aea4eb695fff2888c7c001f
    57 rdf:rest Nf263f38ed4224b11b237682656af85b5
    58 Nf1a2295a40164ffe8484e13edf0cc871 schema:location Berlin, Heidelberg
    59 schema:name Springer Berlin Heidelberg
    60 rdf:type schema:Organisation
    61 Nf263f38ed4224b11b237682656af85b5 rdf:first N62401048081d4f9884fa5793140abfb0
    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)


    ...