LICS 2009 Program =================== Tues Aug 11 (Joint LICS/SAS) =================== 08:30-09:30 LICS/SAS Joint Invited Lecture [Chair: Andrew Pitts] Edmund M. Clarke, "Model Checking: My 27 Year Quest to Conquer the State-Explosion Problem" 09:30-10:30 Session 1 [Chair: Andrew Pitts] Jerome Leroux, "The General Vector Addition System Reachability Problem by Presburger Inductive Invariants" (LICS) David Schmidt, "Abstract Interpretation from a Topological Perspective" (SAS) ----------- 10:30-11:00 Coffee Break ----------- 11:00-12:30 Session 2 [Chair: Radhia Cousot] Liqian Chen, Antoine Mine, Ji Wang, Patrick Cousot, "Interval Polyhedra: An Abstract Domain to Infer Interval Linear Relationships" (SAS) Guillem Godoy, Ashish Tiwari, "Invariant Checking for Programs with Procedure Calls" (SAS) Andrei Voronkov, Iman Narasamdya, "Proving Inter-Program Properties" (SAS) ----------- 12:30-14:00 Lunch ----------- 14:00-15:30 Session 3 [Chair: Martin Abadi] 14:00-15:00 LICS Invited Tutorial Dan Ghica, "Applications of Game Semantics: From Program Analysis to Hardware Synthesis" 15:00-15:30 Vineet Kahlon, "Boundedness vs. Unboundedness of Lock Chains: Characterizing Decidability of CFL-Reachability for Threads Communicating via Locks" (LICS) ----------- 15:30-16:00 Coffee Break ----------- 16:00-17:30 Session 4 [Chair: Gopalan Nadathur] Joachim Parrow, Magnus Johansson, Bjorn Victor and Jesper Bengtson, "Psi-calculi: Mobile processes, Nominal Data and Logic" (LICS) Marcello Bonsangue, Jan Rutten and Alexandra Silva, "An Algebra for Kripke Polynomial Coalgebras" (LICS) Sumit Nain and Moshe Vardi, "Trace Semantics Is Fully Abstract" (LICS) ----------- 17:30-18:00 LICS Short Talks [Chair: Andre Scedrov] Lars Kuhtz, "Efficient Parallel Path Checking" Tomas Brazdil, Petr Jancar and Antonin Kucera, "Reachability and Safety Games on Vector Addition Systems with States" Francesco Ranzato and Francesco Tapparo, "A Time and Space Efficient Simulation Algorithm" ----------- 18:30- LICS Reception, UCLA Fowler Museum. ----------- =================== Wed 12 Aug =================== 08:30-10:30 Session 5 [Chair: Claude Kirchner] Derek Dreyer, Amal Ahmed and Lars Birkedal, "Logical Step-Indexed Logical Relations" Luis Dominguez, "Fully Abstract Logical Bisimilarity for a Polymorphic Object Calculus" Antonino Salibra and Alberto Carraro, "Reflexive Domains are not Complete for the Extensional Lambda Calculus" Frank Pfenning and Robert Simmons, "Substructural Operational Semantics as Ordered Logic Programming" ----------- 10:30-11:00 Coffee Break ----------- 11:00-12:30 Session 6 [Chair: Steven Lindell] Anuj Dawar, Martin Grohe, Bjarki Holm and Bastian Laubner, "Logics with Rank Operators" Emanuel Kieronski and Lidia Tendera, "On the Finite Satisfiability of the Two-Variable First-Order Logic with Equivalence Relations" Ulrich Schoepp and Martin Hofmann, "Pointer Programs and Undirected Reachability" ----------- 12:30-14:00 Lunch ----------- 14:00-15:30 Session 7 [Chair: Rajeev Alur] Oliver Friedmann, "An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it" Tony Tan, "Graph Reachability and Pebble Automata over Infinite Alphabets" Yang Cai, Ting Zhang and Haifeng Luo, "An Improved Lower Bound for the Complementation of Rabin Automata" ----------- 15:30-16:00 Coffee Break ----------- 16:00-17:30 Session 8 [Chair: Moshe Vardi] Naoki Kobayashi and Luke Ong, "A Type System Equivalent to Modal Mu-Calculus Model Checking of Higher-Order Recursion Schemes" Dan Ghica and Adam Bakewell, "Clipping: A Semantics-Directed Syntactic Approximation" Krishnendu Chatterjee, Laurent Doyen and Thomas Henzinger, "Expressiveness and Closure Properties for Quantitative Languages" ----------- 17:30-18:00 Short Talks [Chair: Luke Ong] Andrzej Murawski and Nikos Tzevelekos, "Full Abstraction for Reduced ML" Claudia Faggian and Mauro Piccolo, "Partial orders, event structures, and linear strategies" Maxime Gamboni and Antonio Ravara, "Responsive Choice in Mobile Processes" ----------- 18:00-18:30 Award presentations ----------- 18:30-19:30 LICS Business Meeting ----------- =================== Thurs 13 Aug =================== 08:30-10:30 Session 9 [Chair: Radha Jagadeesan] 08:30-09:30 Invited Lecture John Baez, "Computation and the Periodic Table" 09:30-10:30 Samuel Mimram, "The Structure of First-Order Causality" Christine Tasson and Michele Pagani, "The Inverse Taylor Expansion Problem in Linear Logic" ----------- 10:30-11:00 Coffee Break ----------- 11:00-12:30 Session 10 [Chair: Andrzej Murawski] Stefan Goeller, Richard Mayr and Anthony Widjaja To, "On the Computational Complexity of Verifying One-Counter Processes" Udi Boker and Orna Kupferman, "Co-ing Buchi made Tight and Useful" Mikolaj Bojanczyk, Howard Straubing and Igor Walukiewicz, "Wreath Products of Forest Algebras, with Applications to Logics for Unranked Trees" ----------- 12:30-14:00 Lunch ----------- 14:00-15:30 Session 11 [Chair: Eugenio Moggi] Joachim de Lataillade, "Dinatural Terms in System F" Thorsten Altenkirch and Peter Morris, "Indexed Containers" Luke Ong and Nikos Tzevelekos, "Functional Reachability" ----------- 15:30-16:00 Coffee Break ----------- 16:00-17:30 Session 12 [Chair: Eugenio Moggi] Mathieu Tracol and Michel de Rougemont, "Statistic Analysis for Probabilistic Processes" Taolue Chen, Tingting Han, Joost-Pieter Katoen and Alexandru Mereacre, "Quantitative Model Checking of Continuous-Time Markov Chains Against Timed Automata Specifications" Nathalie Bertrand, Blaise Genest and Hugo Gimbert, "Qualitative Determinacy and Decidability of Stochastic Games with Signals" ----------- 17:30-17:50 Short Talks [Chair: Andrew Pitts] Nataliia Bielova and Fabio Massacci, "Towards Practical Enforcement Theories" Marie Duzi, "Tenses and truth-conditions: a plea for if-then-else" ----------- 18:30-19:30 UCLA Athletics Hall of Fame, J.D. Morgan Center 19:30- Banquet in the Press Room next to the Hall of Fame ----------- =================== Fri 14 Aug =================== 08:30-10:30 Session 13 [Chair: Andrzej Murawski] 08:30-09:30 Invited Tutorial Ben Rossman, "Combining Ehrenfeucht-Fraisse Games" 09:30-10:30 Kristoffer Arnsfelt Hansen, Michal Koucky and Peter Bro Miltersen, "Winning Concurrent Reachability Games Requires Doubly-Exponential Patience" Alessandro Bianco, Fabio Mogavero and Aniello Murano, "Graded Computation Tree Logic" ----------- 10:30-11:00 Coffee Break ----------- 11:00-12:30 Session 14 [Chair: Radha Jagadeesan] Chuck Liang and Dale Miller, "A Unified Sequent Calculus for Focused Proofs" Carles Creus, Guillem Godoy, Francesc Massanes and Ashish Tiwari, "Non-linear Rewrite Closure and Weak Normalization" Michele Basaldella and Claudia Faggian, "Ludics with Repetitions (Exponentials, Interactive Types and Completeness)" ----------- 12:30-14:00 Lunch ----------- 14:00-15:30 Session 15 [Chair: Steven Lindell] Arnaud Durand, Miki Hermann and Gustav Nordh, "Trichotomy in the Complexity of Minimal Inference" Yijia Chen and Joerg Flum, "A Logic for PTIME and a Parameterized Halting Problem" Yevgeny Kazakov and Ian Pratt-Hartmann, "A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics" ----------- 15:30-16:00 Coffee Break ----------- 16:00-17:00 Session 16 [Chair: Andrew Pitts] Andrei Bulatov and Daniel Marx, "The Complexity of Global Cardinality Constraints Barnaby Martin and Florent Madelaine, "The Complexity of Positive First-Order Logic without Equality" ----------- [last updated 2009-07-08]