Program of LICS

Sunday, July 11th

Sunday's program is also available with abstracts and side by side with other events.

08:45‑10:00 Opening. Finite Model Theory
Chair: Victor Vianu
Location: AT LT4
08:45 Opening
09:00 Vince Bárány, Georg Gottlob and Martin Otto
Querying the Guarded Fragment
09:30 Martin Otto
Highly Acyclic Groups, Hypergraph Covers and the Guarded Fragment
10:30‑12:30 Type Theory
Chair: Herman Geuvers
Location: AT LT4
10:30 Vincent Siles and Hugo Herbelin
Equality is typable in Semi-Full Pure Type Systems
11:00 Andrei Popescu, Elsa Gunter and Chris Osborn
Strong normalization of System F by HOAS on top of FOAS
11:30 James Laird
Game Semantics for a Polymorphic Programming Language
12:00 Hugo Herbelin
An intuitionistic logic that proves Markov's principle
14:00‑15:00 FLoC Plenary Talks: tribute to Amir and Robin
Chair: Moshe Vardi
Location: George Square Lecture Theatre
14:00 David Harel (Weizmann Institute of Science)
Amir Pnueli: A Gentle Giant, Lord of the Phi's and the Psi's.
14:30 Gordon Plotkin (University of Edinburgh)
Robin Milner, a Craftsman of Tools for the Mind.
15:30‑17:00 Logic and Automata
Chair: David Harel
Location: AT LT4
15:30 Mark Jenkins, Joel Ouaknine, Alexander Rabinovich and James Worrell
Alternating Timed Automata over Bounded Time
16:00 Thomas Colcombet and Christof Loeding
Regular cost functions over finite trees
16:30 Eryk Kopczynski and Anthony Widjaja To
Parikh Images of Grammars: Complexity and Applications
17:15‑18:15 Complexity of CSP
Chair: Nicole Schweikardt
Location: AT LT4
17:15 Manuel Bodirsky, Martin Hils and Barnaby Martin
On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
17:45 Marcin Kozik and Libor Barto
New conditions for Taylor varieties and CSP
Monday, July 12th

Monday's program is also available with abstracts and side by side with other events.

09:00‑10:00 Invited Lecture
Chair: Rajev Alur
Location: AT LT4
09:00 Martin Abadi (Microsoft Research and UCSC)
The Fine print of Security
10:30‑12:30 Semantics
Chair: Martin Abadi
Location: AT LT4
10:30 Joerg Endrullis, Dimitri Hendriks and Jan Willem Klop
Modular Construction of Fixed Point Combinators and Clocked Boehm Trees
11:00 Christopher Broadbent, Arnaud Carayol, C.-H. Luke Ong and Olivier Serre
Recursion Schemes and Logical Reflection
11:30 James Brotherston and Max Kanovich, Dominique Larchey-Wendling and Didier Galmiche.
Undecidability of Boolean BI, and of propositional separation logic and its neighbours
12:00 Paul-André Melliès
Segal condition meets computational effects
14:00‑15:00 Finite Model Theory
Chair: Stephan Kreutzer
Location: AT LT4
14:00 Dietrich Kuske, Jiamou Liu and Markus Lohrey
The Isomorphism Problem On Classes of Automatic Structures
14:30 Yuguo He
On the strictness of the first-order quantifier structure hierarchy over finite structures
15:30‑17:00 Finite Model Theory
Chair: Yijia Chen
Location: AT LT4
15:30 Martin Grohe
Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors
16:00 Stephan Kreutzer and Siamak Tazari
Lower Bounds for the Complexity of Monadic Second-Order Logic
16:30 Bastian Laubner
Capturing Polynomial Time on Interval Graphs
17:15‑18:15 Logics
Chair: Dan Ghica
Location: AT LT4
17:15 Patricia Johann, Alex Simpson and Janis Voigtländer
A Generic Operational Metatheory for Algebraic Effects
17:45 Noam Zeilberger
Polarity and the logic of delimited continuations
Tuesday, July 13th

Tuesday's program is also available with abstracts and side by side with other events.

09:00‑10:00 FLoC Plenary Talk: Georg Gottlob
Chair: Martin Grohe
Location: George Square Lecture Theatre
09:00 Georg Gottlob (University of Oxford)
Datalog+-: A Family of Logical Query Languages for New Applications.
10:30‑12:30 Logic and Automata
Chair: Georg Gottlob
Location: AT LT4
10:30 Mikołaj Bojańczyk and Sławomir Lasota
An extension of data automata that captures XPath
11:00 Thomas Place and Luc Segoufin
Deciding definability in FO2(<) on trees
11:30 Luis Barguñó, Carles Creus, Guillem Godoy, Florent Jacquemard and Camille Vacher
The Emptiness Problem for Tree Automata with Global Constraints
12:00 Nicole Schweikardt and Luc Segoufin
Addition-invariant FO and regularity
14:00‑15:00 FLoC Keynote Talk: J Strother Moore
Chair: Jean-Pierre Jouannaud
Location: George Square Lecture Theatre
14:00 J Strother Moore (University of Texas)
Theorem Proving for Verification: The Early Days.
15:30‑17:00 Logics
Chair: Amy Felty
Location: AT LT4
15:30 Alessio Guglielmi, Tom Gundersen and Lutz Strassburger
Breaking Paths in Atomic Flows for Classical Logic
16:00 Michele Basaldella and Kazushige Terui
Infinitary completeness in ludics
16:30 Arnon Avron, Ofer Arieli and Anna Zamansky
On Strong Maximality of Paraconsistent Finite-Valued Logics
17:15‑17:55 Short Papers Session
Chair: Stephane Lengrand
Location: AT LT4
17:15 Mohamed Nabih Menaa
On the Compositionality of Round Abstraction
17:25 Pierre-yves Strub and Qian Wang
Coq Modulo Theory - Short Paper
17:35 Stanislav Böhm, Stefan Göller and Petr Jancar
Bisimilarity of one-counter processes is PSPACE-complete
17:45 Jian-Qi Li
A Computability Path Ordering for Polymorphic Terms
Wednesday, July 14th

Wednesday's program is also available with abstracts and side by side with other events.

09:00‑10:00 Invited Lecture
Chair: Martin Escardo
Location: AT LT4
09:00 Catuscia Palamidessi (INRIA and LIX, Ecole Polytechnique)
Probabilistic Information Flow
10:30‑12:30 Process Calculi
Chair: Catuscia Palamidessi
Location: AT LT4
10:30 Magnus Johansson, Jesper Bengtson, Joachim Parrow and Björn Victor
Weak Equivalences in Psi-calculi
11:00 Massimo Bartoletti and Roberto Zunino
A calculus of contracting processes
11:30 Christian Eisentraut, Holger Hermanns and Lijun Zhang
On Probabilistic Automata In Continuous Time
12:00 Jean Goubault-Larrecq
Omega-QRB-Domains and the Probabilistic Powerdomain
14:00‑15:00 Invited Lecture
Chair: Eugenio Moggi
Location: AT LT4
14:00 Vincent Danos (The University of Edinburgh and CNRS)
Abstracting the ODE semantics of rule-based models: exact and automatic model reduction
15:30‑17:00 Concurrency
Chair: Vincent Danos
Location: AT LT4
15:30 Cosimo Laneve and Antonio Vitale
The Expressive Power of Synchronizations
16:00 Sam Staton and Glynn Winskel
On the expressivity of symmetry in event structures
16:30 Thomas Ehrhard
A finiteness structure on resource terms
17:15‑18:20 Coalgebras. Closing
Chair: Phil Scott
Location: AT LT4
17:15 Samson Abramsky
Coalgebras, Chu Spaces, and Representations of Physical Systems
17:45 Stefan Milius
A Sound and Complete Calculus for finite Stream Circuits
18:15 Closing