Logic, Complexity and Automation

Obergurgl University Center, Tyrol, Austria

September 5-7 2016

Workshop to be held as part of Computational Logic in the Alps 2016

Scope

The aim of Logic, Complexity and Automation (LC&A) is to bring together researchers from different areas of mathematics and computer science who all have an interest in computational complexity. We intend to focus on both theoretical and applied aspects of complexity, including, but not limited to:

• implicit computational complexity
• higher order complexity
• type systems
• program analysis
• tools for automating complexity analysis

The workshop will form the final official meeting of the FWF project Automated Complexity Analysis via Transformations. It will comprise a small number of invited talks, together with a collection of presentations given by members and external collaborators of the project. The workshop will be open for anyone to attend, although participants will need to register centrally via the CLA 2016 website.

LC&A will be one of four events held as part of Computational Logic in the Alps (CLA 2016), organised by the Computational Logic group of the University of Innsbruck. CLA will take place during the week of 5-9 September 2016, and is intended to foster friendly discussion and collaboration not just within, but between the individual workshops. As such, we encourage our participants to stay on for the remainder of the week and take part in the other events.

Invited speakers

• Patrick Baillot (ENS Lyon, France): On a type-based complexity analysis of subrecursive programs

• Arnold Beckmann (Swansea University, UK): Provably total NP search problems of bounded arithmetic

• Ulrich Berger (Swansea University, UK): Correctness vs. Efficiency

• Silvia Steila (Universität Bern, Switzerland): Reverse mathematical bounds for the termination theorem

• Florian Zuleger (TU Wien, Austria): Automated complexity analysis with the size-change abstraction

Project participants

Members from Innsbruck

• Stéphane Gimenez
• Alexander Maringele
• Georg Moser
• Thomas Powell
• Michael Schaper
• Maria Schett
• Manuel Schneckenreither

External collaborators

• Guillaume Bonfante (Université de Lorraine, France)
• Flavien Breuvart (Inria Sophia Antipolis, France)
• Jürgen Giesl (RWTH Aachen, Germany)
• Nao Hirokawa (JAIST, Japan)
• Johannes Waldmann (HTWK Leipzig, Germany)

Programme

A detailed and up-to-date programme for the entire event Computational Logic in the Alps is available here.

LC&A will be run in parallel with the 15th International Workshop on Termination (WST) over Monday 5th and Tuesday 6th. In particular, attendees of both workshops will have to opportunity to watch the Termination and Complexity Competition 2016 live on the Tuesday.

The schedule for LC&A is outlined below. Invited talks will last for 60 minutes, and contributed talks 30 minutes, including questions. A full list of titles and abstracts is available here.

During the second part of the week the 4th Austria-Japan Workshop on Rewriting (AJSW) and the 5th International Workshop on Confluence (IWC) will be held in parallel, over Thursday 8th and Friday 9th.

Location

LC&A will be held in the Obergurgl University Center, located high in the Austrian alps just over an hour's drive away from Innsbruck. The center can be accessed from Innsbruck via public transport, and in addition CLA will organise a special bus between Innsbruck and Obergurgl at the beginning and end of the conference. Innsbruck itself is easily reachable, either by train or plane. Rooms will be reserved for participants in the conference center.

Organisation

Enquiries should be directed to one of the following organisers:

• Georg Moser
• Thomas Powell