Resource Analysis by Sup-interpretation View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Jean-Yves Marion , Romain Péchoux

ABSTRACT

We propose a new method to control memory resources by static analysis. For this, we introduce the notion of sup-interpretation which bounds from above the size of function outputs. We establish a criteria for which the stack frame size is polynomially bounded. The criteria analyses terminating as well as non-terminating programs. This method applies to first order functional programming with pattern matching. This work is related to quasi-interpretations but we are now able to determine resources of different algorithms and it is easier to perform an analysis with this new tools. More... »

PAGES

163-176

References to SciGraph publications

  • 2000. A Type System for Bounded Space and Functional In-Place Update—Extended Abstract in PROGRAMMING LANGUAGES AND SYSTEMS
  • 2002-07-02. Efficient First Order Functional Program Interpreter with Time Bound Certifications in LOGIC FOR PROGRAMMING AND AUTOMATED REASONING
  • 2003-11. Heap-Bounded Assembly Language in JOURNAL OF AUTOMATED REASONING
  • 2003. Size-Change Termination for Term Rewriting in REWRITING TECHNIQUES AND APPLICATIONS
  • 2004. A Functional Scenario for Bytecode Verification of Resource Bounds in COMPUTER SCIENCE LOGIC
  • 2003-05-27. Max-Plus Quasi-interpretations in TYPED LAMBDA CALCULI AND APPLICATIONS
  • 2001. On Lexicographic Termination Ordering with Space Bound Certifications in PERSPECTIVES OF SYSTEM INFORMATICS
  • Book

    TITLE

    Functional and Logic Programming

    ISBN

    978-3-540-33438-5
    978-3-540-33439-2

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11737414_12

    DOI

    http://dx.doi.org/10.1007/11737414_12

    DIMENSIONS

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


    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": "\u00c9cole Nationale Sup\u00e9rieure des Mines de Nancy", 
              "id": "https://www.grid.ac/institutes/grid.473477.4", 
              "name": [
                "Loria, Calligramme project, B.P. 239, 54506 Cedex, Vand\u0153uvre-l\u00e8s-Nancy, France", 
                "\u00c9cole Nationale Sup\u00e9rieure des Mines de Nancy, INPL, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Marion", 
            "givenName": "Jean-Yves", 
            "id": "sg:person.016702671367.99", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016702671367.99"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "\u00c9cole Nationale Sup\u00e9rieure des Mines de Nancy", 
              "id": "https://www.grid.ac/institutes/grid.473477.4", 
              "name": [
                "Loria, Calligramme project, B.P. 239, 54506 Cedex, Vand\u0153uvre-l\u00e8s-Nancy, France", 
                "\u00c9cole Nationale Sup\u00e9rieure des Mines de Nancy, INPL, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "P\u00e9choux", 
            "givenName": "Romain", 
            "id": "sg:person.016241557431.75", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016241557431.75"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-44404-1_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000486298", 
              "https://doi.org/10.1007/3-540-44404-1_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44404-1_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000486298", 
              "https://doi.org/10.1007/3-540-44404-1_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44904-3_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002927224", 
              "https://doi.org/10.1007/3-540-44904-3_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44904-3_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002927224", 
              "https://doi.org/10.1007/3-540-44904-3_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30124-0_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007267443", 
              "https://doi.org/10.1007/978-3-540-30124-0_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30124-0_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007267443", 
              "https://doi.org/10.1007/978-3-540-30124-0_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/161468.161472", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009208603"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/360204.360210", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013482748"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321386.321395", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018826104"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46425-5_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024487659", 
              "https://doi.org/10.1007/3-540-46425-5_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0747-7171(87)80022-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026818855"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44881-0_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037217022", 
              "https://doi.org/10.1007/3-540-44881-0_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0956796800003877", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040313166"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0956796800003877", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040313166"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45575-2_46", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041545494", 
              "https://doi.org/10.1007/3-540-45575-2_46"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2003.10.022", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041611540"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(99)00207-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047998683"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/b:jars.0000021014.79255.33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051133555", 
              "https://doi.org/10.1023/b:jars.0000021014.79255.33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1051/ita:2005029", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056972217"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1051/ita:2005029", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056972217"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/hicss.2003.1174809", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093306054"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/lics.1999.782641", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095554525"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2006", 
        "datePublishedReg": "2006-01-01", 
        "description": "We propose a new method to control memory resources by static analysis. For this, we introduce the notion of sup-interpretation which bounds from above the size of function outputs. We establish a criteria for which the stack frame size is polynomially bounded. The criteria analyses terminating as well as non-terminating programs. This method applies to first order functional programming with pattern matching. This work is related to quasi-interpretations but we are now able to determine resources of different algorithms and it is easier to perform an analysis with this new tools.", 
        "editor": [
          {
            "familyName": "Hagiya", 
            "givenName": "Masami", 
            "type": "Person"
          }, 
          {
            "familyName": "Wadler", 
            "givenName": "Philip", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11737414_12", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-33438-5", 
            "978-3-540-33439-2"
          ], 
          "name": "Functional and Logic Programming", 
          "type": "Book"
        }, 
        "name": "Resource Analysis by Sup-interpretation", 
        "pagination": "163-176", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1018767695"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11737414_12"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "596bf4e0956015c6bfb085c6d90df1b0f24b467a4045b0741e71ef1274363fc1"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11737414_12", 
          "https://app.dimensions.ai/details/publication/pub.1018767695"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07: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/0000000356_0000000356/records_57871_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11737414_12"
      }
    ]
     

    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/11737414_12'

    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/11737414_12'

    Turtle is a human-readable linked data format.

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

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

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


     

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

    136 TRIPLES      23 PREDICATES      44 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11737414_12 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Na2541c9732a74267a56fc98b0fe25d72
    4 schema:citation sg:pub.10.1007/3-540-44404-1_3
    5 sg:pub.10.1007/3-540-44881-0_19
    6 sg:pub.10.1007/3-540-44904-3_3
    7 sg:pub.10.1007/3-540-45575-2_46
    8 sg:pub.10.1007/3-540-46425-5_11
    9 sg:pub.10.1007/978-3-540-30124-0_22
    10 sg:pub.10.1023/b:jars.0000021014.79255.33
    11 https://doi.org/10.1016/j.tcs.2003.10.022
    12 https://doi.org/10.1016/s0304-3975(99)00207-8
    13 https://doi.org/10.1016/s0747-7171(87)80022-6
    14 https://doi.org/10.1017/s0956796800003877
    15 https://doi.org/10.1051/ita:2005029
    16 https://doi.org/10.1109/hicss.2003.1174809
    17 https://doi.org/10.1109/lics.1999.782641
    18 https://doi.org/10.1145/161468.161472
    19 https://doi.org/10.1145/321386.321395
    20 https://doi.org/10.1145/360204.360210
    21 schema:datePublished 2006
    22 schema:datePublishedReg 2006-01-01
    23 schema:description We propose a new method to control memory resources by static analysis. For this, we introduce the notion of sup-interpretation which bounds from above the size of function outputs. We establish a criteria for which the stack frame size is polynomially bounded. The criteria analyses terminating as well as non-terminating programs. This method applies to first order functional programming with pattern matching. This work is related to quasi-interpretations but we are now able to determine resources of different algorithms and it is easier to perform an analysis with this new tools.
    24 schema:editor N04a699a7ef8f4ba08d61e119dc83c85c
    25 schema:genre chapter
    26 schema:inLanguage en
    27 schema:isAccessibleForFree false
    28 schema:isPartOf Nc3ffeda7421c47bcb3f034a47705319f
    29 schema:name Resource Analysis by Sup-interpretation
    30 schema:pagination 163-176
    31 schema:productId N1b2b76716dc14028808009e4589efd8d
    32 N5c64b9e96b22468786cd151ea878b00a
    33 N9caf3aa5a2ee471fa7014b233353a46b
    34 schema:publisher Ndcbd2ac99efc484f8515f01746cd91c2
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018767695
    36 https://doi.org/10.1007/11737414_12
    37 schema:sdDatePublished 2019-04-16T07:29
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher Ndd9ca8c127a14a05ad6bf298e538ad6f
    40 schema:url https://link.springer.com/10.1007%2F11737414_12
    41 sgo:license sg:explorer/license/
    42 sgo:sdDataset chapters
    43 rdf:type schema:Chapter
    44 N04a699a7ef8f4ba08d61e119dc83c85c rdf:first N1aebc9572b214a369ad60afaf4c1d8b3
    45 rdf:rest Nb408694b2dcb4fdc95c8dcc0fbc090f8
    46 N1aebc9572b214a369ad60afaf4c1d8b3 schema:familyName Hagiya
    47 schema:givenName Masami
    48 rdf:type schema:Person
    49 N1b2b76716dc14028808009e4589efd8d schema:name dimensions_id
    50 schema:value pub.1018767695
    51 rdf:type schema:PropertyValue
    52 N53b6bcad4d28418db191ee69680aaea9 rdf:first sg:person.016241557431.75
    53 rdf:rest rdf:nil
    54 N5c64b9e96b22468786cd151ea878b00a schema:name readcube_id
    55 schema:value 596bf4e0956015c6bfb085c6d90df1b0f24b467a4045b0741e71ef1274363fc1
    56 rdf:type schema:PropertyValue
    57 N9caf3aa5a2ee471fa7014b233353a46b schema:name doi
    58 schema:value 10.1007/11737414_12
    59 rdf:type schema:PropertyValue
    60 Na2541c9732a74267a56fc98b0fe25d72 rdf:first sg:person.016702671367.99
    61 rdf:rest N53b6bcad4d28418db191ee69680aaea9
    62 Nb408694b2dcb4fdc95c8dcc0fbc090f8 rdf:first Nd548540db59c41b79d8ba3a2a8dde53a
    63 rdf:rest rdf:nil
    64 Nc3ffeda7421c47bcb3f034a47705319f schema:isbn 978-3-540-33438-5
    65 978-3-540-33439-2
    66 schema:name Functional and Logic Programming
    67 rdf:type schema:Book
    68 Nd548540db59c41b79d8ba3a2a8dde53a schema:familyName Wadler
    69 schema:givenName Philip
    70 rdf:type schema:Person
    71 Ndcbd2ac99efc484f8515f01746cd91c2 schema:location Berlin, Heidelberg
    72 schema:name Springer Berlin Heidelberg
    73 rdf:type schema:Organisation
    74 Ndd9ca8c127a14a05ad6bf298e538ad6f schema:name Springer Nature - SN SciGraph project
    75 rdf:type schema:Organization
    76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Information and Computing Sciences
    78 rdf:type schema:DefinedTerm
    79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    80 schema:name Computation Theory and Mathematics
    81 rdf:type schema:DefinedTerm
    82 sg:person.016241557431.75 schema:affiliation https://www.grid.ac/institutes/grid.473477.4
    83 schema:familyName Péchoux
    84 schema:givenName Romain
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016241557431.75
    86 rdf:type schema:Person
    87 sg:person.016702671367.99 schema:affiliation https://www.grid.ac/institutes/grid.473477.4
    88 schema:familyName Marion
    89 schema:givenName Jean-Yves
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016702671367.99
    91 rdf:type schema:Person
    92 sg:pub.10.1007/3-540-44404-1_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000486298
    93 https://doi.org/10.1007/3-540-44404-1_3
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/3-540-44881-0_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037217022
    96 https://doi.org/10.1007/3-540-44881-0_19
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/3-540-44904-3_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002927224
    99 https://doi.org/10.1007/3-540-44904-3_3
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/3-540-45575-2_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041545494
    102 https://doi.org/10.1007/3-540-45575-2_46
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/3-540-46425-5_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024487659
    105 https://doi.org/10.1007/3-540-46425-5_11
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/978-3-540-30124-0_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007267443
    108 https://doi.org/10.1007/978-3-540-30124-0_22
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1023/b:jars.0000021014.79255.33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051133555
    111 https://doi.org/10.1023/b:jars.0000021014.79255.33
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/j.tcs.2003.10.022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041611540
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1016/s0304-3975(99)00207-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047998683
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1016/s0747-7171(87)80022-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026818855
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1017/s0956796800003877 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040313166
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1051/ita:2005029 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056972217
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1109/hicss.2003.1174809 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093306054
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1109/lics.1999.782641 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095554525
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1145/161468.161472 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009208603
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1145/321386.321395 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018826104
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.1145/360204.360210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013482748
    132 rdf:type schema:CreativeWork
    133 https://www.grid.ac/institutes/grid.473477.4 schema:alternateName École Nationale Supérieure des Mines de Nancy
    134 schema:name Loria, Calligramme project, B.P. 239, 54506 Cedex, Vandœuvre-lès-Nancy, France
    135 École Nationale Supérieure des Mines de Nancy, INPL, France
    136 rdf:type schema:Organization
     




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


    ...