LICS 2012 Accepted Papers

  1. Parosh Abdulla, Mohamed Faouzi Atig and Jari Stenman. Dense-Timed Pushdown Automata
  2. Jiří Adámek, Nathan Bowler, Paul Blain Levy and Stefan Milius. Coproducts of Monads on Set
  3. Manindra Agrawal, S. Akshay, Blaise Genest and P. S. Thiagarajan. Approximate Verification of the Symbolic Dynamics of Markov Chains
  4. Rajeev Alur, Emmanuel Filiot and Ashutosh Trivedi. Regular Transformations of Infinite Strings
  5. Robert Atkey. The Semantics of Parsing with Semantic Actions
  6. Albert Atserias, Moritz Müller and Sergi Oliva. Proof Complexity of Relativized Statements
  7. Arnon Avron, Beata Konikowska and Anna Zamansky. Modular Construction of Cut-Free Sequent Calculi for Paraconsistent Logics
  8. Steve Awodey, Nicola Gambino and Kristina Sojakova. Inductive Types in Homotopy Type Theory
  9. David Baelde and Gopalan Nadathur. Combining Deduction Modulo and Logics of Fixed-Point Definitions
  10. Pablo Barceló, Diego Figueira and Leonid Libkin. Graph Logics with Rational Relations and the Generalized Intersection Problem
  11. Libor Barto, Marcin Kozik and Ross Willard. Near Unanimity Constraints have Bounded Pathwidth Duality
  12. Christoph Berkholz. Lower Bounds for Existential Pebble Games and k-Consistency Tests
  13. Jean-Philippe Bernardy and Guilhem Moulin. A Computational Interpretation of Parametricity
  14. Daniel Bundala, Joel Ouaknine and James Worrell. On the Magnitude of Completeness Thresholds in Bounded Model Checking
  15. Arnaud Carayol and Olivier Serre. Collapsible Pushdown Automata and Labeled Recursion Schemes: Equivalence, Safety and Effective Selection
  16. Krishnendu Chatterjee and Laurent Doyen. Partial-Observation Stochastic Games: How to Win when Belief Fails
  17. Krishnendu Chatterjee and Mathieu Tracol. Decidable Problems for Probabilistic Automata on Infinite Words
  18. Krishnendu Chatterjee and Yaron Velner. Mean-Payoff Pushdown Games
  19. Hubie Chen and Victor Dalmau. Decomposing Quantified Conjunctive (or Disjunctive) Formulas
  20. Hubie Chen and Moritz Müller. An Algebraic Preservation Theorem for ℵ0-categorical Quantified Constraint Satisfaction
  21. Yijia Chen and Jörg Flum. On the Ordered Conjecture
  22. Pierre Clairambault, Julian Gutierrez and Glynn Winskel. The Winning Ways of Concurrent Games
  23. Bob Coecke, Ross Duncan, Aleks Kissinger and Quanlong Wang. Strong Complementarity and Non-locality in Categorical Quantum Mechanics
  24. Carles Creus, Adrià Gascón, Guillem Godoy and Lander Ramos. The HOM Problem is EXPTIME-complete
  25. Michael Elberfeld, Martin Grohe and Till Tantau. Where First-Order and Monadic Second-Order Logic Coincide
  26. Javier Esparza, Pierre Ganty and Rupak Majumdar. A Perfect Model for Bounded Verification
  27. Nathanaël Fijalkow, Hugo Gimbert and Youssouf Oualhadj. Deciding the Value 1 Problem of Probabilistic Leaktight Automata
  28. Deepak Garg, Valerio Genovese and Sara Negri. Countermodels from Sequent Calculi in Multi-Modal Logics
  29. Sicun Gao, Jeremy Avigad and Edmund Clarke. Delta-Decidability over the Reals
  30. Serge Grigorieff and Pierre Valarcher. Functionals using Bounded Information and the Dynamics of Algorithms
  31. Stefan Göller, Jean Christoph Jung and Markus Lohrey. The Complexity of Decomposing Modal and First-Order Theories
  32. Clemens Grabmayer, Joerg Endrullis, Dimitri Hendriks, Jan Willem Klop and Lawrence S. Moss. Automatic Sequences and Zip-Specifications
  33. Serge Haddad, Sylvain Schmitz and Philippe Schnoebelen. The Ordinal-Recursive Complexity of Timed-Arc Petri Nets, Data Nets, and Other Enriched Nets
  34. Hugo Herbelin. A Constructive Proof of the Axiom of Dependent Choice, Compatible with Classical Logic
  35. Frédéric Herbreteau, B. Srivathsan and Igor Walukiewicz. Better Abstractions for Timed Automata
  36. Naohiko Hoshino. Step Indexed Realizability Semantics for a Call-by-Value Language Based on Basic Combinatorial Objects
  37. Guilhem Jaber, Nicolas Tabareau and Matthieu Sozeau. Extending Type Theory with Forcing
  38. Sanjay Jain, Alexei Miasnikov and Frank Stephan. The Complexity of Verbal Languages over Groups
  39. Petr Jancar. Bisimulation Equivalence for First-Order Grammars
  40. Jean-Baptiste Jeannin and Dexter Kozen. Capsules and Separation Logic
  41. Emanuel Kieronski, Jakub Michaliszyn, Ian Pratt-Hartmann and Lidia Tendera. Two-Variable First-Order Logic with Equivalence Closure
  42. Anvesh Komuravelli, Corina S. Pasareanu and Edmund M. Clarke. Learning Probabilistic Systems from Tree Samples
  43. Andreas Krebs and A. V. Sreejith. Non-definability of Languages by Generalized First-Order Formulas over (N,+)
  44. Stephan Kreutzer, Sebastian Siebertz and Viktor Engelmann. Model-Checking on Ordered Structures
  45. Annabelle McIver, Larissa Meinicke and Carroll Morgan. A Kantorovich-Monadic Powerdomain for Information Hiding, with Probability and Nondeterminism
  46. Damiano Mazza. An Infinitary Affine Lambda-Calculus Isomorphic to the Full Lambda-Calculus
  47. Paul-André Melliès. Game Semantics in String Diagrams
  48. Jakub Michaliszyn and Jan Otop. Decidable Elementary Modal Logics
  49. Benoît Monin and Laurent Bienvenu. von Neumann's Biased Coin Revisited
  50. Sebastian Muller and Iddo Tzameret. Short Propositional Refutations for Dense Random 3CNF Formulas
  51. Vivek Nigam. On the Complexity of Linear Authorization Logics
  52. Pawel Parys. On the Significance of the Collapse Operation
  53. Adrien Piérard and Eijiro Sumii. A Higher-Order Distributed Calculus with Name Creation
  54. Andre Platzer. The Complete Proof Theory of Hybrid Systems
  55. Sasha Rubin and Alexander Rabinovich. Interpetations in Scattered Trees
  56. David Sabel and Manfred Schmidt-Schauss. Conservative Concurrency in Haskell
  57. Peter Schuster. Induction in Algebra: A First Case Study
  58. Hugh Steele and Andrea Schalk. Constructing Fully Complete Models for Multiplicative Linear Logic
  59. Tony Tan. An Automata Model for Trees with Ordered Data Values
  60. Dmitriy Traytel, Andrei Popescu and Jasmin Christian Blanchette. Foundational, Compositional (Co)Datatypes for Higher-Order Logic
  61. Jamie Vicary. Higher Semantics of Quantum Protocols