Theoretical Computer Science

Zero-Suppressed Binary Decision Diagrams Resilient to Index Faults.- On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs.- Perfect Pipelining for Streaming Large File in Peer-to-Peer Networks.- The Shortest Path Game: Complexity and Algorithms.- Online Scheduling of Unit Length Jobs with Commitment and Penalties.- The Lazy Matroid Problem.- Treewidth Computation and Kernelization in the Parallel External Memory Model.- Capturing Bisimulation-Invariant Complexity Classes with Higher-Order Modal Fixpoint Logic.- Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions.- Subshifts, MSO Logic, and Collapsing Hierarchies.- Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds' Algorithm.- Not All Multi-valued Partial CFL Functions Are Refined by Single-Valued Functions.- Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus.- A Hoare-Like Calculus Using the SROIQs Logic on Transformations of Graphs.- Termination Analysis for Graph Transformation Systems.- Tropical Two-Way Automata.- Parametric LTL on Markov Chains.- Specifying and Verifying Properties of Space.- Primal Infon Logic with Conjunctions as Sets.- From Display Calculi to Deep Nested Sequent Calculi: Formalised for Full Intuitionistic Linear Logic.- Towards a Coalgebraic Chomsky Hierarchy (Extended Abstract).- Strong Completeness for Iteration-Free Coalgebraic Dynamic Logics.- Quantitative Types for the Linear Substitution Calculus.- Generic Partition Refinement Algorithms for Coalgebras and an Instantiation to Weighted Automata.- Looking at Separation Algebras with Boolean BI-eyes.- The Inhabitation Problem for Non-idempotent Intersection Types.

Davide Sangiorgi is Full Professor in Computer Science at the University of Bologna, Italy.