2017
AUTHORSPatricia Bouyer , Piotr Hofman , Nicolas Markey , Mickael Randour , Martin Zimmermann
ABSTRACTWe consider average-energy games, where the goal is to minimize the long-run average of the accumulated energy. While several results have been obtained on these games recently, decidability of average-energy games with a lower-bound constraint on the energy level (but no upper bound) remained open; in particular, so far there was no known upper bound on the memory that is required for winning strategies. By reducing average-energy games with lower-bounded energy to infinite-state mean-payoff games and analyzing the density of low-energy configurations, we show an almost tight doubly-exponential upper bound on the necessary memory, and prove that the winner of average-energy games with lower-bounded energy can be determined in doubly-exponential time. We also prove Open image in new window-hardness of this problem. Finally, we consider multi-dimensional extensions of all types of average-energy games: without bounds, with only a lower bound, and with both a lower and an upper bound on the energy. We show that the fully-bounded version is the only case to remain decidable in multiple dimensions. More... »
PAGES179-195
Foundations of Software Science and Computation Structures
ISBN
978-3-662-54457-0
978-3-662-54458-7
http://scigraph.springernature.com/pub.10.1007/978-3-662-54458-7_11
DOIhttp://dx.doi.org/10.1007/978-3-662-54458-7_11
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1084728175
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/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"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": "Laboratoire Sp\u00e9cification et V\u00e9rification",
"id": "https://www.grid.ac/institutes/grid.464035.0",
"name": [
"LSV, CNRS & ENS Cachan Universit\u00e9 Paris Saclay Cachan France"
],
"type": "Organization"
},
"familyName": "Bouyer",
"givenName": "Patricia",
"id": "sg:person.014467443251.73",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014467443251.73"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Warsaw",
"id": "https://www.grid.ac/institutes/grid.12847.38",
"name": [
"LSV, CNRS & ENS Cachan Universit\u00e9 Paris Saclay Cachan France",
"University of Warsaw Warszawa Poland"
],
"type": "Organization"
},
"familyName": "Hofman",
"givenName": "Piotr",
"id": "sg:person.012777200657.31",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012777200657.31"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institut de Recherche en Informatique et Syst\u00e8mes Al\u00e9atoires",
"id": "https://www.grid.ac/institutes/grid.420225.3",
"name": [
"LSV, CNRS & ENS Cachan Universit\u00e9 Paris Saclay Cachan France",
"IRISA, CNRS & INRIA & U. Rennes 1 Rennes France"
],
"type": "Organization"
},
"familyName": "Markey",
"givenName": "Nicolas",
"id": "sg:person.07601744130.31",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07601744130.31"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Universit\u00e9 Libre de Bruxelles",
"id": "https://www.grid.ac/institutes/grid.4989.c",
"name": [
"Computer Science Department ULB - Universit\u00e9 Libre de Bruxelles Brussels Belgium"
],
"type": "Organization"
},
"familyName": "Randour",
"givenName": "Mickael",
"id": "sg:person.016525130237.39",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016525130237.39"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Saarland University",
"id": "https://www.grid.ac/institutes/grid.11749.3a",
"name": [
"Reactive Systems Group Saarland University Saarbr\u00fccken Germany"
],
"type": "Organization"
},
"familyName": "Zimmermann",
"givenName": "Martin",
"id": "sg:person.010652217057.74",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010652217057.74"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-662-47666-6_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008878122",
"https://doi.org/10.1007/978-3-662-47666-6_21"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ic.2015.03.001",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010847376"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ic.2015.03.001",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010847376"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ic.2015.03.010",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013377026"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ic.2014.12.004",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017400081"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.tcs.2012.07.038",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017993333"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00236-013-0182-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018480690",
"https://doi.org/10.1007/s00236-013-0182-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01768705",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021856463",
"https://doi.org/10.1007/bf01768705"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01768705",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021856463",
"https://doi.org/10.1007/bf01768705"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-24537-9_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024001381",
"https://doi.org/10.1007/978-3-319-24537-9_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10703-010-0105-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027686195",
"https://doi.org/10.1007/s10703-010-0105-x"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-02658-4_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034421154",
"https://doi.org/10.1007/978-3-642-02658-4_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-02658-4_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034421154",
"https://doi.org/10.1007/978-3-642-02658-4_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45212-6_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034896734",
"https://doi.org/10.1007/978-3-540-45212-6_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45212-6_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034896734",
"https://doi.org/10.1007/978-3-540-45212-6_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-00602-9_7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036660750",
"https://doi.org/10.1007/978-3-642-00602-9_7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-00602-9_7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036660750",
"https://doi.org/10.1007/978-3-642-00602-9_7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01732644",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038261869",
"https://doi.org/10.1007/bf01732644"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00236-016-0274-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039997237",
"https://doi.org/10.1007/s00236-016-0274-1"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00236-016-0274-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039997237",
"https://doi.org/10.1007/s00236-016-0274-1"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(78)90011-0",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1040432621"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0304-3975(95)00188-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041478813"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-00395-5_90",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044793646",
"https://doi.org/10.1007/978-3-319-00395-5_90"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-85778-5_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046321257",
"https://doi.org/10.1007/978-3-540-85778-5_4"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1006/inco.2000.2894",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046428528"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-39698-4_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047231693",
"https://doi.org/10.1007/978-3-642-39698-4_15"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.4204/eptcs.227.1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1072355958"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.4204/eptcs.96.14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1072356969"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/lics.2012.30",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095598064"
],
"type": "CreativeWork"
}
],
"datePublished": "2017",
"datePublishedReg": "2017-01-01",
"description": "We consider average-energy games, where the goal is to minimize the long-run average of the accumulated energy. While several results have been obtained on these games recently, decidability of average-energy games with a lower-bound constraint on the energy level (but no upper bound) remained open; in particular, so far there was no known upper bound on the memory that is required for winning strategies. By reducing average-energy games with lower-bounded energy to infinite-state mean-payoff games and analyzing the density of low-energy configurations, we show an almost tight doubly-exponential upper bound on the necessary memory, and prove that the winner of average-energy games with lower-bounded energy can be determined in doubly-exponential time. We also prove Open image in new window-hardness of this problem. Finally, we consider multi-dimensional extensions of all types of average-energy games: without bounds, with only a lower bound, and with both a lower and an upper bound on the energy. We show that the fully-bounded version is the only case to remain decidable in multiple dimensions.",
"editor": [
{
"familyName": "Esparza",
"givenName": "Javier",
"type": "Person"
},
{
"familyName": "Murawski",
"givenName": "Andrzej S.",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-662-54458-7_11",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isFundedItemOf": [
{
"id": "sg:grant.3795792",
"type": "MonetaryGrant"
}
],
"isPartOf": {
"isbn": [
"978-3-662-54457-0",
"978-3-662-54458-7"
],
"name": "Foundations of Software Science and Computation Structures",
"type": "Book"
},
"name": "Bounding Average-Energy Games",
"pagination": "179-195",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-662-54458-7_11"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"dc367c019010e8575e230214f500bd24b9389bd1a4ea53e2bde1cae88c4e671e"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1084728175"
]
}
],
"publisher": {
"location": "Berlin, Heidelberg",
"name": "Springer Berlin Heidelberg",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-662-54458-7_11",
"https://app.dimensions.ai/details/publication/pub.1084728175"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T13:38",
"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_00000331.jsonl",
"type": "Chapter",
"url": "http://link.springer.com/10.1007/978-3-662-54458-7_11"
}
]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-662-54458-7_11'
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-662-54458-7_11'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-54458-7_11'
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-662-54458-7_11'
This table displays all metadata directly associated to this object as RDF triples.
196 TRIPLES
23 PREDICATES
50 URIs
20 LITERALS
8 BLANK NODES