Faster algorithms for mean-payoff games View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-12-08

AUTHORS

L. Brim, J. Chaloupka, L. Doyen, R. Gentilini, J. F. Raskin

ABSTRACT

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. More... »

PAGES

97-118

References to SciGraph publications

  • 2000-03-24. Small Progress Measures for Solving Parity Games in STACS 2000
  • 2007-09. Potential theory for mean payoff games in JOURNAL OF MATHEMATICAL SCIENCES
  • 1993-06. Cyclical games with prohibitions in MATHEMATICAL PROGRAMMING
  • 2008-01-01. Infinite Runs in Weighted Timed Automata with Energy Constraints in FORMAL MODELING AND ANALYSIS OF TIMED SYSTEMS
  • 1992. The Temporal Logic of Reactive and Concurrent Systems, Specification in NONE
  • 1979-06. Positional strategies for mean payoff games in INTERNATIONAL JOURNAL OF GAME THEORY
  • 2003. Resource Interfaces in EMBEDDED SOFTWARE
  • 1993. On model-checking for fragments of μ-calculus in COMPUTER AIDED VERIFICATION
  • 1996. Pushdown processes: Games and model checking in COMPUTER AIDED VERIFICATION
  • 2009. From Parity and Payoff Games to Linear Programming in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10703-010-0105-x

    DOI

    http://dx.doi.org/10.1007/s10703-010-0105-x

    DIMENSIONS

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


    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/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

    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/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

    Subject Predicate Object
    1 sg:pub.10.1007/s10703-010-0105-x schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N1dab4af99fd3449a935a66a3d2880592
    4 schema:citation sg:pub.10.1007/3-540-46541-3_24
    5 sg:pub.10.1007/3-540-56922-7_32
    6 sg:pub.10.1007/3-540-61474-5_58
    7 sg:pub.10.1007/978-1-4612-0931-7
    8 sg:pub.10.1007/978-3-540-45212-6_9
    9 sg:pub.10.1007/978-3-540-85778-5_4
    10 sg:pub.10.1007/978-3-642-03816-7_57
    11 sg:pub.10.1007/bf01580616
    12 sg:pub.10.1007/bf01768705
    13 sg:pub.10.1007/s10958-007-0331-y
    14 schema:datePublished 2010-12-08
    15 schema:datePublishedReg 2010-12-08
    16 schema: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.
    17 schema:genre article
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N219d5db42640400ebd2117d1b7e719f6
    21 N301618e6db65426793b5ae535882ef26
    22 sg:journal.1052628
    23 schema:keywords Andersson
    24 Vorobyov
    25 algorithm
    26 algorithmic problems
    27 applications
    28 complexity
    29 constraints
    30 energy constraints
    31 energy games
    32 equivalent problem
    33 fast algorithm
    34 fixpoint iteration
    35 game
    36 graph
    37 iteration
    38 mean-payoff games
    39 mean-payoff objectives
    40 model
    41 objective
    42 paper
    43 problem
    44 procedure
    45 pseudopolynomial algorithm
    46 pseudopolynomial time
    47 quantitative model
    48 randomized algorithm
    49 results
    50 safety games
    51 solution
    52 such games
    53 system
    54 time
    55 time complexity
    56 two-player game
    57 weighted graph
    58 winners
    59 worst-case complexity
    60 schema:name Faster algorithms for mean-payoff games
    61 schema:pagination 97-118
    62 schema:productId N12de13c2df064877a49cb7b4eaf56551
    63 Nef695cb600e141d4b0444abadbf79989
    64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027686195
    65 https://doi.org/10.1007/s10703-010-0105-x
    66 schema:sdDatePublished 2022-05-10T10:01
    67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    68 schema:sdPublisher N2a2bcf1ab22741d194e1f7a5a529fa40
    69 schema:url https://doi.org/10.1007/s10703-010-0105-x
    70 sgo:license sg:explorer/license/
    71 sgo:sdDataset articles
    72 rdf:type schema:ScholarlyArticle
    73 N12de13c2df064877a49cb7b4eaf56551 schema:name dimensions_id
    74 schema:value pub.1027686195
    75 rdf:type schema:PropertyValue
    76 N1dab4af99fd3449a935a66a3d2880592 rdf:first sg:person.0645117057.83
    77 rdf:rest N77b02488d35344aaa8708841a674dc63
    78 N219d5db42640400ebd2117d1b7e719f6 schema:issueNumber 2
    79 rdf:type schema:PublicationIssue
    80 N2a2bcf1ab22741d194e1f7a5a529fa40 schema:name Springer Nature - SN SciGraph project
    81 rdf:type schema:Organization
    82 N301618e6db65426793b5ae535882ef26 schema:volumeNumber 38
    83 rdf:type schema:PublicationVolume
    84 N3553f2038c1b46bea3e65cabc44879c3 rdf:first sg:person.010207023561.22
    85 rdf:rest rdf:nil
    86 N779c82f1ef504c43aa9e63fb456cd7f1 rdf:first sg:person.010301575457.70
    87 rdf:rest Ndd48566836f54fd388b8e18d732bf3de
    88 N77b02488d35344aaa8708841a674dc63 rdf:first sg:person.013233527367.47
    89 rdf:rest N779c82f1ef504c43aa9e63fb456cd7f1
    90 Ndd48566836f54fd388b8e18d732bf3de rdf:first sg:person.016064406033.00
    91 rdf:rest N3553f2038c1b46bea3e65cabc44879c3
    92 Nef695cb600e141d4b0444abadbf79989 schema:name doi
    93 schema:value 10.1007/s10703-010-0105-x
    94 rdf:type schema:PropertyValue
    95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Information and Computing Sciences
    97 rdf:type schema:DefinedTerm
    98 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    99 schema:name Computation Theory and Mathematics
    100 rdf:type schema:DefinedTerm
    101 sg:journal.1052628 schema:issn 0925-9856
    102 1572-8102
    103 schema:name Formal Methods in System Design
    104 schema:publisher Springer Nature
    105 rdf:type schema:Periodical
    106 sg:person.010207023561.22 schema:affiliation grid-institutes:grid.4989.c
    107 schema:familyName Raskin
    108 schema:givenName J. F.
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010207023561.22
    110 rdf:type schema:Person
    111 sg:person.010301575457.70 schema:affiliation grid-institutes:grid.464035.0
    112 schema:familyName Doyen
    113 schema:givenName L.
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010301575457.70
    115 rdf:type schema:Person
    116 sg:person.013233527367.47 schema:affiliation grid-institutes:grid.10267.32
    117 schema:familyName Chaloupka
    118 schema:givenName J.
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233527367.47
    120 rdf:type schema:Person
    121 sg:person.016064406033.00 schema:affiliation grid-institutes:grid.9027.c
    122 schema:familyName Gentilini
    123 schema:givenName R.
    124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016064406033.00
    125 rdf:type schema:Person
    126 sg:person.0645117057.83 schema:affiliation grid-institutes:grid.10267.32
    127 schema:familyName Brim
    128 schema:givenName L.
    129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0645117057.83
    130 rdf:type schema:Person
    131 sg:pub.10.1007/3-540-46541-3_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044781598
    132 https://doi.org/10.1007/3-540-46541-3_24
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/3-540-56922-7_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006655742
    135 https://doi.org/10.1007/3-540-56922-7_32
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/3-540-61474-5_58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009044758
    138 https://doi.org/10.1007/3-540-61474-5_58
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/978-1-4612-0931-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044704735
    141 https://doi.org/10.1007/978-1-4612-0931-7
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/978-3-540-45212-6_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034896734
    144 https://doi.org/10.1007/978-3-540-45212-6_9
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/978-3-540-85778-5_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046321257
    147 https://doi.org/10.1007/978-3-540-85778-5_4
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/978-3-642-03816-7_57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039939811
    150 https://doi.org/10.1007/978-3-642-03816-7_57
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/bf01580616 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036721262
    153 https://doi.org/10.1007/bf01580616
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/bf01768705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021856463
    156 https://doi.org/10.1007/bf01768705
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/s10958-007-0331-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1002530809
    159 https://doi.org/10.1007/s10958-007-0331-y
    160 rdf:type schema:CreativeWork
    161 grid-institutes:grid.10267.32 schema:alternateName Faculty of Informatics, Masaryk University, Brno, Czech Republic
    162 schema:name Faculty of Informatics, Masaryk University, Brno, Czech Republic
    163 rdf:type schema:Organization
    164 grid-institutes:grid.464035.0 schema:alternateName LSV, ENS Cachan & CNRS, Cachan, France
    165 schema:name Computer Science Department, Université Libre de Bruxelles (U.L.B.), Brussels, Belgium
    166 LSV, ENS Cachan & CNRS, Cachan, France
    167 rdf:type schema:Organization
    168 grid-institutes:grid.4989.c schema:alternateName Computer Science Department, Université Libre de Bruxelles (U.L.B.), Brussels, Belgium
    169 schema:name Computer Science Department, Université Libre de Bruxelles (U.L.B.), Brussels, Belgium
    170 rdf:type schema:Organization
    171 grid-institutes:grid.9027.c schema:alternateName Department of Mathematics and Informatics, University of Perugia, Perugia, Italy
    172 schema:name Computer Science Department, Université Libre de Bruxelles (U.L.B.), Brussels, Belgium
    173 Department of Mathematics and Informatics, University of Perugia, Perugia, Italy
    174 rdf:type schema:Organization
     




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


    ...