2026-08-01T07:26:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13443 2024-03-06T10:52:05Z ddc:004 open_access

A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation Arnold, André Niwiński, Damian Parys, Paweł Mu-calculus Parity games Quasi-polynomial time Black-box algorithm We consider nested fixed-point expressions like μ z. ν y. μ x. f(x,y,z) evaluated over a finite lattice, and ask how many queries to a function f are needed to find the value. The previous upper bounds for a monotone function f of arity d over the lattice {0,1}ⁿ were of the order n^{𝒪(d)}, whereas a lower bound of Ω(n²/(lg n)) is known in case when at least one alternation between the least (μ) and the greatest (ν) fixed point occurs in the expression. Following a recent development for parity games, we show here that a quasi-polynomial number of queries is sufficient, namely n^{lg(d/lg n)+𝒪(1)}. The algorithm is an abstract version of several algorithms proposed recently by a number of authors, which involve (implicitly or explicitly) the structure of a universal tree. We then show a quasi-polynomial lower bound for the number of queries used by the algorithms in consideration. Schloss Dagstuhl – Leibniz-Zentrum für Informatik André Arnold and Damian Niwiński and Paweł Parys 2021 Is Part Of LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2021.9 urn:nbn:de:0030-drops-134430 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.9 eng https://creativecommons.org/licenses/by/3.0/legalcode