Fearnley, John, Ibsen-Jensen, Rasmus 
ORCID: 0000-0003-4783-0389 and Savani, Rahul ORCID: 0000-0003-1262-7831
(2020)
One-Clock Priced Timed Games are PSPACE-hard
LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, abs/20.
pp. 397-409.
ISSN 1043-6871
|
Text
2001.04458v2.pdf - Author Accepted Manuscript Download (464kB) | Preview |
Abstract
The main result of this paper is that computing the value of a one-clock priced timed game (OCPTG) is PSPACE-hard. Along the way, we provide a family of OCPTGs that have an exponential number of event points. Both results hold even in very restricted classes of games such as DAGs with treewidth three. Finally, we provide a number of positive results, including polynomial-time algorithms for even more restricted classes of OCPTGs such as trees.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | cs.GT, cs.GT, cs.FL, cs.LO |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 28 Apr 2020 10:26 |
| Last Modified: | 07 Dec 2024 09:56 |
| DOI: | 10.1145/3373718.3394772 |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3084306 |
| Disclaimer: | The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate. |
Altmetric
Altmetric