Entrance hall of the ICMS

Logic and Algorithms

Jul 21, 2008 - Jul 25, 2008

Appleton Tower, University of Edinburgh

Organisers

Name Institution
Dawar, Anuj University of Cambridge
Etessami, Kousha University of Edinburgh
Vardi, Moshe Rice University

PDF files of some presentations are available within the Programme section of this page.

Scientific Advisory Committee
Andrei Bulatov (Simon Fraser University)
Javier Esparza (Technical University, Munich)
Erich Grädel (Aachen University)
Phokion Kolaitis (IBM Almaden Research Centre)
Andrei Krokhin (Durham University)
Orna Kupferman (Hebrew University)
Leonid Libkin (University of Edinburgh)
Luke Ong (University of Oxford)

The main objective of the workshop on Logic and Algorithms is to tie together a number of new strands of research that have emerged from activity at the Isaac Newton Institute and to bring the diverse communities together again to share the insights gained by recent research. The areas that will be dealt with are as follows:

  • Constraint Satisfaction
  • Database Theory
  • Computer-Aided Verification
  • Games

Many themes and techniques cut across the various areas: the aim of the proposed workshop is to survey ongoing progress in logic and algorithms, with an emphasis on cross-cutting themes and techniques, and to bring some unity and synergy to the field.

Additional support for this workshop is provided by the Isaac Newton Institute. The Laboratory for Foundations of Computer Science will contribute towards the Milner Lecture.

Participation is by invitation only: those interested in attending should contact Anuj Dawar (anuj.dawar@cl.cam.ac.uk). There will be a contribution to local costs (including accommodation and subsistence) from awards to ICMS and the Organisers. Please note that there will be NO registration fee payable by participants for this workshop.

Arrangements

Venue
The Workshop will be held in Lecture Theatre 1 of the Appleton Tower, University of Edinburgh. To view the Theatre and a list of the visual equipment available click here. Follow this link for a map showing the location of Appleton Tower.

Travel
Information about travel to the UK and Edinburgh is available here.

If you have requested accommodation (see below), travel information and directions to Pollock Halls can be found on the website for Edinburgh First, co-ordinators of the accommodation bookings, http://www.edinburghfirst.com/edinburghfirst/travel.asp . We recommend that you take a taxi to the Halls. It should cost around 6.00 GBP from the main railway station (Waverley Station) and between 16.00 and 21.00 GBP from Edinburgh airport. Alternatively there are frequent buses from the airport to Waverley Station, from where you can get a taxi to Pollock Halls. The second of these two maps of Pollock Halls shows the location of both Pollock Halls and Appleton Tower where the lectures will take place. It is approximately a 15 minute walk between the two sites.

Lothian buses charge £1.10 for a single, £2.50 for a day ticket. Please note that the exact fare is required and no change is given. There are several Lothian Buses from the centre of town to Pollock Halls: Service No. 30, 14, 33 or the X48 Park and Ride Bus. If you enter the Service No on the Lothian Buses webpage, you will be able to view the timetable for each service bus. Leave the bus at The Commonwealth Pool on Dalkeith Road. Pollock Halls is situated just behind The Commonwealth Pool.

Accommodation
ICMS has arranged en-suite rooms in university accommodation in Pollock Halls for participants who requested this.

Pollock Halls of Residence
18 Holyrood Park Road
Edinburgh, EH16 5AY
Reception Contact Numbers
+44 (0)131 667 1971 (Tel)
+44 (0)131 668 3217 (Fax)

On arrival at Pollock Halls, please go to the Reception Building on your left, where you will pick up your key and some further information. You can access your room after 14.00. If you arrive earlier you can leave your luggage at Reception. Pollock Halls has 24 hour reception.

Alternatively, those who wished to make their own arrangements may claim back the cost, with receipts, up to a maximum of 35.00 GBP per night for bed and breakfast. A list of Edinburgh accommodation of various sorts and prices can be found on the Accommodation Page on the ICMS web site. Section 4 is particularly relevant.

Registration
There will be a combined Registration and Welcome Buffet from 18.30 to 20.30 on Sun 20 July, in the St Trinnean's Room, St Leonard's Hall, Pollock Halls (see map of Pollock above). Food will be available throughout that period and you may register at any time between 18.30 and 20.30.

Those who cannot register on Sun evening may do so at the workshop venue before the talks start on Mon morning.

The 2008 Milner Lecture
This lecture will take place in Lecture Theatre 1 in Appleton Tower at 17.15 on Wednesday 23 July. For full details click here. Following the lecture there will be a Reception in the Atrium of the Informatics Forum which is the new building directly opposite the entrance to Appleton Tower.

Computer access
At Registration you will be issued with a username, password and further information which will enable you to access either the wireless network or a public PC nearby. Appleton Tower is within a wireless zone as are parts of Pollock Halls.

Meals and Refreshments
There will be a Registration buffet in the St Trinneans Room in St Leonards Hall, Pollock Halls, on Sunday evening and a Workshop dinner on Thursday evening in the Prestonfield Room, John McIntyre Centre, Pollock Halls. A light lunch Mon-Fri and morning and afternoon refreshments will be provided in the Absorb Café area of the concourse outside Lecture Theatre 1 at Appleton Tower.

Financial Matters
The workshop grant will cover the cost of bed and breakfast accommodation at Pollock Halls. (Those who have made their own accommodation arrangements may claim back, with receipts, up to a maximum of 35.00 GBP per night). The buffet supper on Sun, a light lunch Mon-Fri, and the workshop dinner on Thurs evening will be provided free of charge to participants.

The majority of participants are covering their own travel. However, if we have agreed to reimburse some of your travel costs, this will be stated the 'Financial Arrangements' section of the 'Final Information' email. All reimbursement occurs after the workshop. You will be given a claim form at Registration and asked for your bank details to enable payment directly into your account. Please note that receipts are required for all expenses claimed. It would be useful if you can bring bank details to the workshop.

Please note that, in a change to earlier information published on this page, participants will no longer be required to pay the registration fee for the workshop.


Programme

Invited tutorial talks will be given by:

Professor Rajeev Alur (University of Pennsylvania)
Dr Albert Atserias (UPC Barcelona)
Dr Martin Grohe (Humboldt University, Berlin)
Dr Phokion Kolaitis (IBM Almaden Research Centre)
Professor Andreas Podelski (University of Freiburg)
Professor Wolfgang Thomas (RWTH Aachen)

Programme

Monday 21 July
08.30 - 09.00 Registration
09.00 - 10.30 Rajeev Alur (University of Pennsylvania)
Marrying words and trees
10.30 - 11.00 Coffee/Tea
11.00 - 11.40 Mikolaj Bojanczyk (Warsaw University)
Tree languages defined by formulas with one quantifier alternation
11.40 - 12.20 Balder ten Cate (University of Amsterdam)
XPath, tree walking automata and transitive closure logic PDF of slides
12.20 - 14.00 Lunch
14.00 - 15.30 Andreas Podelski (University of Freiburg)
Constraints in verification
15.30 - 16.00 Coffee/Tea
16.00 - 16.40 Alexander Malkis (University of Freiburg)
Precise thread-modular verification PDF of slides
16.40 - 17.20 Achim Blumensath (Technische Universität Darmstadt)
The interpretation hierarchy for guarded second-order logic
17.20 - 18.00 Joel Ouaknine (University of Oxford)
On termination of linear programs and the Skolem problem

Tuesday 22 July
09.00 - 10.30 Albert Atserias (UPC, Barcelona)
Finite model theory for constraint satisfaction problems, and back
10.30 - 11.00 Coffee/Tea
11.00 - 11.40 Hubie Chen (Universitat Pompeu Fabra)
Quantifying Chandra-Merlin PDF of slides
11.40 - 12.20 Andrei Krokhin (Durham University)
Hard CSPs have hard gaps at location 1 PDF of slides
12.20 - 14.00 Lunch
14.00 - 14.40 Paul Gastin (École Normale Supérieure de Cachan)
Distributed timed automata with independently evolving clocks PDF of slides
14.40 - 15.20 Stefan Göller (University of Leipzig)
ICPDL with fixed points and nominals
15.20 - 16.00 Michael Luttenberger (Technical University of Munich)
Derivation tree analysis for accelerated fixed-point computation
16.00 - 16.30 Coffee/Tea
16.30 - 17.10 Pascal Tesson (University of Laval)
Towards a refinement of the complexity classification of CSPs
17.10 - 17.50 Martin Otto (Technische Universität Darmstadt)
Bisimulation invariance over classes of transitive frames PDF of slides

Wednesday 23 July
09.00 - 10.30 Wolfgang Thomas (RWTH, Aachen)
Facets of strategy synthesis in infinite games PDF of slides
10.30 - 11.00 Coffee/Tea
11.00 - 11.40 Thomas Wilke (Christian-Albrechts-Universität zu Kiel)
Complementation, disambiguation, and determinization of Büchi automata PDF of slides
11.40 - 12.20 Stefan Kiefer (Technische Universität München)
Approximative methods for monotone systems of min-max-polynomial equations PDF of slides
12.20 - 14.00 Lunch
Free afternoon
17.15 MILNER LECTURE in Lecture Theatre 1, Appleton Tower

Thursday 24 July
09.00 - 10.30 Phokion Kolaitis (IBM Almaden Research Centre)
Foundations and applications of schema mappings PDF of slides
10.30 - 11.00 Coffee/Tea
11.00 - 11.40 Benjamin Rossman (Massachusetts Institute of Technology)
The first-order variable hierarchy on finite ordered structures Powerpoint slides
11.40 - 12.20 Philipp Weis (University of Massachusetts Amherst)
Lower bounds for formula size PDF of slides
12.20 - 14.00 Lunch
14.00 - 14.40 Tony Kucera (Masaryk University)
On the satisfiability problem for probabilistic CTL
14.40 - 15.20 Marta Kwiatkowska (University of Oxford)
Game-based abstraction-refinement framework for probabilistic processes PDF of slides
15.20 - 16.00 Dominik Wojtczack (University of Edinburgh)
Automated analysis of probabilistic recursive models
16.00 - 16.30 Coffee/Tea
16.30 - 17.10 Wouter Gelade (Hasselt University)
XML schema languages and succinctness of regular expressions PDF of slides
17.10 - 17.50 Jacques Duparc (University of Lausanne)
On the non-Borel mu-calculus formulae
19.30
Workshop Dinner in The Prestonfield Room, John McIntyre Centre, Pollock Halls


Friday 25 July
09.00 - 10.30 Martin Grohe (Humboldt University of Berlin)
Algorithmic and finite model theory PDF of slides
10.30 - 11.00 Coffee/Tea
11.00 - 11.40 Stephan Kreutzer (University of Oxford)
Computing excluded minors PDF of slides
11.40 - 12.20 Yehuda Naveh (IBM, Haifa)
Advances in constraint satisfaction for stimuli generation for functional hardware verification
12.20 - 14.00 Lunch
14.00 - 14.40 Marcin Jurdzinski (University of Warwick)
A simple P-matrix linear complementarity problem for discounted games
14.40 - 15.20 Patrice Ossona de Mendez (CNRS, Paris)
Nowhere dense structures, theory and implications
15.20 - 16.00 Jaroslav Nesetril (Charles University, Prague)
Many facets of dualities (FO and CSP context)
16.00 Coffee/Tea and close of workshop

 

Presentations:

Presentation Details
Alur, Rajeev
Marrying words and trees
View Abstract Down
Atserias, Albert
Finite model theory for constraint satisfaction problems, and back
View Abstract Down
Blumensath, Achim
The interpretation hierarchy for guarded second-order logic
View Abstract Down
Bojanczyk, Mikolaj
Tree languages defined by formulas with one quantifier alternation
View Abstract Down
Chen, Hubie
Quantifying Chandra-Merlin
View Abstract Down
Duparc, Jacques
On the non-Borel mu-calculus formulae
View Abstract Down
Gastin, Paul
Distributed timed automata with independently evolving clocks
View Abstract Down
Gelade, Wouter
XML schema languages and succinctness of regular expressions
View Abstract Down
Göller, Stefan
ICPDL with fixed points and nominals
View Abstract Down
Grohe, Martin
Algorithmic and finite model theory
View Abstract Down
Hague, Matthew
Winning regions of pushdown parity games: a saturation method
View Abstract Down
Jurdzinski, Marcin
A simple P-matrix linear complementarity problem for discounted games
View Abstract Down
Kiefer, Stefan
Approximative methods for monotone systems of min-max-polynomial
View Abstract Down
Kolaitis, Phokion
Foundations and applications of schema mappings
View Abstract Down
Kreutzer, Stephan
Computing excluded minors
View Abstract Down
Krokhin, Andrei
Hard CSPs have hard gaps at location 1
View Abstract Down
Kucera, Tony
On the satisfiability problem for probabilistic CTL
View Abstract Down
Kwiatkowska, Marta
Game-based abstraction-refinement framework for probabilistic processes
View Abstract Down
Luttenberger, Michael
Derivation tree analysis for accelerated fixed-point computation
View Abstract Down
Malkis, Alexander
Precise thread-modular verification
View Abstract Down
Naveh, Yehuda
Advances in constraint satisfaction for stimuli generation for functional hardware verification
View Abstract Down
Nesetril, Jaroslav
Many facets of dualities (FO and CSP context)
View Abstract Down
Ossona de Mendez, Patrice
Nowhere dense structures, theory and implications
View Abstract Down
Otto, Martin
Bisimulation invariance over classes of transitive frames
View Abstract Down
Ouaknine, Joel
On termination of linear programs and the Skolem problem
View Abstract Down
Podelski, Andreas
Constraints in verification
View Abstract Down
Rossman, Benjamin
The first-order variable hierarchy on finite ordered structures
View Abstract Down
ten Cate, Balder
XPath, tree walking automata and transitive closure logic
View Abstract Down
Tesson, Pascal
Towards a refinement of the complexity classification of CSPs
View Abstract Down
Thomas, Wolfgang
Facets of strategy synthesis in infinite games
View Abstract Down
Weis, Philipp
Lower bounds for formula size
View Abstract Down
Wilke, Thomas
Complementation, disambiguation, and determinization of Büchi automata unified
View Abstract Down
Wojtczak, Dominik
Automated analysis of probabilistic recursive models
View Abstract Down

Participants

Name Institution
Alur, Rajeev University of Pennsylvania
Antonopoulos, Timos University of Cambridge
Arenas, Marcelo PUC, Chile
Atserias, Albert UPC, Barcelona
Barcelo, Pablo University of Chile
Berstel, Bruno ILOG, France
Blumensath, Achim Technische Universität Darmstadt
Bojanczyk, Mikolaj Warsaw University
Bradfield, Julian University of Edinburgh
Bulatov, Andrei Simon Fraser University
Carvalho, Catarina Durham University
Chen, Hubie Universitat Pompeu Fabra
Cheney, James University of Edinburgh (local participant - attending talks only)
Coja-Oghlan, Amin University of Edinburgh (local participant - attending talks only)
Dalmau, Victor Universitat Pompeu Fabra
Dawar, Anuj University of Cambridge
Duparc, Jacques University of Lausanne
Egri, Laszlo McGill University
Esparza, Javier Technische Universität München
Etessami, Kousha University of Edinburgh
Gastin, Paul École Normale Supérieure de Cachan
Geerts, Floris University of Edinburgh
Gelade, Wouter Hasselt University
Göller, Stefan University of Leipzig
Grohe, Martin Humboldt University of Berlin
Gutierrez, Julian University of Edinburgh (local participant - attending talks only)
Haddad, Axel École Normale Superieur de Cachan (attending talks only)
Hague, Matthew University of Oxford
He, Yuguo University of Cambridge
Hella, Lauri University of Tampere
Hernich, Andre University of Frankfurt
Holm, Bjarki University of Cambridge
Hunter, Paul University of Oxford
Immerman, Neil University of Massachussets Amherst
Jurdzinski, Marcin University of Warwick
Kalorkoti, Kyriakos University of Edinburgh (local participant - attending talks only)
Kiefer, Stefan Technische Universität München
Kolaitis, Phokion IBM Almaden Research Centre
Kreutzer, Stephan University of Oxford
Krokhin, Andrei Durham University
Kucera, Tony Masaryk University
Kwiatkowska, Marta University of Oxford
Larose, Benoit Concordia University
Leconte, Michel ILOG, France
Leconte, Michel ILOG, France
Libkin, Leonid University of Edinburgh
Liu, Jie Chinese Academy of Sciences (attending talks only)
Lohrey, Markus University of Leipzig
Luttenberger, Michael Technical University of Munich
Malkis, Alexander University of Freiburg
Martin, Barnaby Durham University
Mayr, Richard University of Edinburgh (local participant - attending talks only)
Naveh, Yehuda IBM, Haifa
Nesetril, Jaroslav Charles University, Prague
Ossona de Mendez, Patrice CNRS, Paris
Otto, Martin Technische Universität Darmstadt
Ouaknine, Joel University of Oxford
Parys, Pawel University of Warsaw
Piterman, Nir Imperial College London
Podelski, Andreas University of Freiburg
Pullum, Geoffrey University of Edinburgh (local participant - attending talks only)
Richerby, David University of Leeds
Rossman, Benjamin Massachusetts Institute of Technology
Santhanam, Rahul University of Edinburgh
Schweikardt, Nicole University of Frankfurt
Schwentick, Thomas Technische Universität Dortmund
Segoufin, Luc INRIA, France
Sirangelo, Cristina University of Edinburgh (local participant - attending talks only)
Stewart, Iain Durham University
Stirling, Colin University of Edinburgh
Szeider, Stefan Durham University
ten Cate, Balder University of Amsterdam
Tesson, Pascal University of Laval
Thomas, Wolfgang RWTH, Aachen
Ummels, Michael RWTH Aachen
Väänänen, Jouko University of Amsterdam
Valeriote, Matt McMaster University
Vardi, Moshe Rice University
Vollmer, Heribert Leibniz University Hannover
Weber, Volker Technische Universität Dortmund
Weinstein, Scott University of Pennsylvania
Weis, Philipp University of Massachusetts Amherst
Widjaja To, Anthony University of Edinburgh (local participant - attending talks only)
Wilke, Thomas Christian-Albrechts-Universität zu Kiel
Wojtczak, Dominik University of Edinburgh
Wong, Karianto RWTH, Aachen
Worrell, James University of Oxford
Zivny, Stanislav University of Oxford