LICS 2016 Accepted Papers

Brijesh Dongol and Rob Hierons. Decidability and Complexity for Quiescent Consistency
Matthias Englert, Ranko Lazic and Patrick Totzke. Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete
Loris D'Antoni and Margus Veanes. Minimization of Symbolic Tree Automata
Eryk Kopczynski. Invisible Pushdown Languages
Diego Figueira. Semantically Acyclic Conjunctive Queries under Functional Dependencies
Chuck Liang. Unified Semantics and Proof System for Classical, Intuitionistic and Affine Logics
Iosif Petrakis. A constructive function-theoretic approach to topological compactness
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger and Veronika Loitzenbauer. Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction
Nicolai Kraus. Constructions with Non-Recursive Higher Inductive Types
Martin C. Cooper and Stanislav Živný. The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
Krishnendu Chatterjee, Thomas Henzinger and Jan Otop. Quantitative Automata under Probabilistic Semantics
Steen Vester. Winning Cores in Parity Games
Wan Fokkink and Rob Van Glabbeek. Divide and Congruence II: Delay and Weak Bisimilarity
Michael Benedikt, Pierre Bourhis, Gabriele Puppis and Balder Ten Cate. Querying Visible and Invisible Information
Michael Benedikt, Pierre Bourhis and Michael Vanden Boom. A step up in expressiveness of decidable fixpoint logics
Ranko Lazic and Sylvain Schmitz. The Complexity of Coverability in ν-Petri Nets
Thomas Zeume and Frederik Harwath. Order- Invariance of Two-Variable Logic is Decidable
Sandra Kiefer and Pascal Schweitzer. Upper Bounds on the Quantifier Depth For Graph Differentiation in First Order Logic
Alex Galicki. Effective Brenier's Theorem: Applications to Computable Analysis and Algorithmic Randomness
Olaf Beyersdorff and Jan Pich. Understanding Gentzen and Frege Systems for QBF
Amina Doumane, David Baelde, Lucca Hirschi and Alexis Saurin. Towards Completeness via Proof Search in the Linear Time Mu-calculus
Lucas Heimberg, Dietrich Kuske and Nicole Schweikardt. Hanf normal form for first-order logic with unary counting quantifiers
Antonino Salibra, Giulio Manzonetto and Giordano Favro. Factor Varieties and Symbolic Computation
Andreas Krebs, Howard Straubing, Kamal Lodaya and Paritosh Pandya. Two-variable logic with a between predicate
Andrei Bulatov. Graphs of relational structures: restricted colours
Bakh Khoussainov. Quantifier Free Definability on Infinite Algebras
Thomas Powell. Goedel's functional interpretation and the concept of learning
Azadeh Farzan, Zachary Kincaid and Andreas Podelski. Proving Liveness of Parameterized Programs
Stefan Kiefer and A. Prasad Sistla. Distinguishing Hidden Markov Chains
Silvio Ghilardi and Samuel J. van Gool. Monadic second order logic as the model companion of temporal logic
Akitoshi Kawamura, Florian Steinberg and Martin Ziegler. Complexity Theory of (Functions on) Compact Metric Spaces
Dexter Kozen. Kolmogorov Extension, Martingale Convergence, and Compositionality of Processes
Thomas Colcombet and Stefan Göller. Games with bound guess actions
Viorel Preoteasa and Stavros Tripakis. Towards Compositional Feedback in Non-Deterministic and Non-Input-Receptive Systems
Arnaud Carayol, Christof Löding and Olivier Serre. Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings
Ugo Dal Lago. Infinitary Lambda Calculi from a Linear Perspective
Dirk Pattinson and Lutz Schröder. Program Equivalence is Coinductive
Mikołaj Bojańczyk and Michał Pilipczuk. Definability equals recognizability for graphs of bounded treewidth
Guilhem Jaber and Nikos Tzevelekos. Trace semantics for polymorphic references
Marcin Kozik. Weak consistency notions for all the CSPs of bounded width
Valentin Blot. Hybrid realizability for intuitionistic and classical choice
Krishnendu Chatterjee and Laurent Doyen. Perfect-information Stochastic Games with Generalized Mean-Payoff Objectives
Henning Basold and Herman Geuvers. Type Theory based on Dependent Inductive and Coinductive Types
Manuel Bodirsky and Antoine Mottet. Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
Rasmus Ejlers Møgelberg and Marco Paviotti. Denotational semantics of recursive types in synthetic guarded domain theory
Michael Elberfeld, Marlin Frickenschmidt and Martin Grohe. Order Invariance on Decomposable Structures
Radu Mardare, Prakash Panangaden and Gordon Plotkin. Quantitative Algebraic Reasoning
Emmanuel Filiot, Olivier Gauwin and Nathan Lhote. First-order definability of rational transductions: An algebraic approach
Sam Staton, Hongseok Yang, Chris Heunen, Ohad Kammar and Frank Wood. Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints
Paul-André Melliès and Noam Zeilberger. A bifibrational reconstruction of Lawvere's presheaf hyperdoctrine
Souymodip Chakraborty and Joost-Pieter Katoen. On the Satisfiability of Some Simple Probabilistic Logics
Lorenzo Clemente, Paweł Parys, Sylvain Salvati and Igor Walukiewicz. The diagonal problem for higher-order recursive schemes is decidable
Takeo Uramoto. Semi-galois Categories I: The Classical Eilenberg Variety Theory
Jakub Gajarský, Petr Hlineny, Daniel Lokshtanov, Jan Obdrzalek and M. S. Ramanujan. A New Perspective on FO Model Checking of Dense Graph Classes
Marco Voigt, Christoph Weidenbach and Thomas Sturm. Deciding First-Order Satisfiability when Universal and Existential Variables are Separated
Luc Dartois, Emmanuel Filiot, Pierre-Alain Reynier and Jean-Marc Talbot. Two-Way Visibly Pushdown Automata and Transducers
Parosh Aziz Abdulla, C. Aiswarya and Mohamed Faouzi Atig. Data Communicating Processes with Unreliable Channels
Alan Jeffrey and James Riely. On Thin Air Reads: Towards an Event Structures Model of Relaxed Memory
Nicolas Behr, Vincent Danos and Ilias Garnier. Stochastic mechanics of graph rewriting
Joel Ouaknine, Amaury Pouly, Joao Sousa-Pinto and James Worrell. Solvability of Matrix-Exponential Equations
Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski and Fabio Zanasi. Rewriting modulo symmetric monoidal structure
Damiano Mazza. Church Meets Cook and Levin
Leszek Aleksander Kołodziejczyk and Henryk Michalewski. How unprovable is Rabin's decidability theorem?
Libor Barto and Michael Pinsker. The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
Kuen-Bang Hou, Eric Finster, Daniel R. Licata and Peter Lumsdaine. A Mechanization of the Blakers-Massey Connectivity Theorem in Homotopy Type Theory
Federico Olmedo, Benjamin Lucien Kaminski, Joost-Pieter Katoen and Christoph Matheja. Reasoning about Recursive Probabilistic Programs
Ventsislav Chonev, Joel Ouaknine and James Worrell. On Recurrent Reachability for Continuous Linear Dynamical Systems
Laure Daviaud, Pierre-Alain Reynier and Jean-Marc Talbot. A Generalised Twinning Property for Minimisation of Cost Register Automata
Ross Duncan and Kevin Dunne. Interacting Frobenius Algebras are Hopf.
Emanuele D'Osualdo, Roland Meyer and Georg Zetzsche. First-order logic with reachability for infinite-state systems
Takeshi Tsukada and Luke Ong. Plays as Resource Terms via Non-idempotent Intersection Types
Gilles Barthe, Marco Gaboardi, Benjamin Grégoire, Justin Hsu and Pierre-Yves Strub. Proving Differential Privacy via Probabilistic Couplings
Sarah Loos and André Platzer. Differential Refinement Logic
Brendan Fong, Paolo Rapisarda and Pawel Sobocinski. A categorical approach to open and interconnected dynamical systems
Luca Cardelli, Mirco Tribastone, Max Tschaikowski and Andrea Vandin. Comparing Chemical Reaction Networks: A Categorical and Algorithmic Perspective
Dominic Hughes and Willem Heijltjes. Conflict nets: locally canonical P-time proof nets for MALL
Christoph Berkholz and Jakob Nordström. Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
Mohamed Faouzi Atig, Dmitry Chistikov, Piotr Hofman, K. Narayan Kumar, Prakash Saivasan and Georg Zetzsche. Complexity of regular abstractions of one-counter languages
Wataru Hino, Hiroki Kobayashi, Ichiro Hasuo and Bart Jacobs. Healthiness from Duality
Damien Pous. Coinduction All the Way Up
Guilhem Jaber, Gabriel Lewertowski, Pierre-Marie Pédrot, Matthieu Sozeau and Nicolas Tabareau. The Definitional Side of the Forcing
Tuomo Lempiäinen. Ability to Count Messages Is Worth $\Theta(\Delta)$ Rounds in Distributed Computing
Thomas Seiller. Interaction Graphs: Full Linear Logic
James Laird. Fixed Points in Quantitative Semantics
Anupam Das. From positive and intuitionistic bounded arithmetic to proof complexity