| 2016 | Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete. | Matthias Englert, Ranko Lazic, Patrick Totzke |
| 2016 | Order Invariance on Decomposable Structures. | Michael Elberfeld, Marlin Frickenschmidt, Martin Grohe |
| 2016 | Interacting Frobenius Algebras are Hopf. | Ross Duncan, Kevin Dunne |
| 2016 | Towards Completeness via Proof Search in the Linear Time μ-calculus: The case of Bchi inclusions. | Amina Doumane, David Baelde, Lucca Hirschi, Alexis Saurin |
| 2016 | First-order logic with reachability for infinite-state systems. | Emanuele D'Osualdo, Roland Meyer, Georg Zetzsche |
| 2016 | Decidability and Complexity for Quiescent Consistency. | Brijesh Dongol, Robert M. Hierons |
| 2016 | Unifying Logical and Statistical AI. | Pedro M. Domingos, Daniel Lowd, Stanley Kok, Aniruddh Nath, Hoifung Poon, Matthew Richardson, Parag Singla |
| 2016 | A Generalised Twinning Property for Minimisation of Cost Register Automata. | Laure Daviaud, Pierre-Alain Reynier, Jean-Marc Talbot |
| 2016 | From positive and intuitionistic bounded arithmetic to monotone proof complexity. | Anupam Das |
| 2016 | Two-Way Visibly Pushdown Automata and Transducers. | Luc Dartois, Emmanuel Filiot, Pierre-Alain Reynier, Jean-Marc Talbot |
| 2016 | Minimization of Symbolic Tree Automata. | Loris D'Antoni, Margus Veanes |
| 2016 | The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns. | Martin C. Cooper, Stanislav Zivn |
| 2016 | Games with bound guess actions. | Thomas Colcombet, Stefan Gller |
| 2016 | The Diagonal Problem for Higher-Order Recursion Schemes is Decidable. | Lorenzo Clemente, Pawel Parys, Sylvain Salvati, Igor Walukiewicz |
| 2016 | On Recurrent Reachability for Continuous Linear Dynamical Systems. | Ventsislav Chonev, Jol Ouaknine, James Worrell |
| 2016 | Quantitative Automata under Probabilistic Semantics. | Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop |
| 2016 | Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction. | Krishnendu Chatterjee, Wolfgang Dvork, Monika Henzinger, Veronika Loitzenbauer |
| 2016 | Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives. | Krishnendu Chatterjee, Laurent Doyen |
| 2016 | On the Satisfiability of Some Simple Probabilistic Logics. | Souymodip Chakraborty, Joost-Pieter Katoen |
| 2016 | Comparing Chemical Reaction Networks: A Categorical and Algorithmic Perspective. | Luca Cardelli, Mirco Tribastone, Max Tschaikowski, Andrea Vandin |
| 2016 | Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings. | Arnaud Carayol, Christof Lding, Olivier Serre |
| 2016 | Graphs of relational structures: restricted types. | Andrei A. Bulatov |
| 2016 | Rewriting modulo symmetric monoidal structure. | Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski, Fabio Zanasi |
| 2016 | Definability equals recognizability for graphs of bounded treewidth. | Mikolaj Bojanczyk, Michal Pilipczuk |
| 2016 | Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction. | Manuel Bodirsky, Antoine Mottet |