Relating Accumulative and Non-accumulative Functional Programs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001

AUTHORS

Armin Kühnemann , Robert Glück , Kazuhiko Kakehi

ABSTRACT

We study the problem to transform functional programs, which intensively use append functions (like inefficient list reversal), into programs, which use accumulating parameters instead (like eficient list reversal). We give an (automatic) transformation algorithm for our problem and identify a class of functional programs, namely restricted 2-modular tree transducers, to which it can be applied. Moreover, since we get macro tree transducers as transformation result and since we also give the inverse transformation algorithm, we have a new characterization for the class of functions induced by macro tree transducers. More... »

PAGES

154-168

References to SciGraph publications

  • 1988-05. Composition and evaluation of attribute coupled grammars in ACTA INFORMATICA
  • 1970-09. Mappings and grammars on trees in MATHEMATICAL SYSTEMS THEORY
  • 1968-06. Semantics of context-free languages in MATHEMATICAL SYSTEMS THEORY
  • Book

    TITLE

    Rewriting Techniques and Applications

    ISBN

    978-3-540-42117-7
    978-3-540-45127-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-45127-7_13

    DOI

    http://dx.doi.org/10.1007/3-540-45127-7_13

    DIMENSIONS

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


    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/0303", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Macromolecular and Materials Chemistry", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/03", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Chemical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "TU Dresden", 
              "id": "https://www.grid.ac/institutes/grid.4488.0", 
              "name": [
                "Institute for Theoretical Computer Science, Department of Computer Science, Dresden University of Technology, D-01062\u00a0Dresden, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "K\u00fchnemann", 
            "givenName": "Armin", 
            "id": "sg:person.015633306630.74", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015633306630.74"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Waseda University", 
              "id": "https://www.grid.ac/institutes/grid.5290.e", 
              "name": [
                "Institute for Software Production Technology, Waseda University, 3-4-1 Okubo, Shinjuku, Tokyo\u00a0169-8555, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gl\u00fcck", 
            "givenName": "Robert", 
            "id": "sg:person.010754010217.31", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Waseda University", 
              "id": "https://www.grid.ac/institutes/grid.5290.e", 
              "name": [
                "Institute for Software Production Technology, Waseda University, 3-4-1 Okubo, Shinjuku, Tokyo\u00a0169-8555, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kakehi", 
            "givenName": "Kazuhiko", 
            "id": "sg:person.012530056042.57", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012530056042.57"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1017/s0956796800001179", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004319108"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(85)90066-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012161455"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(82)90003-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012802714"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/5956.5957", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016193336"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(90)90147-a", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019824477"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01692511", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025480202", 
              "https://doi.org/10.1007/bf01692511"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01692511", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025480202", 
              "https://doi.org/10.1007/bf01692511"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01692511", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025480202", 
              "https://doi.org/10.1007/bf01692511"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(93)90191-u", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034684746"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02737108", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039434342", 
              "https://doi.org/10.1007/bf02737108"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02737108", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039434342", 
              "https://doi.org/10.1007/bf02737108"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(91)90353-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039571087"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-6423(83)90021-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043873783"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2001", 
        "datePublishedReg": "2001-01-01", 
        "description": "We study the problem to transform functional programs, which intensively use append functions (like inefficient list reversal), into programs, which use accumulating parameters instead (like eficient list reversal). We give an (automatic) transformation algorithm for our problem and identify a class of functional programs, namely restricted 2-modular tree transducers, to which it can be applied. Moreover, since we get macro tree transducers as transformation result and since we also give the inverse transformation algorithm, we have a new characterization for the class of functions induced by macro tree transducers.", 
        "editor": [
          {
            "familyName": "Middeldorp", 
            "givenName": "Aart", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-45127-7_13", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-42117-7", 
            "978-3-540-45127-3"
          ], 
          "name": "Rewriting Techniques and Applications", 
          "type": "Book"
        }, 
        "name": "Relating Accumulative and Non-accumulative Functional Programs", 
        "pagination": "154-168", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-45127-7_13"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5ae3eb024741a70e92fabb5c15551844f46b276a096476dcf9fcdf09e0e54284"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1019075739"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-45127-7_13", 
          "https://app.dimensions.ai/details/publication/pub.1019075739"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T13:27", 
        "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_8664_00000255.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-45127-7_13"
      }
    ]
     

    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-45127-7_13'

    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-45127-7_13'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45127-7_13'

    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-45127-7_13'


     

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

    118 TRIPLES      23 PREDICATES      38 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-45127-7_13 schema:about anzsrc-for:03
    2 anzsrc-for:0303
    3 schema:author N6b49fd5d41f748fcb7a9ff48ee7d908b
    4 schema:citation sg:pub.10.1007/bf01692511
    5 sg:pub.10.1007/bf01695769
    6 sg:pub.10.1007/bf02737108
    7 https://doi.org/10.1016/0022-0000(85)90066-2
    8 https://doi.org/10.1016/0167-6423(83)90021-7
    9 https://doi.org/10.1016/0304-3975(82)90003-2
    10 https://doi.org/10.1016/0304-3975(90)90147-a
    11 https://doi.org/10.1016/0304-3975(91)90353-4
    12 https://doi.org/10.1016/0304-3975(93)90191-u
    13 https://doi.org/10.1017/s0956796800001179
    14 https://doi.org/10.1145/5956.5957
    15 schema:datePublished 2001
    16 schema:datePublishedReg 2001-01-01
    17 schema:description We study the problem to transform functional programs, which intensively use append functions (like inefficient list reversal), into programs, which use accumulating parameters instead (like eficient list reversal). We give an (automatic) transformation algorithm for our problem and identify a class of functional programs, namely restricted 2-modular tree transducers, to which it can be applied. Moreover, since we get macro tree transducers as transformation result and since we also give the inverse transformation algorithm, we have a new characterization for the class of functions induced by macro tree transducers.
    18 schema:editor N6a4a22f44e09458da76eda12624dbdda
    19 schema:genre chapter
    20 schema:inLanguage en
    21 schema:isAccessibleForFree false
    22 schema:isPartOf Nf784790771104fd4aff023eab954de36
    23 schema:name Relating Accumulative and Non-accumulative Functional Programs
    24 schema:pagination 154-168
    25 schema:productId N0297b42db886482783f4d46b1263089b
    26 N54df0bad0da64cc6a2c1a2b66e7fea28
    27 N9289bc55e9394556a95953e6ac411892
    28 schema:publisher N4df4f18335754b93a7cf3f3d73e6500d
    29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019075739
    30 https://doi.org/10.1007/3-540-45127-7_13
    31 schema:sdDatePublished 2019-04-15T13:27
    32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    33 schema:sdPublisher Ne4e428b5cecf47399145e63555d92ade
    34 schema:url http://link.springer.com/10.1007/3-540-45127-7_13
    35 sgo:license sg:explorer/license/
    36 sgo:sdDataset chapters
    37 rdf:type schema:Chapter
    38 N0297b42db886482783f4d46b1263089b schema:name doi
    39 schema:value 10.1007/3-540-45127-7_13
    40 rdf:type schema:PropertyValue
    41 N4df4f18335754b93a7cf3f3d73e6500d schema:location Berlin, Heidelberg
    42 schema:name Springer Berlin Heidelberg
    43 rdf:type schema:Organisation
    44 N54df0bad0da64cc6a2c1a2b66e7fea28 schema:name readcube_id
    45 schema:value 5ae3eb024741a70e92fabb5c15551844f46b276a096476dcf9fcdf09e0e54284
    46 rdf:type schema:PropertyValue
    47 N6a4a22f44e09458da76eda12624dbdda rdf:first Nccee24b52b6749dbb2eaab0e4e8838ad
    48 rdf:rest rdf:nil
    49 N6b49fd5d41f748fcb7a9ff48ee7d908b rdf:first sg:person.015633306630.74
    50 rdf:rest Nee02b388edf442298e8a3241d46ed9f6
    51 N9289bc55e9394556a95953e6ac411892 schema:name dimensions_id
    52 schema:value pub.1019075739
    53 rdf:type schema:PropertyValue
    54 Nccee24b52b6749dbb2eaab0e4e8838ad schema:familyName Middeldorp
    55 schema:givenName Aart
    56 rdf:type schema:Person
    57 Ne4e428b5cecf47399145e63555d92ade schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 Nee02b388edf442298e8a3241d46ed9f6 rdf:first sg:person.010754010217.31
    60 rdf:rest Nf72e88a2c90b42549eb8e86643dde393
    61 Nf72e88a2c90b42549eb8e86643dde393 rdf:first sg:person.012530056042.57
    62 rdf:rest rdf:nil
    63 Nf784790771104fd4aff023eab954de36 schema:isbn 978-3-540-42117-7
    64 978-3-540-45127-3
    65 schema:name Rewriting Techniques and Applications
    66 rdf:type schema:Book
    67 anzsrc-for:03 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Chemical Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0303 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Macromolecular and Materials Chemistry
    72 rdf:type schema:DefinedTerm
    73 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
    74 schema:familyName Glück
    75 schema:givenName Robert
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    77 rdf:type schema:Person
    78 sg:person.012530056042.57 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
    79 schema:familyName Kakehi
    80 schema:givenName Kazuhiko
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012530056042.57
    82 rdf:type schema:Person
    83 sg:person.015633306630.74 schema:affiliation https://www.grid.ac/institutes/grid.4488.0
    84 schema:familyName Kühnemann
    85 schema:givenName Armin
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015633306630.74
    87 rdf:type schema:Person
    88 sg:pub.10.1007/bf01692511 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025480202
    89 https://doi.org/10.1007/bf01692511
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/bf01695769 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033919759
    92 https://doi.org/10.1007/bf01695769
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/bf02737108 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039434342
    95 https://doi.org/10.1007/bf02737108
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/0022-0000(85)90066-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012161455
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0167-6423(83)90021-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043873783
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/0304-3975(82)90003-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012802714
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/0304-3975(90)90147-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1019824477
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/0304-3975(91)90353-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039571087
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/0304-3975(93)90191-u schema:sameAs https://app.dimensions.ai/details/publication/pub.1034684746
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1017/s0956796800001179 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004319108
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1145/5956.5957 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016193336
    112 rdf:type schema:CreativeWork
    113 https://www.grid.ac/institutes/grid.4488.0 schema:alternateName TU Dresden
    114 schema:name Institute for Theoretical Computer Science, Department of Computer Science, Dresden University of Technology, D-01062 Dresden, Germany
    115 rdf:type schema:Organization
    116 https://www.grid.ac/institutes/grid.5290.e schema:alternateName Waseda University
    117 schema:name Institute for Software Production Technology, Waseda University, 3-4-1 Okubo, Shinjuku, Tokyo 169-8555, Japan
    118 rdf:type schema:Organization
     




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


    ...