One-Clock Priced Timed Games with Negative Weights
Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modelling the cost of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the cost to reach a ta...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2022-08-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/6764/pdf |
| _version_ | 1797268502391816192 |
|---|---|
| author | Thomas Brihaye Gilles Geeraerts Axel Haddad Engel Lefaucheux Benjamin Monmege |
| author_facet | Thomas Brihaye Gilles Geeraerts Axel Haddad Engel Lefaucheux Benjamin Monmege |
| author_sort | Thomas Brihaye |
| collection | DOAJ |
| description | Priced timed games are two-player zero-sum games played on priced timed
automata (whose locations and transitions are labeled by weights modelling the
cost of spending time in a state and executing an action, respectively). The
goals of the players are to minimise and maximise the cost to reach a target
location, respectively. We consider priced timed games with one clock and
arbitrary integer weights and show that, for an important subclass of them (the
so-called simple priced timed games), one can compute, in pseudo-polynomial
time, the optimal values that the players can achieve, with their associated
optimal strategies. As side results, we also show that one-clock priced timed
games are determined and that we can use our result on simple priced timed
games to solve the more general class of so-called negative-reset-acyclic
priced timed games (with arbitrary integer weights and one clock). The
decidability status of the full class of priced timed games with one-clock and
arbitrary integer weights still remains open. |
| first_indexed | 2024-04-25T01:33:30Z |
| format | Article |
| id | doaj.art-855a3ad47a244767baac92a13811c604 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:33:30Z |
| publishDate | 2022-08-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-855a3ad47a244767baac92a13811c6042024-03-08T10:39:30ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742022-08-01Volume 18, Issue 310.46298/lmcs-18(3:17)20226764One-Clock Priced Timed Games with Negative WeightsThomas BrihayeGilles GeeraertsAxel HaddadEngel LefaucheuxBenjamin MonmegePriced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modelling the cost of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary integer weights and show that, for an important subclass of them (the so-called simple priced timed games), one can compute, in pseudo-polynomial time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called negative-reset-acyclic priced timed games (with arbitrary integer weights and one clock). The decidability status of the full class of priced timed games with one-clock and arbitrary integer weights still remains open.https://lmcs.episciences.org/6764/pdfcomputer science - computer science and game theorycomputer science - logic in computer science |
| spellingShingle | Thomas Brihaye Gilles Geeraerts Axel Haddad Engel Lefaucheux Benjamin Monmege One-Clock Priced Timed Games with Negative Weights Logical Methods in Computer Science computer science - computer science and game theory computer science - logic in computer science |
| title | One-Clock Priced Timed Games with Negative Weights |
| title_full | One-Clock Priced Timed Games with Negative Weights |
| title_fullStr | One-Clock Priced Timed Games with Negative Weights |
| title_full_unstemmed | One-Clock Priced Timed Games with Negative Weights |
| title_short | One-Clock Priced Timed Games with Negative Weights |
| title_sort | one clock priced timed games with negative weights |
| topic | computer science - computer science and game theory computer science - logic in computer science |
| url | https://lmcs.episciences.org/6764/pdf |
| work_keys_str_mv | AT thomasbrihaye oneclockpricedtimedgameswithnegativeweights AT gillesgeeraerts oneclockpricedtimedgameswithnegativeweights AT axelhaddad oneclockpricedtimedgameswithnegativeweights AT engellefaucheux oneclockpricedtimedgameswithnegativeweights AT benjaminmonmege oneclockpricedtimedgameswithnegativeweights |