Priority promotion with Parysian flair

Article

Benerecetti, M., Dell'Erba, D., Mogavero, F., Schewe, S. and Wojtczak, D. 2025. Priority promotion with Parysian flair. Journal of Computer and System Sciences. 147. https://doi.org/10.1016/j.jcss.2024.103580
TypeArticle
TitlePriority promotion with Parysian flair
AuthorsBenerecetti, M., Dell'Erba, D., Mogavero, F., Schewe, S. and Wojtczak, D.
Abstract

We develop an algorithm that combines the advantages of Priority Promotion, that is one of the leading approaches to solving large parity games in practice, with the quasi-polynomial time guarantees offered by Parys' algorithm. Hybridising these algorithms sounds both natural and difficult, as they both generalise the classic recursive algorithm in different ways that appear to be irreconcilable: while the promotion transcends the call structure, the guarantees change on each level. We show that an interface that respects both is not only effective, but also efficient.

Sustainable Development Goals9 Industry, innovation and infrastructure
Middlesex University ThemeCreativity, Culture & Enterprise
PublisherElsevier
JournalJournal of Computer and System Sciences
ISSN0022-0000
Electronic1090-2724
Publication dates
Online28 Aug 2024
PrintFeb 2025
Publication process dates
Submitted03 Apr 2023
Accepted07 Aug 2024
Deposited13 Mar 2026
Output statusPublished
Publisher's version
License
File Access Level
Open
Copyright Statement

© 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).

Digital Object Identifier (DOI)https://doi.org/10.1016/j.jcss.2024.103580
Permalink -

https://repository.mdx.ac.uk/item/367x6x

Log in to edit

Download files

Publisher's version
1-s2.0-S0022000024000758-main.pdf
License: CC BY 4.0
File access level: Open

  • 11
    total views
  • 6
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

DFAMiner: an efficient tool for learning minimal separating DFAs from labelled samples
Dell’Erba, D., Li, Y., Schewe, S. and Turrini, A. 2026. DFAMiner: an efficient tool for learning minimal separating DFAs from labelled samples. Science of Computer Programming. https://doi.org/10.1016/j.scico.2026.103506
DFAMiner: mining minimal separating DFAs from labelled samples
Dell’Erba, D., Li, Y. and Schewe, S. 2024. DFAMiner: mining minimal separating DFAs from labelled samples. Platzer, A., Rozier, K.Y., Pradella, M. and Rossi, M. (ed.) 26th International Symposium on Formal Methods. Milan, Italy 09 - 13 Sep 2024 Cham Springer. pp. 48-66 https://doi.org/10.1007/978-3-031-71177-0_4
Solving mean-payoff games via quasi dominions
Benerecetti, M., Dell'Erba, D. and Mogavero, F. 2024. Solving mean-payoff games via quasi dominions. Information and Computation. 297. https://doi.org/10.1016/j.ic.2024.105151
Smaller progress measures and separating automata for parity games
Dell'Erba, D. and Schewe, S. 2022. Smaller progress measures and separating automata for parity games. Frontiers in Computer Science. 4. https://doi.org/10.3389/fcomp.2022.936903