Martin Zimmermann

Martin Zimmermann

Auto-generated profile, based on publicly available information

Martin Zimmermann

Aalborg University, Aalborg, Denmark

Research Focus & Metrics

Academic Career Length

36Years (1991-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 July 2013 in Theoretical Computer Science
Verified
Journal Article
Closed access
MZMartin Zimmermann
Martin Zimmermann

26 June 2014 in Logical Methods in Computer Science
Verified
Journal Article
Open access
PDF file
NFNathanaël Fijalkow
Nathanaël Fijalkow
MZMartin Zimmermann
Martin Zimmermann
We consider two-player games played on finite graphs equipped with costs on edges and introduce two winning conditions, cost-parity and cost-Streett, which require bounds on the cost between requests and their responses. Both conditions generalize the corresponding classical omega-regular conditions and the corresponding finitary conditions. For parity games with costs we show that the first player has positional winning strategies and that determining the winner lies in NP and coNP. For Streett games with costs we show that the first player has finite-state winning strategies and that determining the winner is EXPTIME-complete. The second player might need infinite memory in both games. Both types of games with costs can be solved by solving linearly many instances of their classical variants.

1 April 2017 in Information and Computation
Verified
Journal Article
Closed access
PFPeter Faymonville
Peter Faymonville
MZMartin Zimmermann
Martin Zimmermann

31 October 2019 in Acta Informatica
Verified
Journal Article
Open access
PDF file
DNDaniel Neider
Daniel Neider
AWAlexander Weinert
Alexander Weinert
MZMartin Zimmermann
Martin Zimmermann
Recently, Dallal, Neider, and Tabuada studied a generalization of the classical game-theoretic model used in program synthesis, which additionally accounts for unmodeled intermittent disturbances. In this extended framework, one is interested in computing optimally resilient strategies, i.e., strategies that are resilient against as many disturbances as possible. Dallal, Neider, and Tabuada showed how to compute such strategies for safety specifications. In this work, we compute optimally resilient strategies for a much wider range of winning conditions and show that they do not require more memory than winning strategies in the classical model. Our algorithms only have a polynomial overhead in comparison to the ones computing winning strategies. In particular, for parity conditions, optimally resilient strategies are positional and can be computed in quasipolynomial time.

20 June 2015
Verified
Book Chapter
Closed access
PDF file
FKFelix Klein
Felix Klein
MZMartin Zimmermann
Martin Zimmermann

Verified
Conference Paper
Open access
PDF file
WFWladimir Fridman
Wladimir Fridman
CLChristof Löding
Christof Löding
MZMartin Zimmermann
Martin Zimmermann
We continue the investigation of delay games, infinite games in which one player may postpone her moves for some time to obtain a lookahead on her opponent's moves. We show that the problem of determining the winner of such a game is undecidable for deterministic context-free winning conditions. Furthermore, we show that the necessary lookahead to win a deterministic context-free delay game cannot be bounded by any elementary function. Both results hold already for restricted classes of deterministic context-free winning conditions.