# Automatic Bound Computation

The undecidability of the Halting problem is a famous result that goes back to the beginnings of computer science. The result says that there is no general method for automatically proving the termination of programs. Note, that this statement does not contradict the fact that in practice it is very well possible to prove termination for important program classes automatically. For example, it was a huge success when the first automatic tool chain was able to automatically prove the termination of Windows Device Drivers. Because drivers run in kernel mode, non-terminating drivers could cause the whole system to hang. Despite this success, termination is not a satisfying answer to most programmers who not only want to know that their programs terminate but also when! In ongoing research we are developing tools and algorithms for automatically deriving complexity bounds. Consider the following programs:

 ```x = y = n; while (x > 0 && y > 0) if(random()) x--; else y--; ``` ```x = y = n; while (x > 0 && y > 0) if(random()) x--; else { y--; x = n; } ``` ```while (n > 0) t := A[n]; while (n > 0 && t = A[n]) n--; ``` ```i := 0; while (i < n) { j := i + 1; while (j < n) { if (random()) { ConsumeResource(); j--; n--; } j++; } i++; } ```

Our tool Loopus automatically establishes that in the first and third program the complexity of the loop is O(n) and O(n2) in the second program. Moreover our tool establishes that ConsumeResource() is only called O(n) times. If you find the above described research exciting, we can offer you a variety of topics for bachelor / master theses and projects for practical course work and student jobs.

It is beneficial, if you bring the following qualities:

• programming skills
• interest in scientific work
• basic knowledge in logic and set-theory
• willingness to study state-of-the-art publications

[Contact Florian Zuleger]

## Summer School on Logic, Artificial Intelligence and Verification

The doctoral college Logical Methods in Computer Science (LogiCS) and the Austrian Society for Rigorous Systems Engineering (RiSE) will host a summer school on Logic, Artificial Intelligence and Verification at TU Wien, Vienna, Austria from July 3 to July 5.

## Helmut Veith Stipend

The first recipient of the Helmut Veith Stipend for excellent female master’s students in computer science will be presented on March 14 at the following event: "More female students in computer science. Who cares?" Panel discussion with renowned scientists about diversity in STEM Studies March 14, 5:30pm, TU Wien The Helmut Veith Stipend is dedicated […]

## Congratulations, Dr. Mitra Tabaei Befrouei

Mitra Tabaei Befrouei successfully defended her doctoral thesis on "Effective Error Explanation Techniques for Concurrent Software" on December 6, 2016. The FORSYTE group congratulates the newly-minted Doctor!

## WAIT 2016 in Vienna

The third WAIT workshop on induction is held between 17-18 November at the TU Wien. Details are available on the workshop page.

## Two papers at POPL’17

Two papers co-authored by researchers from our group have been accepted for POPL’17: “Coming to Terms with Quantified Reasoning” by Simon Robillard, Andrei Voronkov, and Laura Kovacs; and “A Short Counterexample Property for Safety and Liveness Verification of Fault-tolerant Distributed Algorithms” by Igor Konnov, Marijana Lazic, Helmut Veith, and Josef Widder