TU Wien Informatics

20 Years

Automata-Based Analysis of Recursive Programs with Thread-Creation

  • 2010-12-10
  • Research

We survey work on automata-based optimal analysis of programs with thread-creation and potentially recursive procedures.

Abstract

We survey work on automata-based optimal analysis of programs with thread-creation and potentially recursive procedures. Specifically, we introduce dynamic pushdown networks (DPNs) that extend pushdown processes by thread creation as a model for such programs, introduce their semantics, and summarize basic results on reachability analysis and its applications. Moving from a word-shaped to tree-shaped views of executions allows us to impose regular constraints on the communicated actions in symbolic backward analysis or even to describe the entire set of executions by regular means. This in turn enables us to do lock-join-sensitive reachability analysis as the set of action trees that have a lock-join-sensitive schedule turns out to be regular.

The talk is based on papers presented at CONCUR 2005, CAV 2009, and VMCAI 2011, and is a joint work with Ahmed Bouajjani, Tayssir Touili, Peter Lammich, Alexander Wenner, Thomas Gawlitza, and Helmut Seidl.

Biography

Markus Müller-Olm studied Computer Science and Mathematics at Christian-Albrechts-Universität in Kiel, Germany, from which he got his PhD in 1996 with a dissertation on modular compiler verification. Afterwards he has been a post-doctoral researcher at the universities of Passau, Dortmund, Trier, and Hagen. After a habilitation in 2003 at Dortmund University with a Habilitationsschrift on static analysis of sequential and parallel programs, he is now a professor at Westfälische-Wilhelms-Universität Münster, Germany, where he heads the research group on software construction and verification.

Note

Zu diesem Vortrag lädt der Arbeitsbereich für Programmiersprachen und Übersetzer am Institut für Computersprachen herzlich ein. Tee: 14:30 Uhr in der Bibliothek E185.1, Argentinierstr. 8, 4. Stock (Mitte).

Speakers

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.

Note: This is one of the thousands of items we imported from the old website. We’re in the process of reviewing each and every one, but if you notice something strange about this particular one, please let us know. — Thanks!