Succinct progress measures for solving parity games
| Autor: | Marcin Jurdziński, Ranko Lazić |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
QA75
FOS: Computer and information sciences Computer Science - Logic in Computer Science Theoretical computer science Computer science Formal Languages and Automata Theory (cs.FL) Computer Science - Formal Languages and Automata Theory 0102 computer and information sciences 02 engineering and technology 01 natural sciences Logic in Computer Science (cs.LO) 010201 computation theory & mathematics Bounded function Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Data Structures and Algorithms (cs.DS) Parity (mathematics) |
| DOI: | 10.48550/arxiv.1702.05051 |
| Popis: | The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasi-polynomial 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|