Current Trends in Theory and Practice of Computer Science
  Print-outs & Poster
Accepted Papers

Foundations of Computer Science

7: Gerald Luettgen and Walter Vogler: Safe Reasoning with Logic LTS

8: Viliam Geffert and Dana Pardubska: Factoring and Testing Primes in Small Space

13: Alexander Okhotin and Christian Reitwießner: Conjunctive grammars with restricted disjunction

16: Laurent Gourves, Adria Lyra, Carlos Martinhon and Jerome Monnot: The minimum reload s-t path/trail/walk problems

26: Maria Rita Di Berardini, Flavio Corradini and Walter Vogler: Time and Fairness in a Process Algebra with Non-Blocking Reading

28: Taku Aratsu, Kouichi Hirata and Tetsuji Kuboyama: Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes

30: David Frutos Escrig, Carlos Gregorio-Rodríguez and Miguel Palomino: On the unification of process semantics: Observational semantics

35: Martin Kutrib, Hartmut Messerschmidt and Friedrich Otto: On Stateless Deterministic Restarting Automata

37: Frederic Peschanski and Joel-Alexis Bialkiewicz: Modelling and Verifying Mobile Systems using Pi-graphs

58: Reinhard Bauer, Gianlorenzo D'Angelo, Daniel Delling and Dorothea Wagner: The Shortcut Problem - Complexity and Approximation

59: philippe moser and elvira mayordomo: Polylog space compression is incomparable with Lempel-Ziv and pushdown compression

63: Stefan Porschen and Tatjana Schmidt: On Some SAT-Variants over Linear Formulas

66: Cinzia Di Giusto, Maurizio Gabbrielli and Maria Chiara Meo: Expressiveness of multiple heads in CHR

67: Beate Bollig: On the OBDD complexity of threshold functions and the variable ordering problem

68: Martin Dietzfelbinger and Ulf Schellbach: Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes

73: Henning Wunderlich: On Toda's Theorem in Structural Communication Complexity

81: Grzegorz Stachowiak: Asynchronous deterministic rendezvous on the line

87: Hannes Moser: A Problem Kernelization for Graph Packing

88: Jan Jezabek: Increasing Machine Speed in On-line Scheduling of Weighted Unit-length Jobs in Slotted Time

90: Johannes C: Schneider: Unambiguous Erasing Morphisms in Free Monoids

91: Marcella Anselmo, Natasha Jonoska and Maria Madonia: Framed versus Unframed Two-Dimensional Recognizable Languages

94: Simone Faro and Domenico Cantone: Pattern Matching with Swaps for Short Patterns in Linear Time

95: Robert Koenig, Ueli Maurer and Stefano Tessaro: Abstract Storage Devices

96: Taolue Chen, Wan Fokkink and Rob van Glabbeek: On Finite Bases for Weak Semantics: Failures versus Impossible Futures

103: Taishin Daigo and Kouichi Hirata: On Generating Maximal Acyclic Subhypergraphs with Polynomial Delay

118: Torsten Tholey: Improved Algorithms for the 2-Vertex Disjoint Paths Problem

120: Ruslans Tarasovs and Rusins Freivalds: Group Input Machine

128: Suzana Andova and Sonja Georgievska: On Compositionality, Efficiency, and Applicability of Abstraction in Probabilistic Systems

130: Klaus Reinhardt: The simple reachability problem in switch graphs

137: Konstantinos Chatzikokolakis, Sophia Knight and Prakash Panangaden: Epistemic Strategies and Games on Concurrent Processes

154: Caron Pascal, Jean-Marc Champarnaud and Ludovic Mignot: A new family of regular operators fitting with the position automaton construction

Theory and Practice of Software Services

19: Walter Dosch and Annette Stümpel: Implementing Services by Partial State Machines

92: Juan Jose Dominguez, Antonia Estero-Botaro and Inmaculada Medina-Bulo: A Framework for Mutant Genetic Generation for WS-BPEL

108: Kaiyu Wan, Mubarak Mohammad and vangalur alagar: A Formal Model of Business Application Integration from Web Services (Position Paper)

113: Ondrej Habala, Marek Paralic, Viera Rozinajova and Peter Bartalos: Semantically-aided Data-aware Service Workflow Composition

150: Dongpil Kwak, Joongsoo Lee, Dohyun Kim and Younghee Lee: User Care Preference-based Semantic Service Discovery in a Ubiquitous Environment

155: Walter Binder and Niranjan Suri: Green Computing: Energy Consumption Optimized Service Hosting

Game Theoretic Aspects of E-commerce

57: Kim Thang Nguyen: NP-hardness of pure Nash equilibrium in Scheduling and Connection Games

140: Rica Gonen and Elam Pavlov: Adaptive Incentive-Compatible Sponsored Search Auction

Techniques and Tools for Formal Verification

18: Thomas Chatain, Paul Gastin and Nathalie Sznajder: Natural specifications yield decidability for distributed synthesis of asynchronous systems

49: Sebastian Mauser, Robert Lorenz and Gabriel Juhas: Partial Order Semantics of Types of Nets

53: Johann Schuster, Jens Bachmann, Markus Siegle and Martin Riedl: An Efficient Symbolic Elimination Algorithm for the Stochastic Process Algebra tool CASPA

80: René Thiemann: From outermost termination to innermost termination

82: Nguyen Van Tang and Mizuhito Ogawa: Event-Clock Visibly Pushdown Automata

83: Frederic Vogels, Bart Jacobs and Frank Piessens: A machine checked soundness proof for an intermediate verification language

98: 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

109: Min Wan and Gianfranco Ciardo: Symbolic Reachability Analysis of Integer Timed Petri Nets

110: Min Wan and Gianfranco Ciardo: Symbolic State-space Generation of Asynchronous Systems Using Extensible Decision Diagrams

112: Ansgar Fehnker, Ralf Huuck, Bastian Schlich and Michael Tapp: Automatic Bug Detection in Microcontroller Software by Static Program Analysis

Student Research Forum

25: Tomas Potuzak and Pavel Herout: An Efficient Communication Protocol for Distributed Traffic Simulation: Introduction of the Long Step Method

31: Suzette Stoutenburg, Jugal Kalita and Shayn Hawthorne: Extracting Semantic Relationships between Wikipedia Articles

32: Suzette Stoutenburg, Jugal Kalita and Justin Gray: Acquiring Complex Cross-Ontological Relationships

38: Benedek Nagy and Peter Varga: A New Normal Form for Context-Sensitive Grammars

39: Ginta Garkaje and Rusins Freivalds: Quantum and probabilistic finite multitape automata

40: Lelde Lace, Oksana Scegulnaja-Dubrovska and Rusins Freivalds: Languages Recognizable by Quantum Finite Automata with cut-point 0

65: Anna Urbanska: Application of Graph Separators to the Efficient Division-Free Computation of Determinant

71: Pavel Loupal and Karel Richta: XML Query Evaluation Using a Lambda Calculus Based Framework

105: Romain Beauxis: A smooth probabilistic extension of concurrent constraint programming

123: Mohammad Amin Fazli, Kamyar Khodamoradi, Mehrdad Farajtabar, Marjan Ghazvininejad and Mohammad Ghodsi: The Inefficiency of Equilibria in a Network Creation Game with Packet Forwarding


15: Vera Kurkova: Model Complexity in Learning from High-Dimensional Data

27: Simone Faro and Thierry Lecroq: Efficient Pattern Matching on Binary Strings

93: 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 Arcs

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