LICS 2016: THIRTY FIRST ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE
PROGRAM

Days: Tuesday, July 5th Wednesday, July 6th Thursday, July 7th Friday, July 8th

Tuesday, July 5th

View this program: with abstractssession overviewtalk overview

09:00-10:40 Session 1A: Probabilistic Models of Computation
09:00
Stochastic mechanics of graph rewriting ( abstract )
09:25
On the Satisfiability of Some Simple Probabilistic Logics ( abstract )
09:50
Distinguishing Hidden Markov Chains ( abstract )
10:15
Quantitative Automata under Probabilistic Semantics ( abstract )
09:00-10:40 Session 1B: Decidability
09:00
Deciding First-Order Satisfiability when Universal and Existential Variables are Separated ( abstract )
09:25
The diagonal problem for higher-order recursive schemes is decidable ( abstract )
09:50
Two-variable logic with a between relation ( abstract )
10:15
Decidability and Complexity for Quiescent Consistency ( abstract )
13:40-15:20 Session 3A: Proof Theory
13:40
From positive and intuitionistic bounded arithmetic to proof complexity ( abstract )
14:05
Goedel's functional interpretation and the concept of learning ( abstract )
14:30
Understanding Gentzen and Frege Systems for QBF ( abstract )
14:55
Unified Semantics and Proof System for Classical, Intuitionistic and Affine Logics ( abstract )
13:40-15:20 Session 3B: Model Checking
13:40
Data Communicating Processes with Unreliable Channels ( abstract )
14:05
A New Perspective on FO Model Checking of Dense Graph Classes ( abstract )
14:30
Proving Liveness of Parameterized Programs ( abstract )
14:55
Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction ( abstract )
15:50-17:15 Session 4A: Automata Theory
15:50
Complexity of regular abstractions of one-counter languages ( abstract )
16:15
Two-Way Visibly Pushdown Automata and Transducers ( abstract )
16:40
Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings ( abstract )
15:50-17:15 Session 4B: Games and Logic
15:50
Plays as Resource Terms via Non-idempotent Intersection Types ( abstract )
16:15
Perfect-information Stochastic Games with Generalized Mean-Payoff Objectives ( abstract )
16:40
Games with bound guess actions ( abstract )
Wednesday, July 6th

View this program: with abstractssession overviewtalk overview

09:00-10:40 Session 5A: Model Theory
09:00
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps ( abstract )
09:25
Hanf normal form for first-order logic with unary counting quantifiers ( abstract )
09:50
Upper Bounds on the Quantifier Depth For Graph Differentiation in First Order Logic ( abstract )
10:15
Querying Visible and Invisible Information ( abstract )
09:00-10:34 Session 5B: Induction/Coinduction
09:00
Coinduction All the Way Up ( abstract )
09:25
Denotational semantics of recursive types in synthetic guarded domain theory ( abstract )
09:50
Type Theory based on Dependent Inductive and Coinductive Types ( abstract )
10:15
Program Equivalence is Coinductive ( abstract )
13:40-15:20 Session 7A: Semantics
13:40
Fixed Points in Quantitative Semantics ( abstract )
14:05
Ability to Count Messages Is Worth $\Theta(\Delta)$ Rounds in Distributed Computing ( abstract )
14:30
The Definitional Side of the Forcing ( abstract )
14:55
Towards Completeness via Proof Search in the Linear Time Mu-calculus ( abstract )
13:40-15:20 Session 7B: Monadic Second-Order Logic
13:40
First-order definability of rational transductions: An algebraic approach ( abstract )
14:05
Order Invariance on Decomposable Structures ( abstract )
14:30
Definability equals recognizability for graphs of bounded treewidth ( abstract )
14:55
Monadic second order logic as the model companion of temporal logic ( abstract )
15:50-17:15 Session 8A: Linear Logic
15:50
Interaction Graphs: Full Linear Logic ( abstract )
16:15
Conflict nets: efficient locally canonical MALL proof nets ( abstract )
16:40
Infinitary Lambda Calculi from a Linear Perspective ( abstract )
15:50-17:15 Session 8B: Reachability
15:50
First-order logic with reachability for infinite-state systems ( abstract )
16:15
The Complexity of Coverability in ν-Petri Nets ( abstract )
16:40
Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete ( abstract )
Thursday, July 7th

View this program: with abstractssession overviewtalk overview

09:00-10:40 Session 9A: Hybrid Systems
09:00
Comparing Chemical Reaction Networks: A Categorical and Algorithmic Perspective ( abstract )
09:25
A categorical approach to open and interconnected dynamical systems ( abstract )
09:50
Differential Refinement Logic ( abstract )
10:15
On Recurrent Reachability for Continuous Linear Dynamical Systems ( abstract )
09:00-10:40 Session 9B: Category Theory
09:00
Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints ( abstract )
09:25
Interacting Frobenius Algebras are Hopf. ( abstract )
09:50
Semi-galois Categories I: The Classical Eilenberg Variety Theory ( abstract )
10:15
A bifibrational reconstruction of Lawvere's presheaf hyperdoctrine ( abstract )
13:40-15:45 Session 11A: Type Theory
13:40
A Mechanization of the Blakers-Massey Connectivity Theorem in Homotopy Type Theory ( abstract )
14:05
Hybrid realizability for intuitionistic and classical choice ( abstract )
14:30
Trace semantics for polymorphic references ( abstract )
14:55
Constructions with Non-Recursive Higher Inductive Types ( abstract )
15:20
A constructive function-theoretic approach to topological compactness ( abstract )
13:40-15:45 Session 11B: Constraint Solving
13:40
The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems ( abstract )
14:05
Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction ( abstract )
14:30
Weak consistency notions for all the CSPs of bounded width ( abstract )
14:55
Graphs of relational structures: restricted colours ( abstract )
15:20
The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns ( abstract )
Friday, July 8th

View this program: with abstractssession overviewtalk overview

09:00-10:40 Session 13A: Probabilistic Models of Computation
09:00
Reasoning about Recursive Probabilistic Programs ( abstract )
09:25
Healthiness from Duality ( abstract )
09:50
Kolmogorov Extension, Martingale Convergence, and Compositionality of Processes ( abstract )
10:15
Quantitative Algebraic Reasoning ( abstract )
09:00-10:40 Session 13B: Algebraic Methods
09:00
Rewriting modulo symmetric monoidal structure ( abstract )
09:25
Effective Brenier's Theorem: Applications to Computable Analysis and Algorithmic Randomness ( abstract )
09:50
Quantifier Free Definability on Infinite Algebras ( abstract )
10:15
Factor Varieties and Symbolic Computation ( abstract )
13:40-15:20 Session 15A: Logics of Programs
13:40
Proving Differential Privacy via Probabilistic Couplings ( abstract )
14:05
On Thin Air Reads: Towards an Event Structures Model of Relaxed Memory ( abstract )
14:30
Towards Compositional Feedback in Non-Deterministic and Non-Input-Receptive Systems ( abstract )
14:55
Divide and Congruence II: Delay and Weak Bisimilarity ( abstract )
13:40-15:20 Session 15B: Decidability
13:40
How unprovable is Rabin's decidability theorem? ( abstract )
14:05
Solvability of Matrix-Exponential Equations ( abstract )
14:30
Order-Invariance of Two-Variable Logic is Decidable ( abstract )
14:55
A step up in expressiveness of decidable fixpoint logics ( abstract )
15:50-17:15 Session 16A: Complexity
15:50
Church Meets Cook and Levin ( abstract )
16:15
Complexity Theory of (Functions on) Compact Metric Spaces ( abstract )
16:40
Semantically Acyclic Conjunctive Queries under Functional Dependencies ( abstract )
15:50-17:15 Session 16B: Automata Theory
15:50
A Generalised Twinning Property for Minimisation of Cost Register Automata ( abstract )
16:15
Invisible Pushdown Languages ( abstract )
16:40
Minimization of Symbolic Tree Automata ( abstract )