38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012)

Invited speakers

Foundations of Computer Science
• Felipe Cucker: The Legacy of Turing in Numerical Analysis

• Peter van Emde Boas: Turing Machines for Dummies

• Jiří Wiedermann: Towards Computational Models of Artificial Cognitive Systems that Can, in Principle, Pass the Turing Test

• Yuri Gurevich: What’s an Algorithm?

• Giuseppe F. Italiano: Strong Bridges and Strong Articulation Points of Directed Graphs

Software & Web Engineering

• Paul De Bra: A Fully Generic Approach for Realizing the Adaptive Web

• Pavel Zezula: Multi Feature Indexing Network (MUFIN) – Similarity Search Platform for many Applications

Cryptography, Security, and Verification

• Orna Kupferman: Recent Challenges and Ideas in Temporal Synthesis

• Krzysztof Pietrzak: Efficient Cryptography from Hard Learning Problems

Artificial Intelligence

• Roberto Navigli: Don’t Take Shortcuts! Computational Lexical Semantics and the Turing Test

• Kevin Warwick: Not Another Look at the Turing Test!

Regular Speakers

Foundations of Computer Science

• Klaus Jansen: A Fast Approximation Scheme for the Multiple Knapsack Problem

• Jiří Šíma and Stanislav Žák: A Sufficient Condition for Sets Hitting the Class for Read-Once Branching Programs of Width 3

• Panagiotis Cheilaris, Balázs Keszegh and Dömötör Pálvölgyi: Unique-maximum and Conflict-free Coloring for Hypergraphs and Trees

• Peter Damaschke and Azam Sheikh Muhammad: Randomized Group Testing Both Query-Optimal And Minimal Adaptive

• Johannes Ebbing and Peter Lohmann: Complexity of Model Checking for Modal Dependence Logic

• Anna Gál and Jing-Tang Jang: A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators

• Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, Romeo Rizzi and Florian Sikora: Complexity Insights of the Minimum Duplication Problem

• Jean-François Couturier, Pinar Heggernes, Pim Van 'T Hof and Dieter Kratsch: Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration

• Jun Yan: Complete Problem for Perfect Zero-Knowledge Quantum Proof

• Ilir Çapuni and Gács Péter: A Turing Machine Resisting Isolated Bursts of Faults

• Lila Kari, Steffen Kopecki and Shinnosuke Seki: Iterated Hairpin Completions of Non-crossing Words

• Emmanuel Filiot and Frédéric Servais: Visibly Pushdown Transducers with Look-Ahead

• Luca Aceto, David de Frutos-Escrig, Carlos Gregorio-Rodríguez and Anna Ingólfsdóttir: The Equational Theory of Weak Complete Simulation Semantics over BCCSP

• Keisuke Goto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda: Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts

• Turlough Neary and Damien Woods: The Complexity of Small Universal Turing Machines: A Survey

• Maciej Gazda and Tim A. C. Willemse: Consistent Consequence for Boolean Equation Systems

• Sacha Krug: On the Approximation Ratio of the Path Matching Christofides Algorithm

• Giovanna Janet Lavado and Giovanni Pighizzini: Parikh's Theorem and Descriptional Complexity

• Chenyi Zhang and Jun Pang: An Algorithm for Probabilistic Alternating Simulation

• Ondrej Čepek, Petr Kučera and Václav Vlček: Properties of SLUR Formulae

• Ömer Eǧecioǧlu, Oscar Ibarra and Nicholas Tran: Multitape NFA: Weak Synchronization of the Input Heads

• Petr Golovach, Daniel Paulusma and Jian Song: 4-Coloring H-Free Graphs When H Is Small

• Andrzej Lingas and Dzmitry Sledneu: A Combinatorial Algorithm for All-pairs Shortest Paths in Directed Vertex-weighted Graphs with Applications to Disc Graphs

• Konstanty Junosza-Szaniawski and Michał Tuczyński: Counting Maximal Independent Sets in Subcubic Graphs

Software & Web Engineering

• Peter Kajsa and Pavol Návrat: Design Pattern Support Based on Source Code Annotations and Feature Models

• Martin Jačala and Jozef Tvarožek: Named Entity Disambiguation Based on Explicit Semantics

• Tomáš Černý, Slávka Jaroměřská, Petr Praus, Luboš Matl and Michael J. Donahoo: Towards a Smart, Self-scaling Cooperative Web Cache

• Elina Kalnina, Audris Kalnins, Agris Sostaks, Edgars Celms and Janis Iraids: Tree Based Domain-Specific Mapping Languages

• Dries Vanoverberghe, Jonathan de Halleux, Nikolai Tillmann and Frank Piessens: State Coverage: Software Validation Metrics beyond Code Coverage

• Tomáš Majer and Marián Šimko: Leveraging Microblogs for Resource Ranking

• Jaroslav Škrabálek, Petr Kunc and Tomáš Pitner: Inner Architecture of a Social Networking System

• Prabhu Shankar Kaliappan and Hartmut König: On the Formalization of UML Activities for Component-Based Protocol Design Specifications

• Tadeusz Kobus and Paweł T. Wojciechowski: RESTGroups for Resilient Web Services

Cryptography, Security, and Verification

• Jan Stolarek and Piotr Lipiński: Improving Watermark Resistance Against Removal Attacks Using Orthogonal Wavelet Adaptation

• Nikola Beneš, Ivana Černá and Filip Štefaňák: Factorization for Component-Interaction Automata

• Martin Pettai and Peeter Laud: Securing the Future – An Information Flow Analysis of a Distributed OO Language

• Maciej Gȩbala and Mirosław Kutyłowski: Optimizing Segment Based Document Protection

Artificial Intelligence

• Jacek Mańdziuk and Maciej Świechowski: Generic Heuristic Approach to General Game Playing

• Jiří Iša, Zuzana Reitermanová and Ondřej Sýkora: Cost-sensitive Classification with Unconstrained Influence Diagrams Best Student Paper Award

• Petr Jarušek and Radek Pelánek: Modeling and Predicting Students Problem Solving Times

• Iulia Nica and Franz Wotawa: The SiMoL: Modeling Language for Simulation and (Re-) Configuration

• Roman Barták, Con Sheahan and Ann Sheahan: MAK€ – A System for Modeling, Optimizing, and Analyzing Production in Small and Medium Enterprises

• Lucas Bordeaux and Joao Marques-Silva: Knowledge Compilation with Empowerment

Student Research Forum

Foundations of Computer Science

• Fuyuan Zhang, Flemming Nielson and Hanne Riis Nielson: Fixpoints vs. Moore Families

• Robert Ganian: Using Neighborhood Diversity to Solve Hard Problems One of the Best Poster Award

• Michalis Christou, Maxime Crochemore and Costas Iliopoulos: Quasiperiodicities in Fibonacci Strings Best Poster Award

• Marina I. Maslennikova: Reset Complexity of Ideal Languages

• Kaspars Balodis, Anda Berina, Gleb Borovitsky, Rusins Freivalds, Ginta Garkaje, Vladimirs Kacs, Jānis Kalējs, Ilja Kucevalovs, Janis Rocans and Madars Virza: Probabilistic and Frequency Finite-State Transducers

Software & Web Engineering

• Piotr Miklosik, Piotr Nowicki and Jerzy Nawrocki: Web-based Bibliometric Data Warehouse

Artificial Intelligence

• Ladislav Lenc and Pavel Král: Gabor Wavelets for Automatic Face Recognition