LICS 2009 List of Accepted Papers

Jerome Leroux. The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
Arnaud Durand, Miki Hermann and Gustav Nordh. Trichotomy in the Complexity of Minimal Inference
Yijia Chen and Jörg Flum. A logic for PTIME and a parameterized halting problem
Nathalie Bertrand, Blaise Genest and Hugo Gimbert. Qualitative Determinacy and Decidability of Stochastic Games with Signals
Tony Tan. Graph Reachability and Pebble Automata over Infinite Alphabets
Antonino Salibra and Alberto Carraro. Reflexive domains are not complete for the extensional lambda calculus
Luke Ong and Nikos Tzevelekos. Functional Reachability
Dan Ghica and Adam Bakewell. Clipping: A Semantics-Directed Syntactic Approximation
Thorsten Altenkirch and Peter Morris. Indexed Containers
Ulrich Schoepp and Martin Hofmann. Pointer Programs and Undirected Reachability
Barnaby Martin and Florent Madelaine. The complexity of positive first-order logic without equality
Samuel Mimram. The Structure of First-Order Causality
Joachim de Lataillade. Dinatural terms in system F
Stefan Göller, Richard Mayr and Anthony Widjaja To. On the Computational Complexity of Verifying One-Counter Processes
Naoki Kobayashi and Luke Ong. A Type System Equivalent to Modal Mu-Calculus Model Checking of Higher-Order Recursion Schemes
Yevgeny Kazakov and Ian Pratt-Hartmann. A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
Oliver Friedmann. A Super-Polynomial Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it
Yang Cai, Ting Zhang and Haifeng Luo. An Improved Lower Bound for the Complementation of Rabin Automata
Vineet Kahlon. Boundedness vs. Unboundedness of Lock Chains: Characterizing Decidability of CFL-Reachability for Threads Communicating via Locks
Derek Dreyer, Amal Ahmed and Lars Birkedal. Logical Step-Indexed Logical Relations
Kristoffer Arnsfelt Hansen, Michal Koucky and Peter Bro Miltersen. Winning Concurrent Reachability Games Requires Doubly-Exponential Patience
Mikolaj Bojanczyk, Howard Straubing and Igor Walukiewicz. Wreath Products of Forest Algebras, with Applications to Logics for Unranked Trees
Mathieu Tracol and Michel de Rougemont. Statistic Analysis for Probabilistic Processes
Luís Dominguez. Fully Abstract Logical Bisimilarity for a Polymorphic Object Calculus
Michele Basaldella and Claudia Faggian. Ludics with repetitions (Exponentials, Interactive types and Completeness)
Alessandro Bianco, Fabio Mogavero and Aniello Murano. Graded Computation Tree Logic
Emanuel Kieronski and Lidia Tendera. On the Finite Satisfiability of the Two-Variable First-Order Logic with Equivalence Relations
Udi Boker and Orna Kupferman. Co-ing Büchi: Less Open, Much More Practical
Krishnendu Chatterjee, Laurent Doyen and Thomas Henzinger. Expressiveness and Closure Properties for Quantitative Languages
Christine Tasson and Michele Pagani. The Inverse Taylor Expansion Problem in Linear Logic
Andrei Bulatov and Daniel Marx. The complexity of global cardinality constraints
Taolue Chen, Tingting Han, Joost-Pieter Katoen and Alexandru Mereacre. Quantitative Model Checking of Continuous-Time Markov Chains Against Timed Automata Specifications
Joachim Parrow, Magnus Johansson, Björn Victor and Jesper Bengtson. Psi-calculi: Mobile processes, nominal data, and logic
Anuj Dawar, Martin Grohe, Bjarki Holm and Bastian Laubner. Logics with Rank Operators
Marcello Bonsangue, jan rutten and Alexandra Silva. Algebras for Kripke Polynomial Coalgebras
Frank Pfenning and Robert Simmons. Substructural Operational Semantics as Ordered Logic Programming
Carles Creus, Guillem Godoy, Francesc Massanés and Ashish Tiwari. Non-linear Rewrite Closure and Weak Normalization
Chuck Liang and Dale Miller. A Unified Sequent Calculus for Focused Proofs
Sumit Nain and Moshe Vardi. Trace Semantics Is Fully Abstract

Back to the LICS web page.