Ontology type: schema:ScholarlyArticle Open Access: True
2010-12-08
AUTHORSL. Brim, J. Chaloupka, L. Doyen, R. Gentilini, J. F. Raskin
ABSTRACTIn this paper, we study algorithmic problems for quantitative models that are motivated by the applications in modeling embedded systems. We consider two-player games played on a weighted graph with mean-payoff objective and with energy constraints. We present a new pseudopolynomial algorithm for solving such games, improving the best known worst-case complexity for pseudopolynomial mean-payoff algorithms. Our algorithm can also be combined with the procedure by Andersson and Vorobyov to obtain a randomized algorithm with currently the best expected time complexity. The proposed solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games. Our results imply also that energy games and mean-payoff games can be reduced to safety games in pseudopolynomial time. More... »
PAGES97-118
http://scigraph.springernature.com/pub.10.1007/s10703-010-0105-x
DOIhttp://dx.doi.org/10.1007/s10703-010-0105-x
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1027686195
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/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"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"
}
],
"author": [
{
"affiliation": {
"alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic",
"id": "http://www.grid.ac/institutes/grid.10267.32",
"name": [
"Faculty of Informatics, Masaryk University, Brno, Czech Republic"
],
"type": "Organization"
},
"familyName": "Brim",
"givenName": "L.",
"id": "sg:person.0645117057.83",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0645117057.83"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic",
"id": "http://www.grid.ac/institutes/grid.10267.32",
"name": [
"Faculty of Informatics, Masaryk University, Brno, Czech Republic"
],
"type": "Organization"
},
"familyName": "Chaloupka",
"givenName": "J.",
"id": "sg:person.013233527367.47",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233527367.47"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "LSV, ENS Cachan & CNRS, Cachan, France",
"id": "http://www.grid.ac/institutes/grid.464035.0",
"name": [
"Computer Science Department, Universit\u00e9 Libre de Bruxelles (U.L.B.), Brussels, Belgium",
"LSV, ENS Cachan & CNRS, Cachan, France"
],
"type": "Organization"
},
"familyName": "Doyen",
"givenName": "L.",
"id": "sg:person.010301575457.70",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010301575457.70"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics and Informatics, University of Perugia, Perugia, Italy",
"id": "http://www.grid.ac/institutes/grid.9027.c",
"name": [
"Computer Science Department, Universit\u00e9 Libre de Bruxelles (U.L.B.), Brussels, Belgium",
"Department of Mathematics and Informatics, University of Perugia, Perugia, Italy"
],
"type": "Organization"
},
"familyName": "Gentilini",
"givenName": "R.",
"id": "sg:person.016064406033.00",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016064406033.00"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Computer Science Department, Universit\u00e9 Libre de Bruxelles (U.L.B.), Brussels, Belgium",
"id": "http://www.grid.ac/institutes/grid.4989.c",
"name": [
"Computer Science Department, Universit\u00e9 Libre de Bruxelles (U.L.B.), Brussels, Belgium"
],
"type": "Organization"
},
"familyName": "Raskin",
"givenName": "J. F.",
"id": "sg:person.010207023561.22",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010207023561.22"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/s10958-007-0331-y",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002530809",
"https://doi.org/10.1007/s10958-007-0331-y"
],
"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/3-540-46541-3_24",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044781598",
"https://doi.org/10.1007/3-540-46541-3_24"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4612-0931-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044704735",
"https://doi.org/10.1007/978-1-4612-0931-7"
],
"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": "sg:pub.10.1007/3-540-61474-5_58",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009044758",
"https://doi.org/10.1007/3-540-61474-5_58"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-56922-7_32",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006655742",
"https://doi.org/10.1007/3-540-56922-7_32"
],
"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/bf01580616",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036721262",
"https://doi.org/10.1007/bf01580616"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-03816-7_57",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039939811",
"https://doi.org/10.1007/978-3-642-03816-7_57"
],
"type": "CreativeWork"
}
],
"datePublished": "2010-12-08",
"datePublishedReg": "2010-12-08",
"description": "In this paper, we study algorithmic problems for quantitative models that are motivated by the applications in modeling embedded systems. We consider two-player games played on a weighted graph with mean-payoff objective and with energy constraints. We present a new pseudopolynomial algorithm for solving such games, improving the best known worst-case complexity for pseudopolynomial mean-payoff algorithms. Our algorithm can also be combined with the procedure by Andersson and Vorobyov to obtain a randomized algorithm with currently the best expected time complexity. The proposed solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games. Our results imply also that energy games and mean-payoff games can be reduced to safety games in pseudopolynomial time.",
"genre": "article",
"id": "sg:pub.10.1007/s10703-010-0105-x",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1052628",
"issn": [
"0925-9856",
"1572-8102"
],
"name": "Formal Methods in System Design",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "38"
}
],
"keywords": [
"mean-payoff games",
"mean-payoff objectives",
"worst-case complexity",
"equivalent problem",
"energy games",
"pseudopolynomial algorithm",
"time complexity",
"weighted graph",
"algorithmic problems",
"fast algorithm",
"two-player game",
"pseudopolynomial time",
"randomized algorithm",
"safety games",
"fixpoint iteration",
"energy constraints",
"algorithm",
"such games",
"game",
"quantitative model",
"complexity",
"problem",
"Vorobyov",
"iteration",
"graph",
"constraints",
"solution",
"applications",
"Andersson",
"model",
"system",
"winners",
"procedure",
"results",
"time",
"objective",
"paper"
],
"name": "Faster algorithms for mean-payoff games",
"pagination": "97-118",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1027686195"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10703-010-0105-x"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10703-010-0105-x",
"https://app.dimensions.ai/details/publication/pub.1027686195"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-10T10:01",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_523.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s10703-010-0105-x"
}
]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/s10703-010-0105-x'
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/s10703-010-0105-x'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10703-010-0105-x'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10703-010-0105-x'
This table displays all metadata directly associated to this object as RDF triples.
174 TRIPLES
22 PREDICATES
72 URIs
54 LITERALS
6 BLANK NODES