# 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]

## LogicLounge in memoriam Helmut Veith

Will robots take away your job? In memory of Helmut Veith, this year’s Conference on Computer Aided Verification (CAV), which takes place in Toronto, will feature a LogicLounge on the effect of automation and artificial intelligence on our jobs.

## Marijana Lazić wins ZONTA mobility stipend

Marijana Lazić won the “ZONTA CLUB WIEN I – TU-Mobilitätsstipendium” for her research in the intersection of computer-aided verification and distributed computing theory.

## Questions answered by Leslie Lamport

Leslie Lamport is going to answer questions about a Mathematical View of Computer Systems in Informatikhörsaal on Tuesday at 6pm. Check the announcement at the VCLA website and do not forget to watch the lecture beforehand.

## FRIDA 2016 in Marocco

We had nice talks at the workshop on Formal Reasoning in Distributed Algorithms (FRIDA) this year. Look at the workshop web page.

## Laura Kovács joins FORSYTE as full professor

We welcome Laura Kovács, who joined the FORSYTE group as a full professor of computer science in April 2016.