The Library
Succinct progress measures for solving parity games
Tools
Tools
Tools
Jurdzinski, Marcin and Lazic, Ranko (2017) Succinct progress measures for solving parity games. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, 20-23 Jun 2017. Published in: Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) pp. 1-9. ISBN 9781509030187. doi:10.1109/LICS.2017.8005092
|
PDF
WRAP-succinct-progress-measures-parity-games-Lazic-2017.pdf - Accepted Version - Requires a PDF viewer. Download (654Kb) | Preview |
Official URL: https://doi.org/10.1109/LICS.2017.8005092
Abstract
The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasipolynomial time, where previously the best algorithms were mildly subexponential. We devise an alternative quasi-polynomial time algorithm based on progress measures, which allows us to reduce the space required from quasi-polynomial to nearly linear. Our key technical tools are a novel concept of ordered tree coding, and a succinct tree coding result that we prove using bounded adaptive multi-counters, both of which are interesting in their own right.
| Item Type: | Conference Item (Paper) | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Computer science -- Mathematics, Directed graphs | ||||||||
| Series Name: | Annual Symposium on Logic in Computer Science | ||||||||
| Journal or Publication Title: | Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||||||
| Publisher: | ACM ; IEEE | ||||||||
| ISBN: | 9781509030187 | ||||||||
| Official Date: | 2017 | ||||||||
| Dates: |
|
||||||||
| Page Range: | pp. 1-9 | ||||||||
| Article Number: | 32 | ||||||||
| DOI: | 10.1109/LICS.2017.8005092 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 21 April 2017 | ||||||||
| Date of first compliant Open Access: | 24 April 2017 | ||||||||
| Conference Paper Type: | Paper | ||||||||
| Title of Event: | 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||||||
| Type of Event: | Conference | ||||||||
| Location of Event: | Reykjavik, Iceland | ||||||||
| Date(s) of Event: | 20-23 Jun 2017 | ||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
