Some Programming Languages for Logspace and Ptime View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Guillaume Bonfante

ABSTRACT

We propose two characterizations of complexity classes by means of programming languages. The first concerns Logspace while the second leads to Ptime. This latter characterization shows that adding a choice command to a Ptime language (the language WHILE of Jones [1]) may not necessarily provide NPtime computations. The result is close to Cook in [2] who used “auxiliary push-down automata”. Logspace is obtained through a decidable mechanism of tiering. It is based on an analysis of deforestation due to Wadler in [3]. We get also a characterization of NLogspace. More... »

PAGES

66-80

References to SciGraph publications

  • 1992-06. A new recursion-theoretic characterization of the polytime functions in COMPUTATIONAL COMPLEXITY
  • 1993. Lambda calculus characterizations of poly-time in TYPED LAMBDA CALCULI AND APPLICATIONS
  • 2004. A Functional Language for Logarithmic Space in PROGRAMMING LANGUAGES AND SYSTEMS
  • 2002-01. A term rewriting characterization of the functions computable in polynomial space in ARCHIVE FOR MATHEMATICAL LOGIC
  • 1988. Deforestation: Transforming programs to eliminate trees in ESOP '88
  • 2001. On Lexicographic Termination Ordering with Space Bound Certifications in PERSPECTIVES OF SYSTEM INFORMATICS
  • 2005. Quasi-interpretations and Small Space Bounds in TERM REWRITING AND APPLICATIONS
  • 1997. Predicative functional recurrence and poly-space in TAPSOFT '97: THEORY AND PRACTICE OF SOFTWARE DEVELOPMENT
  • Book

    TITLE

    Algebraic Methodology and Software Technology

    ISBN

    978-3-540-35633-2
    978-3-540-35636-3

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11784180_8

    DOI

    http://dx.doi.org/10.1007/11784180_8

    DIMENSIONS

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


    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/2004", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Linguistics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Language, Communication and Culture", 
            "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": "Bonfante", 
            "givenName": "Guillaume", 
            "id": "sg:person.010426674211.24", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010426674211.24"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-19027-9_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002106122", 
              "https://doi.org/10.1007/3-540-19027-9_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01201998", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007256989", 
              "https://doi.org/10.1007/bf01201998"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01201998", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007256989", 
              "https://doi.org/10.1007/bf01201998"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(99)00209-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009612334"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s001530200002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009677925", 
              "https://doi.org/10.1007/s001530200002"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s001530200002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009677925", 
              "https://doi.org/10.1007/s001530200002"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0030611", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011909508", 
              "https://doi.org/10.1007/bfb0030611"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321623.321625", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014684553"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2275767", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020272537"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30477-7_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031551776", 
              "https://doi.org/10.1007/978-3-540-30477-7_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30477-7_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031551776", 
              "https://doi.org/10.1007/978-3-540-30477-7_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-32033-3_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040944011", 
              "https://doi.org/10.1007/978-3-540-32033-3_12"
            ], 
            "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/s0304-3975(98)00357-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044396155"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/565816.503297", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049560968"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0037112", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050153123", 
              "https://doi.org/10.1007/bfb0037112"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/lics.1999.782641", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095554525"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/503272.503297", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098927424"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2006", 
        "datePublishedReg": "2006-01-01", 
        "description": "We propose two characterizations of complexity classes by means of programming languages. The first concerns Logspace while the second leads to Ptime. This latter characterization shows that adding a choice command to a Ptime language (the language WHILE of Jones [1]) may not necessarily provide NPtime computations. The result is close to Cook in [2] who used \u201cauxiliary push-down automata\u201d. Logspace is obtained through a decidable mechanism of tiering. It is based on an analysis of deforestation due to Wadler in [3]. We get also a characterization of NLogspace.", 
        "editor": [
          {
            "familyName": "Johnson", 
            "givenName": "Michael", 
            "type": "Person"
          }, 
          {
            "familyName": "Vene", 
            "givenName": "Varmo", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11784180_8", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-35633-2", 
            "978-3-540-35636-3"
          ], 
          "name": "Algebraic Methodology and Software Technology", 
          "type": "Book"
        }, 
        "name": "Some Programming Languages for Logspace and Ptime", 
        "pagination": "66-80", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045363669"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11784180_8"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d8162a420f0077b4d81d6d04e39df031efc69ff981f73870e0cacf3fec086db8"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11784180_8", 
          "https://app.dimensions.ai/details/publication/pub.1045363669"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:31", 
        "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_57894_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11784180_8"
      }
    ]
     

    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/11784180_8'

    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/11784180_8'

    Turtle is a human-readable linked data format.

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

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

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


     

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

    124 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11784180_8 schema:about anzsrc-for:20
    2 anzsrc-for:2004
    3 schema:author N1780f473bd614c7388da0aea99a82d26
    4 schema:citation sg:pub.10.1007/3-540-19027-9_23
    5 sg:pub.10.1007/3-540-45575-2_46
    6 sg:pub.10.1007/978-3-540-30477-7_21
    7 sg:pub.10.1007/978-3-540-32033-3_12
    8 sg:pub.10.1007/bf01201998
    9 sg:pub.10.1007/bfb0030611
    10 sg:pub.10.1007/bfb0037112
    11 sg:pub.10.1007/s001530200002
    12 https://doi.org/10.1016/s0304-3975(98)00357-0
    13 https://doi.org/10.1016/s0304-3975(99)00209-1
    14 https://doi.org/10.1109/lics.1999.782641
    15 https://doi.org/10.1145/321623.321625
    16 https://doi.org/10.1145/503272.503297
    17 https://doi.org/10.1145/565816.503297
    18 https://doi.org/10.2307/2275767
    19 schema:datePublished 2006
    20 schema:datePublishedReg 2006-01-01
    21 schema:description We propose two characterizations of complexity classes by means of programming languages. The first concerns Logspace while the second leads to Ptime. This latter characterization shows that adding a choice command to a Ptime language (the language WHILE of Jones [1]) may not necessarily provide NPtime computations. The result is close to Cook in [2] who used “auxiliary push-down automata”. Logspace is obtained through a decidable mechanism of tiering. It is based on an analysis of deforestation due to Wadler in [3]. We get also a characterization of NLogspace.
    22 schema:editor N0dda3375836e4f859e1af6587e6e2cfb
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree false
    26 schema:isPartOf N40bb69f18a104fe6be073afba16f0205
    27 schema:name Some Programming Languages for Logspace and Ptime
    28 schema:pagination 66-80
    29 schema:productId N5743da6789d9478db8b9a9cc856c1dfe
    30 N9d51b7f8cf2c4963aac29559afc33abc
    31 Nefc882e03a37471db906fc776bce9c00
    32 schema:publisher N96b18ef76804443f82dcf8b0a6a7697b
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045363669
    34 https://doi.org/10.1007/11784180_8
    35 schema:sdDatePublished 2019-04-16T07:31
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher Ncceaea9934e84fb388884088d10d2599
    38 schema:url https://link.springer.com/10.1007%2F11784180_8
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset chapters
    41 rdf:type schema:Chapter
    42 N0dda3375836e4f859e1af6587e6e2cfb rdf:first N340daa1cf63e444dbc1a3cd88f0ba294
    43 rdf:rest N992b814c63fd4d8098ec4091d321bda1
    44 N1780f473bd614c7388da0aea99a82d26 rdf:first sg:person.010426674211.24
    45 rdf:rest rdf:nil
    46 N340daa1cf63e444dbc1a3cd88f0ba294 schema:familyName Johnson
    47 schema:givenName Michael
    48 rdf:type schema:Person
    49 N40bb69f18a104fe6be073afba16f0205 schema:isbn 978-3-540-35633-2
    50 978-3-540-35636-3
    51 schema:name Algebraic Methodology and Software Technology
    52 rdf:type schema:Book
    53 N5743da6789d9478db8b9a9cc856c1dfe schema:name dimensions_id
    54 schema:value pub.1045363669
    55 rdf:type schema:PropertyValue
    56 N96b18ef76804443f82dcf8b0a6a7697b schema:location Berlin, Heidelberg
    57 schema:name Springer Berlin Heidelberg
    58 rdf:type schema:Organisation
    59 N992b814c63fd4d8098ec4091d321bda1 rdf:first Nb53f520cf98f4fb8b9b5cf0d4af809dd
    60 rdf:rest rdf:nil
    61 N9d51b7f8cf2c4963aac29559afc33abc schema:name readcube_id
    62 schema:value d8162a420f0077b4d81d6d04e39df031efc69ff981f73870e0cacf3fec086db8
    63 rdf:type schema:PropertyValue
    64 Nb53f520cf98f4fb8b9b5cf0d4af809dd schema:familyName Vene
    65 schema:givenName Varmo
    66 rdf:type schema:Person
    67 Ncceaea9934e84fb388884088d10d2599 schema:name Springer Nature - SN SciGraph project
    68 rdf:type schema:Organization
    69 Nefc882e03a37471db906fc776bce9c00 schema:name doi
    70 schema:value 10.1007/11784180_8
    71 rdf:type schema:PropertyValue
    72 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Language, Communication and Culture
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Linguistics
    77 rdf:type schema:DefinedTerm
    78 sg:person.010426674211.24 schema:affiliation https://www.grid.ac/institutes/grid.473477.4
    79 schema:familyName Bonfante
    80 schema:givenName Guillaume
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010426674211.24
    82 rdf:type schema:Person
    83 sg:pub.10.1007/3-540-19027-9_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002106122
    84 https://doi.org/10.1007/3-540-19027-9_23
    85 rdf:type schema:CreativeWork
    86 sg:pub.10.1007/3-540-45575-2_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041545494
    87 https://doi.org/10.1007/3-540-45575-2_46
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/978-3-540-30477-7_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031551776
    90 https://doi.org/10.1007/978-3-540-30477-7_21
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/978-3-540-32033-3_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040944011
    93 https://doi.org/10.1007/978-3-540-32033-3_12
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/bf01201998 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007256989
    96 https://doi.org/10.1007/bf01201998
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/bfb0030611 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011909508
    99 https://doi.org/10.1007/bfb0030611
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/bfb0037112 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050153123
    102 https://doi.org/10.1007/bfb0037112
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/s001530200002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009677925
    105 https://doi.org/10.1007/s001530200002
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/s0304-3975(98)00357-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044396155
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/s0304-3975(99)00209-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009612334
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1109/lics.1999.782641 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095554525
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1145/321623.321625 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014684553
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1145/503272.503297 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098927424
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1145/565816.503297 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049560968
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.2307/2275767 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020272537
    120 rdf:type schema:CreativeWork
    121 https://www.grid.ac/institutes/grid.473477.4 schema:alternateName École Nationale Supérieure des Mines de Nancy
    122 schema:name Loria, Calligramme project, B.P. 239, 54506 Cedex, Vandœuvre-lès-Nancy, France
    123 École Nationale Supérieure des Mines de Nancy, INPL, France
    124 rdf:type schema:Organization
     




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


    ...