Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
Link to record
Permanent link

Direct link
Sandberg, Sven
Publications (10 of 17) Show all publications
Abdulla, P., Ben Henda, N., Mayr, R. & Sandberg, S. (2006). Limiting Behavior of Markov Chains with Eager Attractors. In: Third International Conference on the Quantitative Evaluation of Systems (QEST) (pp. 253-262).
Open this publication in new window or tab >>Limiting Behavior of Markov Chains with Eager Attractors
2006 (English)In: Third International Conference on the Quantitative Evaluation of Systems (QEST), 2006, p. 253-262Conference paper, Published paper (Refereed)
National Category
Computer Engineering
Identifiers
urn:nbn:se:uu:diva-82148 (URN)
Available from: 2006-12-21 Created: 2006-12-21 Last updated: 2018-01-13
Sandberg, S. (2005). Homing and Synchronizing Sequences. In: Model-Based Testing of Reactive Systems (pp. 5-33). : Springer Verlag
Open this publication in new window or tab >>Homing and Synchronizing Sequences
2005 (English)In: Model-Based Testing of Reactive Systems, Springer Verlag , 2005, p. 5-33Chapter in book (Other scientific)
Place, publisher, year, edition, pages
Springer Verlag, 2005
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-19108 (URN)3-540-26278-4 (ISBN)
Available from: 2007-01-05 Created: 2007-01-05 Last updated: 2018-01-12
Björklund, H., Sandberg, S. & Vorobyov, S. (2004). A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games. : DIMACS
Open this publication in new window or tab >>A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games
2004 (English)Report (Other (popular scientific, debate etc.))
Place, publisher, year, edition, pages
DIMACS, 2004
Series
DIMACS Technical Reports Published in 2004 ; 5
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-72103 (URN)
Available from: 2005-05-30 Created: 2005-05-30 Last updated: 2018-01-14
Björklund, H., Sandberg, S. & Vorobyov, S. (2004). Memoryless Determinacy of Parity and Mean Payoff Games: A Simple Proof. Theoretical Computer Science, 310(1-3), 365-378
Open this publication in new window or tab >>Memoryless Determinacy of Parity and Mean Payoff Games: A Simple Proof
2004 (English)In: Theoretical Computer Science, Vol. 310, no 1-3, p. 365-378Article in journal (Other (popular scientific, debate etc.)) Published
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-72105 (URN)
Available from: 2005-05-30 Created: 2005-05-30 Last updated: 2018-01-14
Björklund, H., Sandberg, S. & Vorobyov, S. (2004). Randomized Subexponential Algorithms for Infinite Games. : Uppsala Universitet
Open this publication in new window or tab >>Randomized Subexponential Algorithms for Infinite Games
2004 (English)Report (Other (popular scientific, debate etc.))
Abstract [en]

The complexity of solving infinite games, including parity, mean payoff, and simple stochastic games, is an important open problem in verification, automata theory, and complexity theory. In this paper we develop an abstract setting for studying and solving such games, as well as related problems, based on function optimization over certain discrete structures. We introduce new classes of completely local-global (CLG) and recursively local-global (RLG) functions, and show that strategy evaluation functions for parity and simple stochastic games belong to these classes. We also establish a relation to the previously well-studied completely unimodal (CU) and local-global functions. A number of nice properties of CLG-functions are proved. In this setting, we survey several randomized optimization algorithms appropriate for CU-, CLG-, and RLG-functions. We show that the subexponential algorithms for linear programming by Kalai and Matousek, Sharir, and Welzl, can be adapted to optimizing the functions we study, with preserved subexponential expected running time. We examine the relations to two other abstract frameworks for subexponential optimization, the LP-type problems of Matousek, Sharir, Welzl, and the abstract optimization problems of Gärtner. The applicability of our abstract optimization approach to parity games builds upon a discrete strategy evaluation measure. We also consider local search type algorithms, and settle two nontrivial, but still exponential, upper bounds. As applications we address some complexity-theoretic issues including non-PLS-completeness of the problems studied.

Place, publisher, year, edition, pages
Uppsala Universitet, 2004
Series
Technical reports from the Department of Information Technology ; 2004-011
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-72104 (URN)
Available from: 2006-11-27 Created: 2006-11-27 Last updated: 2018-01-14
Björklund, H., Sandberg, S. & Vorobyov, S. (2003). A Discrete Subexponential Algorithm for Parity Games.
Open this publication in new window or tab >>A Discrete Subexponential Algorithm for Parity Games
2003 (English)Report (Other scientific)
Identifiers
urn:nbn:se:uu:diva-45450 (URN)
Note
Published in Proceedings of STACS 2003, LNCS 2607Available from: 2006-12-27 Created: 2006-12-27
Björklund, H., Sandberg, S. & Vorobyov, S. (2003). A Discrete Subexponential Algorithm for Parity Games. In: Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science, STACS'2003.
Open this publication in new window or tab >>A Discrete Subexponential Algorithm for Parity Games
2003 (English)In: Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science, STACS'2003, 2003Conference paper, Published paper (Refereed)
Identifiers
urn:nbn:se:uu:diva-10760 (URN)
Available from: 2007-04-23 Created: 2007-04-23
Björklund, H. & Sandberg, S. (2003). Algorithms for Combinatorial Optimization and Games Adapted from Linear Programming. : Uppsala: Department of Information Technology, Uppsala University
Open this publication in new window or tab >>Algorithms for Combinatorial Optimization and Games Adapted from Linear Programming
2003 (English)Report (Other scientific)
Place, publisher, year, edition, pages
Uppsala: Department of Information Technology, Uppsala University, 2003
Series
IT Technical Report 2003-015
Identifiers
urn:nbn:se:uu:diva-49008 (URN)
Available from: 2006-12-27 Created: 2006-12-27
Björklund, H. & Sandberg, S. (2003). Algorithms for Combinatorial Optimization and Games Adapted from Linear Programming. In: Proceedings of the Eighth European Summer School on Logic, Language, and Information (ESSLLI) Student Session (pp. 13-24).
Open this publication in new window or tab >>Algorithms for Combinatorial Optimization and Games Adapted from Linear Programming
2003 (English)In: Proceedings of the Eighth European Summer School on Logic, Language, and Information (ESSLLI) Student Session, 2003, p. 13-24Conference paper, Published paper (Refereed)
Identifiers
urn:nbn:se:uu:diva-48560 (URN)
Available from: 2006-12-27 Created: 2006-12-27
Björklund, H., Sandberg, S. & Vorobyov, S. (2003). An Improved Subexponential Algorithm for Parity Games. : Uppsala: Department of Information Technology, Uppsala University
Open this publication in new window or tab >>An Improved Subexponential Algorithm for Parity Games
2003 (English)Report (Other scientific)
Place, publisher, year, edition, pages
Uppsala: Department of Information Technology, Uppsala University, 2003
Series
IT Technical Report 2003-017
Identifiers
urn:nbn:se:uu:diva-49006 (URN)
Available from: 2006-12-27 Created: 2006-12-27
Organisations

Search in DiVA

Show all publications