Ontology type: schema:Chapter Open Access: True
2008
AUTHORSJean-Yves Marion , Romain Péchoux
ABSTRACTThis paper is part of a research on static analysis in order to predict program resources and belongs to the implicit computational complexity line of research. It presents intrinsic characterizations of the classes of functions, which are computable in , that is by a uniform, poly-logarithmic depth and polynomial size family of circuits, using first order functional programs. Our characterizations are new in terms of first order functional programming language and extend the characterization of in [9]. These characterizations are obtained using a complexity measure, the sup-interpretation, which gives upper bounds on the size of computed values and captures a lot of program schemas. More... »
PAGES136-147
Theory and Applications of Models of Computation
ISBN
978-3-540-79227-7
978-3-540-79228-4
http://scigraph.springernature.com/pub.10.1007/978-3-540-79228-4_12
DOIhttp://dx.doi.org/10.1007/978-3-540-79228-4_12
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1026553376
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-INPL, \u00c9cole Nationale Sup\u00e9rieure des Mines de Nancy, B.P. 239, 54506, Vand\u0153uvre-l\u00e8s-Nancy Cedex, 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-INPL, \u00c9cole Nationale Sup\u00e9rieure des Mines de Nancy, B.P. 239, 54506, Vand\u0153uvre-l\u00e8s-Nancy Cedex, 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": "https://doi.org/10.1145/346048.346051",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005765514"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11874683_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006062970",
"https://doi.org/10.1007/11874683_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11874683_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006062970",
"https://doi.org/10.1007/11874683_14"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0022-0000(90)90022-d",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007070716"
],
"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/0304-3975(92)90386-t",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007694429"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.tcs.2003.10.018",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008459023"
],
"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": "https://doi.org/10.1145/322217.322230",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010875099"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11916277_7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012388623",
"https://doi.org/10.1007/11916277_7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11916277_7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012388623",
"https://doi.org/10.1007/11916277_7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01202288",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015506435",
"https://doi.org/10.1007/bf01202288"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01202288",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015506435",
"https://doi.org/10.1007/bf01202288"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0890-5401(90)90063-n",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017490867"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11737414_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018767695",
"https://doi.org/10.1007/11737414_12"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11737414_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018767695",
"https://doi.org/10.1007/11737414_12"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-24727-2_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1020241211",
"https://doi.org/10.1007/978-3-540-24727-2_4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-24727-2_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1020241211",
"https://doi.org/10.1007/978-3-540-24727-2_4"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1006/inco.1998.2700",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029192341"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-60178-3_81",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029652351",
"https://doi.org/10.1007/3-540-60178-3_81"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4612-3466-1_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031303856",
"https://doi.org/10.1007/978-1-4612-3466-1_4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4612-3466-1_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031303856",
"https://doi.org/10.1007/978-1-4612-3466-1_4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-74915-8_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032657209",
"https://doi.org/10.1007/978-3-540-74915-8_21"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-74915-8_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032657209",
"https://doi.org/10.1007/978-3-540-74915-8_21"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/28395.28409",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037335279"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11494645_33",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038435051",
"https://doi.org/10.1007/11494645_33"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11494645_33",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038435051",
"https://doi.org/10.1007/11494645_33"
],
"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/0022-0000(81)90038-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053111440"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/s0097539704445597",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062879554"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/sfcs.1998.743522",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095275026"
],
"type": "CreativeWork"
}
],
"datePublished": "2008",
"datePublishedReg": "2008-01-01",
"description": "This paper is part of a research on static analysis in order to predict program resources and belongs to the implicit computational complexity line of research. It presents intrinsic characterizations of the classes of functions, which are computable in , that is by a uniform, poly-logarithmic depth and polynomial size family of circuits, using first order functional programs. Our characterizations are new in terms of first order functional programming language and extend the characterization of in [9]. These characterizations are obtained using a complexity measure, the sup-interpretation, which gives upper bounds on the size of computed values and captures a lot of program schemas.",
"editor": [
{
"familyName": "Agrawal",
"givenName": "Manindra",
"type": "Person"
},
{
"familyName": "Du",
"givenName": "Dingzhu",
"type": "Person"
},
{
"familyName": "Duan",
"givenName": "Zhenhua",
"type": "Person"
},
{
"familyName": "Li",
"givenName": "Angsheng",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-79228-4_12",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-79227-7",
"978-3-540-79228-4"
],
"name": "Theory and Applications of Models of Computation",
"type": "Book"
},
"name": "A Characterization of NCk by First Order Functional Programs",
"pagination": "136-147",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-79228-4_12"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"7e8029492fb06726a90baa1387b74b1837c91198bd65f05151c6701ef63820d4"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1026553376"
]
}
],
"publisher": {
"location": "Berlin, Heidelberg",
"name": "Springer Berlin Heidelberg",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-79228-4_12",
"https://app.dimensions.ai/details/publication/pub.1026553376"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-16T06:04",
"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/0000000349_0000000349/records_113673_00000001.jsonl",
"type": "Chapter",
"url": "https://link.springer.com/10.1007%2F978-3-540-79228-4_12"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/978-3-540-79228-4_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/978-3-540-79228-4_12'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-79228-4_12'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-79228-4_12'
This table displays all metadata directly associated to this object as RDF triples.
167 TRIPLES
23 PREDICATES
50 URIs
20 LITERALS
8 BLANK NODES