onr:"swepub:oai:DiVA.org:uu-49004"
Search: onr:"swepub:oai:DiVA.org:uu-49004" > On Fixed-Parameter ...
- 1 of 1
- Previous record
- Next record
- To hitlist
On Fixed-Parameter Complexity of Infinite Games
-
- Björklund, Henrik (author)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,COMPUTING SCIENCE
-
- Sandberg, Sven (author)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
-
- Vorobyov, Sergei (author)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
- (creator_code:org_t)
- Uppsala: Department of Information Technology, Uppsala University, 2003
- English.
- Series: Technical report / Department of Information Technology, Uppsala University, 1404-3203 ; 2003-038
- Reports (other academic/artistic)
Abstract
Subject headings
Close
- We investigate and classify fixed parameter complexity of several infinite duration games, including Rabin, Streett, Muller, parity, mean payoff, and simple stochastic, using different natural parameterizations.Most known fixed parameter intractable games are PSPACE- or EXP-complete classically, AW[*] or XP-hard parametrically, and are all finite duration games. In contrast, the games we consider are infinite duration, solvable in positional or finite memory strategies, and belong to "lower" complexity classes, like NP and/or coNP. However, the best known algorithms they possess are of complexity nf(k), i.e., XP is the only upper bound, with no known parametric lower bounds.We demonstrate that under different parameterizations these games may have different or equivalent FPT-statuses, and present several tractable and intractable cases.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Publication and Content Type
- vet (subject category)
- rap (subject category)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Björklund, Henri ...
- Sandberg, Sven
- Vorobyov, Sergei
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- Parts in the series
- Technical report ...
- By the university
- Uppsala University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
