LICS 2015 Accepted Papers

Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase and Pierre McKenzie. Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-Complete
Krishnendu Chatterjee, Monika Henzinger and Veronika Loitzenbauer. Improved Algorithms for One-Pair and k-Pair Streett Objectives
Tomasz Gogacz and Jerzy Marcinkowski. The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable.
Facundo Carreiro. Characterization theorems for PDL and FO(TC)
Jiri Adamek, Stefan Milius, Robert Myers and Henning Urbat. Varieties of Languages in a Category
Sebastian Enqvist, Fatemeh Seifan and Yde Venema. Monadic Second-Order Logic and Bisimulation Invariance for Coalgebras
Annabelle McIver, Carroll Morgan and Tahiry Rabehaja. Abstract Hidden Markov Models: a monadic account of quantitative information flow
Fabian Reiter. Distributed Graph Automata
Nathanael Ackerman, Cameron Freer and Robert Lubarsky. Feedback Turing Computability, and Turing Computability as Feedback
Jennifer Hackett and Graham Hutton. Programs for Cheap!
Erich Grädel, Łukasz Kaiser, Wied Pakusa and Svenja Schalthöfer. Characterising Choiceless Polynomial Time with First-Order Interpretations
Felix Canavoi, Erich Grädel, Simon Leßenich and Wied Pakusa. Defining winning strategies in fixed-point logic
Michael Benedikt, Thomas Colcombet, Balder Ten Cate and Michael Vanden Boom. The Complexity of Boundedness for Guarded Logics
Antoine Amarilli and Michael Benedikt. Finite Open-World Query Answering with Number Restrictions
Meghyn Bienvenu, Stanislav Kikot and Vladimir Podolskii. Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results
Michael Benedikt, Balder Ten Cate and Michael Vanden Boom. Interpolation with Decidable Fixpoint Logics
Naoki Kobayashi and Xin Li. Automata-Based Abstraction Refinement for muHORS Model Checking
Andreas Krebs and Oleg Verbitsky. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth
Udi Boker, Thomas Henzinger and Jan Otop. The Target Discounted-Sum Problem
Chris Heunen and Bert Lindenhovius. Domains of Commutative C*-subalgebras
Catarina Carvalho, Florent Madelaine and Barnaby Martin. From complexity to algebra and back: digraph classes, collapsibility and the PGP
Krishnendu Chatterjee, Thomas Henzinger and Jan Otop. Nested Weighted Automata
Lorenzo Clemente and Sławomir Lasota. Timed pushdown automata revisited
Takeshi Tsukada and Luke Ong. Nondeterminism in Game Semantics via Sheaves
Tim Disney and Cormac Flanagan. Traces for Type Soundness
Guillaume Munch-Maccagnoni and Gabriel Scherer. Polarised Intermediate Representation of λ Calculus with Sums
Matthias Baaz, Alexander Leitsch and Giselle Reis. A note on the complexity of classical and intuitionistic proofs
Thomas Place. Separating Regular Languages with Two Quantifier Alternations
Lorenzo Clemente and Jean-François Raskin. Controller synthesis for the multidimensional beyond worst-case and almost-sure problems
Arno Pauly and Matthew de Brecht. Descriptive Set Theory in the category of Represented Spaces
Tomas Brazdil, Stefan Kiefer, Antonin Kucera and Petr Novotný. Long-Run Average Behaviour of Probabilistic Vector Addition Systems
Arnold Beckmann and Norbert Preining. Hyper Natural Deduction
Abbas Edalat. Extension of Domain Maps in Differential and Integral Calculus
Arnaud Carayol and Olivier Serre. How Good Is a Strategy in a Game With Nature?
Paul Brunet and Damien Pous. Petri automata for Kleene allegories
Diego Figueira and Leonid Libkin. Path Logics for Querying Graphs: Combining Expressiveness and Efficiency
Joerg Endrullis, Clemens Grabmayer and Dimitri Hendriks. Regularity Preserving but not Reflecting Encodings
Raphaëlle Crubillé and Ugo Dal Lago. Metric Reasoning About Lambda-Terms: The Affine Case
Krishnendu Chatterjee, Zuzana Komarkova and Jan Kretinsky. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes
Mikolaj Bojanczyk. Star Height via Games
Jérôme Leroux and Sylvain Schmitz. Reachability in Vector Addition Systems Demystified
Simon Castellan, Pierre Clairambault and Glynn Winskel. The parallel intentionally fully abstract games model of PCF
Borja Balle, Prakash Panangaden and Doina Precup. A Canonical Form for Weighted Automata and Applications to Approximate Minimization
Ugo Dal Lago, Claudia Faggian, Benoit Valiron and Akira Yoshimizu. Parallelism and Synchronization in an Infinitary Context
Amar Hadzihasanovic. A Diagrammatic Axiomatisation for Qubit Entanglement
Beniamino Accattoli and Claudio Sacerdoti Coen. On the Usefulness of Constructors
Anupam Das and Colin Riba. A complete axiomatisation of MSO on infinite trees
Wojciech Czerwiński and Petr Jancar. Branching Bisimilarity of Normed BPA Processes is in NEXPTIME
Bartek Klin, Eryk Kopczyński, Joanna Ochremiak and Szymon Toruńczyk. Locally finite Constraint Satisfaction Problems
Laura Bozzelli and David Pearce. On the complexity of Temporal Equilibrium Logic
Victor Dalmau, Laszlo Egri, Benoit Larose, Arash Rafiey and Pavol Hell. Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy
Kenji Maillard and Paul-André Melliès. A fibrational account of local states
Andrzej Murawski, Steven Ramsay and Nikos Tzevelekos. Bisimilarity in fresh-register automata
Antonia Lechner, Joel Ouaknine and James Worrell. On the Complexity of Linear Arithmetic with Divisibility
Albert Atserias and Jose Balcazar. Entailment among probabilistic implications
Benoît Monin and Andre Nies. A unifying approach to the Gamma question
Dominic Hughes and Willem Heijltjes. Complexity Bounds for Sum-Product Logic via Additive Proof Nets and Petri Nets
Daniel R. Licata and Guillaume Brunerie. A Cubical Approach to Synthetic Homotopy Theory
Chaodong He and Mingzhang Huang. Branching Bisimilarity on Normed BPA Is EXPTIME-complete
Tomer Kotek, Mantas Simkus, Helmut Veith and Florian Zuleger. Extending ALCQIO with Reachability: Between Finite Model Theory and Description Logic
Adria Gascon, Manfred Schmidt-Schauss and Ashish Tiwari. One Context Unification Problems Solvable in Polynomial Time