Theoretical Computer Science

1. Front Matter

   PDF

2. Track A: Algorithms, Complexity and Models of Computation

   1. Zero-Suppressed Binary Decision Diagrams Resilient to Index Faults

      • Anna Bernasconi, Valentina Ciriani

      Pages 1-12

   2. On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs

      • Bugra Caskurlu, Vahan Mkrtchyan, Ojas Parekh, K. Subramani

      Pages 13-26

   3. Perfect Pipelining for Streaming Large File in Peer-to-Peer Networks

      • Fei Chen, Xiaowei Wu

      Pages 27-38

   4. The Shortest Path Game: Complexity and Algorithms

      • Andreas Darmann, Ulrich Pferschy, Joachim Schauer

      Pages 39-53

   5. Online Scheduling of Unit Length Jobs with Commitment and Penalties

      • Stanley P. Y. Fung

      Pages 54-65

   6. The Lazy Matroid Problem

      • Laurent Gourvès, Jérôme Monnot, Aris T. Pagourtzis

      Pages 66-77

   7. Treewidth Computation and Kernelization in the Parallel External Memory Model

      • Riko Jacob, Tobias Lieber, Matthias Mnich

      Pages 78-89

   8. Capturing Bisimulation-Invariant Complexity Classes with Higher-Order Modal Fixpoint Logic

      • Martin Lange, Etienne Lozes

      Pages 90-103

   9. Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions

      • Hiroki Morizumi

      Pages 104-110

   10. Subshifts, MSO Logic, and Collapsing Hierarchies

       • Ilkka Törmä

       Pages 111-122

   11. Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds’ Algorithm

       • Jiří Wiedermann

       Pages 123-135

   12. Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract)

       • Tomoyuki Yamakami

       Pages 136-150

3. Track B: Logic, Semantics, Specification and Verification

   1. Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus

      • Patrick Baillot, Erika De Benedetti, Simona Ronchi Della Rocca

      Pages 151-163

   2. A Hoare-Like Calculus Using the SROIQ^σ Logic on Transformations of Graphs

      • Jon Haël Brenas, Rachid Echahed, Martin Strecker

      Pages 164-178

   3. Termination Analysis for Graph Transformation Systems

      • H. J. Sander Bruggink, Barbara König, Hans Zantema

      Pages 179-194

   4. Tropical Two-Way Automata

      • Vincent Carnino, Sylvain Lombardy

      Pages 195-206

   5. Parametric LTL on Markov Chains

      • Souymodip Chakraborty, Joost-Pieter Katoen

      Pages 207-221

   6. Specifying and Verifying Properties of Space

      • Vincenzo Ciancia, Diego Latella, Michele Loreti, Mieke Massink

      Pages 222-235

   7. Primal Infon Logic with Conjunctions as Sets

      • Carlos Cotrini, Yuri Gurevich, Ori Lahav, Artem Melentyev

      Pages 236-249

This book constitutes the refereed proceedings of the 8th FIP WG 2.2 International Conference, TCS 2014, held in Rome, Italy, in September 2014. The 26 revised full papers presented, together with two invited talks, were carefully reviewed and selected from 73 submissions. [Suggestion--please check and add more if needed] TCS-2014 consisted of two tracks, with separate program committees, which dealt respectively with: - Track A: Algorithms, Complexity and Models of Computation, and - Track B: Logic, Semantics, Specification and Verification

• computational complexity
• design and analysis of algorithms
• formal languages and automata theory
• formal methods
• game theory
• graphs
• logic
• models of computation
• semantics and reasoning
• theory of computation
• type theory
• algorithm analysis and problem complexity

• Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya, Barcelona, Spain

  Josep Diaz

• Dipartimento di Informatica - Scienza e Ingegneria (DISI), Università di Bologna, Bologna, Italy

  Ivan Lanese, Davide Sangiorgi

Policies and ethics