IFIP Theoretical Computer Science 2012 (TCS 2012)

• Rajeev Alur: Streaming Transducers

Session I: Automata
• Suna Bensch, Markus Holzer, Martin Kutrib and Andreas Malcher Input-Driven Stack Automata.
• Takeshi Tsukada and Naoki Kobayashi An Intersection Type System for Deterministic Pushdown Automata.
• Gerald Luettgen and Walter Vogler Modal Interface Automata

Session II: Logics
• Hans L. Bodlaender Probabilistic Inference and Monadic Second Order Logic.
• Salvatore La Torre and Margherita Napoli A Temporal Logic for Multi-threaded Programs.
• Colin Riba A Model Theoretic Proof of Completeness of an Axiomatization of Monadic Second-Order Logic on Infinite Words.

Session III: Stochastic modelling
• Falak Sher and Joost-Pieter Katoen Compositional Abstraction Techniques for Probabilistic Automata.
• Lei Song and Jens Chr. Godskesen Broadcast Abstraction in a Stochastic Calculus for Mobile Networks.

Session IV: Formal languages
• Galina Jiraskova and Benedek Nagy On union-free and deterministic union-free languages.
• Alexander Kurz, Tomoyuki Suzuki and Emilio Tuosto A Characterisation of Languages on Infinite Alphabets with Nominal Regular Expressions.

• Jiri Wiedermann: Computability and Non-Computability Issues in Amorphous Computing

Session V: Complexity
• Michele Boreale and Michela Paolini Worst- and average-case privacy breaches in randomization mechanisms.
• Galina Jiraskova and Tomas Masopust On Properties and State Complexity of Deterministic State-Partition Automata.
• Hongyu Liang The Algorithmic Complexity of k-Domatic Partition of Graphs.

Session VI: Decidability
• Arnaud Carayol and Zoltan Esik A context-free linear ordering with an undecidable first-order theory.
• Petr Jancar, Prateek Karandikar and Philippe Schnoebelen Unidirectional channel systems can be tested.

Session VII: Algorithms
• Marijke Bodlaender, Cor Hurkens, Vincent Kusters, Frank Staals, Gerhard J. Woeginger and Hans Zantema Cinderella versus the wicked Stepmother.
• Vangelis Paschos and Federico Della Croce Efficient algorithms for the max k-vertex cover problem.

• Yuri Gurevich: Foundational Analyses of Computation

Session VIII: Semantics I
• Fabio Gadducci, Giacoma Monreale and Ugo Montanari A Modular LTS for Open Reactive Systems.
• Bas Luttik Unique Parallel Decomposition in Branching and Weak Bisimulation Semantics.
• Yuxin Deng and Yuan Feng Open Bisimulation for Quantum Processes.

Session IX: Verification
• Philipp Kuefner, Uwe Nestmann and Christina Rickmann Formal Verification of Distributed Algorithms.
• Virgile Mogbil and Emmanuel Beffara Proofs as executions.
• Davide Ancona and Giovanni Lagorio Static single information form for abstract compilation.

Session X: Semantics II
• Tomasz Brengos Weak bisimulations for coalgebras over ordered functors.
• Steffen Van Bakel and Maria Grazia Vigliotti An output-based semantics of Lambda-mu with explicit substitution in the pi-calculus.