photo

Dietmar Berwanger

École Polytechnique Fédérale de Lausanne | EPFL
Models and Theory of Computation | MTC
EPFL - Station 14, 1015 Lausanne, Suisse

Phone: (+41) 21 693 12 21 • Fax: (+41) 21 693 75 40
Email:dietmar.berwanger.at.epfl.dot.ch

Research

I work as a postdoc in the Models and Theory of Computation group of Tom Henzinger. My research is on logical and algorithmical foundations of interactive systems, with emphasis on:

Publications

[1] D. Berwanger, Admissibility in infinite games, Proceedings of STACS 2007 -- Symposium on Theoretical Aspects of Computer Science, Springer-Verlag. Forthcoming.
List, Abstract 

@InProceedings{Berwanger07,
  AUTHOR = {Dietmar Berwanger},
  TITLE = {Admissibility in infinite games},
  BOOKTITLE = {STACS 2007 -- Symposium on Theoretical Aspects of Computer Science, Proceedings},
  PUBLISHER = {Springer-Verlag},
  SERIES = {LNCS},
  YEAR = {2007},
  NOTE = {Forthcoming}
}

[2] D. Berwanger, E. Grädel, and G. Lenzi, The variable hierarchy of the mu-calculus is strict, Theory of Computing Systems, Selected Papers from STACS 2005, Springer-Verlag. Forthcoming.
List, Abstract 

@Misc{BerwangerGraLen06,
  AUTHOR = {Dietmar Berwanger and Erich Gr{\"a}del and Giacomo Lenzi},
  TITLE = {The variable hierarchy of the $\mu$-calculus is strict},
  note = {To appear in Theory of Computing Systems},
  URL = {http://mtc.epfl.ch/~dwb/pub/hierarchy.pdf}
}

[3] D. Berwanger and D. Janin, Automata on directed graphs: vertex versus edge marking, in Proceedings of ICGT 2006 -- vol. 4178 of LNCS, pp. 46--60,Springer-Verlag, 2006.
List, Abstract 

@InProceedings{BerwangerJan06,
  AUTHOR = {Dietmar Berwanger and David Janin},
  TITLE = {Automata on Directed Graphs: Vertex versus Edge Marking},
  booktitle = {Proceedings of ICGT 2006 -- International Conference on Graph Transformation},
  URL = {http://mtc.epfl.ch/~dwb/pub/acc.pdf},
  PUBLISHER = {Springer-Verlag},
  SERIES = {LNCS},
  VOLUME = {4179},
  PAGES = {46 -- 60},
}

[4] D. Berwanger, A. Dawar, P. Hunter, and S. Kreutzer, DAG-width and parity games. in Proceedings of STACS 2006, vol. 3884 of LNCS, pp. 524--436, Springer-Verlag, 2006.
List, Abstract 

@INPROCEEDINGS{BDHK06,
  AUTHOR = {Dietmar Berwanger and Anuj Dawar and Paul Hunter and
Stephan Kreutzer},
  TITLE = {DAG-width and parity games},
  BOOKTITLE = {STACS 2006, Proceedings of the 23rd Symposium on
                 Theoretical Aspects of Computer Science},
  PUBLISHER = {Springer-Verlag},
  SERIES = {LNCS},
  VOLUME = {3884},
  YEAR = {2006},
  PAGES = {524--436},
  URL = {http://mtc.epfl.ch/~dwb/pub/dagwidth.pdf},
  TASK = {7}
}
`

[5] D. Berwanger and E. Grädel, Entanglement - A measure for the complexity of directed graphs with applications to logic and games., in Proceedings of LPAR 2004, Montevideo, Uruguay, vol. 3452 of LNCS, pp. 209-223, Springer-Verlag, 2005.
List, Abstract

@INPROCEEDINGS{BerwangerGraLPAR04,
  AUTHOR = {Dietmar Berwanger and Erich Gr{\"a}del},
  TITLE = {Entanglement - {A} Measure for the Complexity of
                 Directed Graphs with Applications to Logic and Games.},
  PAGES = {209--223},
  BOOKTITLE = {Proceedings of LPAR 2004, Montevideo, Uruguay},
  PUBLISHER = {Springer-Verlag},
  SERIES = {LNCS},
  VOLUME = {3452},
  YEAR = {2005},
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/dwb/BG_lpar04.pdf},
  TASK = {2}
}

[6] D. Berwanger and G. Lenzi, The variable hierarchy of the mu-calculus is strict, in STACS 2005, Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science, vol. 3404 of LNCS, pp. 97-109, Springer-Verlag, 2005.
List, Abstract

@INPROCEEDINGS{BerwangerLen05,
  AUTHOR = {Dietmar Berwanger and Giacomo Lenzi},
  TITLE = {The variable hierarchy of the $\mu$-calculus is
                 strict},
  BOOKTITLE = {STACS 2005, Proceedings of the 22nd Symposium on
                 Theoretical Aspects of Computer Science},
  PUBLISHER = {Springer-Verlag},
  SERIES = {LNCS},
  VOLUME = {3404},
  YEAR = {2005},
  PAGES = {97--109},
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/dwb/hierarchy.ps},
  TASK = {7}
}

[7] D. Berwanger, Games and logical expressiveness,. PhD thesis, RWTH Aachen, 2005.
List, Abstract

@PHDTHESIS{BerwangerThesis,
  AUTHOR = {Dietmar Berwanger},
  TITLE = {Games and Logical Expressiveness},
  SCHOOL = {RWTH Aachen},
  YEAR = {2005},
  TASK = {2,7},
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/dwb/express.ps}
}

[8] D. Berwanger and E. Grädel, Fixed-point logics and solitaire games, Theory of Computing Systems, vol. 37, pp. 675-694, 2004.
List, Abstract

@ARTICLE{BerwangerGra04,
  AUTHOR = {Dietmar Berwanger and Erich Gr{\"a}del},
  TITLE = {Fixed-Point Logics and Solitaire Games},
  JOURNAL = {Theory of Computing Systems},
  PUBLISHER = {Springer-Verlag},
  YEAR = {2004},
  VOLUME = {37},
  PAGES = {675--694},
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/graedel/BeGr_tocs.pdf},
  TASK = {2,7}
}

[9] D. Berwanger, Game logic is strong enough for parity games, Studia Logica, vol. 75, no. 2, pp. 205-219, 2003. Special issue on Game Logic and Game Algebra edited by M. Pauly and R. Parikh.
List, Abstract

@ARTICLE{Ber03,
  AUTHOR = {Dietmar Berwanger},
  TITLE = {Game Logic is Strong Enough for Parity Games},
  JOURNAL = {Studia Logica},
  PUBLISHER = {Kluwer},
  YEAR = 2003,
  VOLUME = 75,
  NUMBER = 2,
  PAGES = {205--219},
  NOTE = {Special issue on Game Logic and Game Algebra edited by M. Pauly and R. Parikh},
  URL = {http://journals.kluweronline.com/article.asp?PIPS=5253758}
}

[10] D. Berwanger, E. Grädel, and S. Kreutzer, Once upon a time in the west. Determinacy, complexity and definability of path games, in Proceedings of the 10th International Conference on Logic for Programming and Automated Reasoning, vol. 2850 of LNCS, pp. 226-240, Springer-Verlag, 2003.
List, Abstract

@INPROCEEDINGS{BGK03,
  AUTHOR = {Dietmar Berwanger and Erich Gr{\"a}del and Sthephan
                 Kreutzer},
  TITLE = {Once Upon a Time in the West. {D}eterminacy,
                 Complexity and Definability of Path Games},
  BOOKTITLE = {Proceedings of the 10th International Conference on
                 Logic for Programming and Automated Reasoning},
  YEAR = {2003},
  SERIES = {LNCS},
  VOLUME = {2850},
  PAGES = {226--240},
  PUBLISHER = {Springer-Verlag},
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/graedel/lpar03.ps},
  TASK = {7}
}

[11] D. Berwanger and A. Blumensath, Automata for guarded fixed point logics, in Automata, Logics, and Infinite Games (E. Grädel, W. Thomas, and T. Wilke, eds.), no. 2500 in LNCS, ch. 19, pp. 343-355, Springer Verlag, 2002.
List

@INCOLLECTION{BerwangerBl02,
  AUTHOR = {Dietmar~Berwanger and Achim~Blumensath},
  TITLE = {Automata for Guarded Fixed Point Logics},
  BOOKTITLE = {Automata, Logics, and Infinite Games},
  PAGES = {343-355},
  PUBLISHER = {Springer Verlag},
  YEAR = 2002,
  EDITOR = {E.~Gr\"adel and W.~Thomas and T.~Wilke},
  NUMBER = 2500,
  SERIES = {LNCS},
  CHAPTER = 19,
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/dwb/guarded.ps}
}

[12] D. Berwanger and E. Grädel, Fixed point formulae and solitaire games, in Proceedings of the 2nd International Workshop on Complexity in Automated Deduction, CiAD 2002, 2002.
List, Abstract

@INPROCEEDINGS{BerwangerGra02,
  AUTHOR = {Dietmar~Berwanger and Erich~Gr{\"a}del},
  TITLE = {Fixed point formulae and solitaire games},
  BOOKTITLE = {Proceedings of the 2nd International Workshop on
                 Complexity in Automated Deduction, CiAD 2002},
  YEAR = {2002},
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/dwb/ciad02.ps},
  TASK = {7}
}

[13] D. Berwanger, E. Grädel, and G. Lenzi, On the variable hierarchy of the modal mu-calculus, in Computer Science Logic, CSL 2002 (J. Bradfield, ed.), vol. 2471 of LNCS, pp. 352-366, Springer-Verlag, 2002.
List, Abstract

@INPROCEEDINGS{BerwangerGraLen02,
  AUTHOR = {Dietmar~Berwanger and Erich~Gr{\"a}del and
                 Giacomo~Lenzi},
  TITLE = {On the variable hierarchy of the modal mu-calculus},
  BOOKTITLE = {Computer Science Logic, CSL 2002},
  EDITOR = {Julian Bradfield},
  YEAR = {2002},
  SERIES = {LNCS},
  VOLUME = {2471},
  PAGES = {352--366},
  PUBLISHER = {Springer-Verlag},
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/dwb/csl02.ps}
}

[14] D. Berwanger and A. Blumensath, The monadic theory of tree-like structures, in Automata, Logics, and Infinite Games (E. Grädel, W. Thomas, and T. Wilke, eds.), no. 2500 in LNCS, ch. 16, pp. 285-301, Springer Verlag, 2002.
List

@INCOLLECTION{BlumensathBe02,
  AUTHOR = {Dietmar~Berwanger and Achim~Blumensath},
  TITLE = {The Monadic Theory of Tree-like Structures},
  BOOKTITLE = {Automata, Logics, and Infinite Games},
  PAGES = {285-301},
  PUBLISHER = {Springer Verlag},
  YEAR = 2002,
  EDITOR = {E.~Gr\"adel and W.~Thomas and T.~Wilke},
  NUMBER = 2500,
  SERIES = {LNCS},
  CHAPTER = 16,
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/dwb/muchnik.ps}
}

[15] D. Berwanger and E. Grädel, Games and model checking for guarded logics, in Proceedings of the 8th International Conference on Logic for Programming and Automated Reasoning, LPAR 2001, Havana (R. Nieuwenhuis and A. Voronkov, eds.), vol. 2250 of LNCS, Springer-Verlag, 2001.
List, Abstract

@INPROCEEDINGS{BeGr01,
  AUTHOR = {D. Berwanger and E. Gr{\"a}del},
  TITLE = {Games and Model Checking for Guarded Logics},
  BOOKTITLE = {Proceedings of the 8th International Conference on
                 Logic for Programming and Automated Reasoning, {LPAR}
                 2001, Havana},
  EDITOR = {R. Nieuwenhuis and A. Voronkov},
  YEAR = {2001},
  SERIES = {LNCS},
  VOLUME = {2250},
  PUBLISHER = {Springer-Verlag},
  URL = {http://www-mgi.informatik.rwth-aachen.de/Publications/pub/graedel/lpar.ps}
}

Work in progress

Web

I maintain the website of the GAMES Research Training Network and the collection of Open Problems in Finite Model Theory.

Dietmar Berwanger • November, 2006