Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BY - Uznanie autorstwaA Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation
| cris.lastimport.scopus | 2024-02-12T20:38:26Z |
| dc.abstract.en | 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. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Słowenia |
| dc.conference.datefinish | 2021-01-28 |
| dc.conference.datestart | 2021-01-25 |
| dc.conference.place | Lublana |
| dc.conference.series | Annual Conference on Computer Science Logic |
| dc.conference.series | Annual Conference on Computer Science Logic |
| dc.conference.seriesshortcut | CSL |
| dc.conference.shortcut | CSL 2021 |
| dc.conference.weblink | https://csl2021.fmf.uni-lj.si/ |
| dc.contributor.author | Parys, Paweł |
| dc.contributor.author | Niwiński, Damian |
| dc.contributor.author | Arnold, André |
| dc.date.accessioned | 2024-01-24T18:06:19Z |
| dc.date.available | 2024-01-24T18:06:19Z |
| dc.date.copyright | 2021-01-13 |
| dc.date.issued | 2021 |
| dc.description.accesstime | AT_PUBLICATION |
| dc.description.finance | Publikacja bezkosztowa |
| dc.description.version | FINAL_PUBLISHED |
| dc.description.volume | 183 |
| dc.identifier.doi | 10.4230/LIPICS.CSL.2021.9 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/101814 |
| dc.identifier.weblink | https://doi.org/10.4230/LIPIcs.CSL.2021.9 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 9:1--9:23 |
| dc.rights | CC-BY |
| dc.sciencecloud | nosend |
| dc.subject.en | Mu-calculus |
| dc.subject.en | Parity games |
| dc.subject.en | Quasi-polynomial time |
| dc.subject.en | Black-box algorithm |
| dc.title | A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |