Current Trends in Theory and Practice of Computer Science
  Print-outs & Poster
Program and Presentations

Detailed Program

Invited Talks

  1. Jan 25, 09:15, Chair: Peter Bro Miltersen
    David Parkes: When Analysis Fails: Heuristic Mechanism Design via Self-Correcting Procedures [PDF]

  2. Jan 25, 11:00, Chair Jiri Wiederman
    Nicole Immorlica: Technology Diffusion in Social Networks: The Role of Compatibility [PPTX] [PPT]

  3. Jan 25, 15:30, Chair: Keith Jeffery
    Christian Attiogbe: Can Component/Service-based Systems be Proved Correct? [PDF]

  4. Jan 25, 17:15, Chair: Antonin Kucera
    Josh Berdine: Automatic Verication of Heap Manipulation using Separation Logic [PPSX]

  5. Jan 26, 09:00, Chair: Catuscia Palamidessi
    Giuseppe Longo: Randomness and Determination, from Physics and Computing towards Biology [PPT]

  6. Jan 28, 09:00, Chair: Branislav Rovan
    Marcin Jurdzinski: Algorithms for Solving Infinite Games [PDF]

  7. Jan 29, 09:00, Chair: Jan van Leeuwen
    Arne Andersson: A New Analysis of Expected Revenue: Combinatorial and Simultaneous Auctions [PPT]

  8. Jan 29, 10:45, Chair: Petr Tuma
    Radovan Janecek: Service Oriented Architecture Pitfalls [PPTX] [PPT]

  9. Jan 29, 15:30, Chair: Mogens Nielsen
    Christel Baier: Probabilistic Acceptors for Languages over Infinite Words [PDF]

  10. Jan 29, 17:15, Chair: Julius Stuller
    Dawson Engler: A Few Billion Lines of Code Later: Experiences in Commercializing a Static Checking Tool

  11. Jan 26, 20:00-21:00

    Keith Jeffery: ERCIM Roadshow [PPT]

Contributed Talks 1 - Jan 26, 10:45

  • Congress Hall - Foundations of Computer Science
    • Chair: Rica Gonen
    • Gerald Luettgen and Walter Vogler: Safe Reasoning with Logic LTS
    • Viliam Geffert and Dana Pardubska: Factoring and Testing Primes in Small Space [PPS]
    • Alexander Okhotin and Christian Reitwießner: Conjunctive grammars with restricted disjunction [PDF]
  • Room A - Theory and Practice of Software Services
    • Chair: Walter Binder
    • Walter Dosch and Annette Stuempel: Implementing Services by Partial State Machines [PDF]
    • Juan Jose Dominguez, Antonia Estero-Botaro and Inmaculada Medina-Bulo: A Framework for Mutant Genetic Generation for WS-BPEL [PDF]
    • Kaiyu Wan, Mubarak Mohammad and Vangalur Alagar: A Formal Model of Business Application Integration from Web Services [PPTX] [PPT]

Contributed Talks 2 - Jan 26, 15:30

  • Congress Hall - Foundations of Computer Science
    • Chair: Jaroslav Pokorny
    • Laurent Gourves, Adria Lyra, Carlos Martinhon and Jerome Monnot: The minimum reload s-t path/trail/walk problems [PPT]
    • Maria Rita Di Berardini, Flavio Corradini and Walter Vogler: Time and Fairness in a Process Algebra with Non-Blocking Reading [PDF]
    • Taku Aratsu, Kouichi Hirata and Tetsuji Kuboyama: Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes [PPT]
  • Room A - Foundations of Computer Science
    • Chair: Giuseppe Longo
    • David Frutos Escrig, Carlos Gregorio-Rodríguez and Miguel Palomino: On the unification of process semantics: observational semantics [PDF]
    • Martin Kutrib, Hartmut Messerschmidt and Friedrich Otto: On stateless deterministic restarting automata [PDF]
    • Frederic Peschanski and Joel-Alexis Bialkiewicz: Modelling and Verifying Mobile Systems using Pi-graphs [PDF]
  • Room B - Theory and Practice of Software Services
    • Chair: Lubomir Bulej
    • Ondrej Habala, Marek Paralic, Viera Rozinajova and Peter Bartalos: Semantically-aided Data-aware Service Workflow Composition [PPT]
    • Dongpil Kwak, Joongsoo Lee, Dohyun Kim and Younghee Lee: User Care Preference-based Semantic Service [PPT]
    • Walter Binder and Niranjan Suri: Green Computing: Energy Consumption Optimized Service Hosting [PPT]

Contributed Talks 3 - Jan 26, 17:15

  • Congress Hall - Foundations of Computer Science
    • Chair: Christian Attiogbe
    • Reinhard Bauer, Gianlorenzo D'Angelo, Daniel Delling and Dorothea Wagner: The Shortcut Problem -- Complexity and Approximation [PDF]
    • Philippe Moser and Elvira Mayordomo: Polylog space compression is incomparable with Lempel-Ziv and pushdown compression [PDF]
    • Stefan Porschen and Tatjana Schmidt: On Some SAT-Variants over Linear Formulas [PDF]
  • Room A - Foundations of Computer Science
    • Chair: Viliam Geffert
    • Cinzia Di Giusto, Maurizio Gabbrielli and Maria Chiara Meo: Expressiveness of multiple heads in CHR [PDF]
    • Beate Bollig: On the OBDD complexity of threshold functions and the variable ordering problem [PDF]
    • Martin Dietzfelbinger and Ulf Schellbach: Weaknesses of cuckoo hashing with a simple universal hash class: The case of large universes [PDF]
  • Room B - Game Theoretic Aspects of E-commerce
    • Chair: Arne Andersson
    • Kim Thang Nguyen: NP-hardness about Nash equilibrium using negated gadgets [PDF]
    • Rica Gonen and Elam Pavlov: Adaptive Incentive-Compatible Sponsored Search Auction [PDF]

Contributed Talks 4 - Jan 27, 09:00

  • Congress Hall - Foundations of Computer Science
    • Chair: Jan Janecek
    • Henning Wunderlich: On Toda's Theorem in structural communication complexity [PDF]
    • Grzegorz Stachowiak: Asynchronous deterministic rendezvous on the line [PDF]
    • Hannes Moser: Problem Kernelization for Graph Packing [PDF]
  • Room A - Techniques and Tools for Formal Verification
    • Chair: Josh Berdine
    • Thomas Chatain, Paul Gastin and Nathalie Sznajder: Natural specifications yield decidability for distributed synthesis of asynchronous systems [PDF]
    • Sebastian Mauser, Robert Lorenz and Gabriel Juhas: Partial Order Semantics of Types of Nets [PPT]
    • Johann Schuster, Jens Bachmann, Markus Siegle and Martin Riedl: An Efficient Symbolic Elimination Algorithm for the Stochastic Process Algebra tool CASPA [PDF]

Contributed Talks 5 - Jan 27, 10:45

  • Congress Hall - Foundations of Computer Science
    • Chair: Filip Zavoral
    • Jan Jezabek: Increasing Machine Speed in On-line Scheduling of Weighted Unit-length Jobs in Slotted Time [PDF]
    • Johannes C. Schneider: Unambiguous Erasing Morphisms in Free Monoids [PDF]
    • Marcella Anselmo, Natasha Jonoska and Maria Madonia: Framed versus Unframed Two-Dimensional Recognizable Languages [PPT]
  • Room A - Foundations of Computer Science
    • Chair: Dana Pardubska
    • Simone Faro and Domenico Cantone: Patter Matching with Swaps in Linear Time for Short Patterns [PDF]
    • Robert Koenig, Ueli Maurer and Stefano Tessaro: Abstract Storage Devices [PDF]
    • Taolue Chen, Wan Fokkink and Rob van Glabbeek: On Finite Bases for Weak Semantics: Failures versus Impossible Futures [PDF]
  • Room B - Techniques and Tools for Formal Verification
    • Chair: Gabriel Juhas
    • René Thiemann: From outermost termination to innermost termination [PDF]
    • Nguyen Van Tang and Mizuhito Ogawa: Event-Clock Visibly Pushdown Automata [PPT]
    • Frederic Vogels, Bart Jacobs and Frank Piessens: A machine checked soundness proof for an intermediate verification language [PDF]

Contributed Talks 6 - Jan 28, 10:45

  • Congress Hall - Foundations of Computer Science
    • Chair: Christel Baier
    • Taishin Daigo and Kouichi Hirata: On Generating Maximal Acyclic Subhypergraphs with Polynomial Delay [PPTX] [PPT]
    • Torsten Tholey: Improved Algorithms for the 2-Vertex Disjoint Paths Problem [PDF]
    • Ruslans Tarasovs and Rusins Freivalds: Group Input Machine [PDF]
    • Suzana Andova and Sonja Georgievska: On Compositionality, Efficiency and Applicability of Abstraction in Probabilistic Systems [PDF]
  • Room A - Foundations of Computer Science
    • Chair: Marcin Jurdzinski
    • Klaus Reinhardt: The Simple Reachability Problem in Switch Graphs [PDF]
    • Konstantinos Chatzikokolakis, Sophia Knight and Prakash Panangaden: Epistemic Strategies and Games on Concurrent Processes [PDF]
    • Caron Pascal, Jean-Marc Champarnaud and Ludovic Mignot: A New Family of Regular Operators Fitting with the Position Automaton Construction [PDF]
  • Room B - Techniques and Tools for Formal Verification
    • Chair: Gabriel Juhas
    • Kong Susanto, Tim Todman, Jose Coutinho and Wayne Luk: Design Validation by Symbolic Simulation and Equivalence Checking: A Case Study in Memory Optimisation for Image Manipulation [ODP] [PDF]
    • Min Wan and Gianfranco Ciardo: Symbolic Reachability Analysis of Integer Timed Petri Nets [PDF]
    • Min Wan and Gianfranco Ciardo: On-the-fly symbolic state-space generation of asynchronous systems using extensible decision diagrams [PDF]
    • Ansgar Fehnker, Ralf Huuck, Bastian Schlich and Michael Tapp: Automatic Bug Detection in Microcontroller Software by Static Program Analysis [PPT]

Student Research Forum - Jan 28, 15:30

  • Chair: Maria Bielikova [PPT]

  • Benedek Nagy and Peter Varga: A New Normal Form for Context-Sensitive Grammars [PPT]
  • Ginta Garkaje and Rusins Freivalds: Quantum and probabilistic finite multitape automata [PPT]
  • Anna Urbanska: Application of Graph Separators to the Efficient Division-Free Computation of Determinant [PPT]
  • Lelde Lace, Oksana Scegulnaja-Dubrovska and Rusins Freivalds: Languages Recognizable by Quantum Finite Automata with cut-point 0 [PPT]
  • Romain Beauxis: A smooth probabilistic extension of concurrent constraint programming [PDF]
  • Tomas Potuzak and Pavel Herout: An Efficient Communication Protocol for Distributed Traffic Simulation: Introduction of the Long Step Method [PPT]
  • Pavel Loupal and Karel Richta: XML Query Evaluation Using a Lambda Calculus Based Framework [PPT]
  • Suzette Stoutenburg, Jugal Kalita and Shayn Hawthorne: Extracting Semantic Relationships between Wikipedia Articles [PPT]
  • Suzette Stoutenburg, Jugal Kalita and Justin Gray: Acquiring Complex Cross-Ontological Relationships [PPT]

Posters - Jan 28, 15:30

  • Chair: Maria Bielikova

  • Vera Kurkova: Model Complexity in Learning from High-Dimensional Data
  • Simone Faro and Thierry Lecroq: Efficient Pattern Matching on Binary Strings
  • Simone Faro and Domenico Cantone:A Faster Algorithm for the Single Source Shortest Path Problem in the Presence of Few Sources or Destinations of Negative

SOFSEM 2009, January 24-30, 2009, ©pindlerùv Mlýn, Czech Republic