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