| Saturday January 21, 2012 | |||
| 16:00 – 21:00 | SOFSEM 2012 Registration | ||
| 19:00 – 21:30 | Dinner | ||
| Sunday January 22, 2012 | |||
| 8:30 – 9:00 | SOFSEM 2012 Registration | ||
| 9:00 – 9:15 Hall A |
Georg Gottlob, General Chair: SOFSEM 2012 Opening Session | ||
| 9:15 – 10:45 Hall A |
Felipe Cucker: The Legacy of Turing in Numerical Analysis chaired by Jan van Leeuwen |
||
| 10:45 – 11:15 | Coffee Break | ||
| 11:15 – 12:45 Hall A |
Paul De Bra: A Fully Generic Approach for Realizing the Adaptive Web chaired by Mária Bieliková |
||
| 12:45 – 13:45 | Lunch Break | ||
| 15:30 – 17:00 Hall A |
Orna Kupferman: Recent Challenges and Ideas in Temporal Synthesis chaired by Stefan Katzenbeisser |
||
| 17:00 – 17:30 | Coffee Break | ||
| 17:30 – 19:00 Hall A |
Kevin Warwick: Not Another Look at the Turing Test! chaired by Gerhard Friedrich |
||
| 19:30 – 22:00 | SOFSEM 2012 Welcome Dinner at Horal Hotel | ||
| Monday January 23, 2012 | |||
| 9:00 – 10:30 Hall A |
Pavel Zezula: Multi Feature Indexing Network (MUFIN) – Similarity Search Platform for many Applications chaired by Mária Bieliková |
||
| 10:30 – 11:00 | Coffee Break | ||
| Room A | Room B | Room C | |
| 11:00 – 11:25 |
Jean-Francois Couturier, Pinar Heggernes, Pim van 't Hof and Dieter Kratsch: Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration? |
Tadeusz Kobus and Paweł T. Wojciechowski: RESTGroups for Resilient Web Services |
Lila Kari, Steffen Kopecki and Shinnosuke Seki: Iterated Hairpin Completions of Non-Crossing Words |
| 11:25 – 11:50 |
Andrzej Lingas and Dzmitry Sledneu: A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs |
Tomáš Černý, Petr Praus, Slávka Jaroměřská, Luboš Matl and Michael J. Donahoo: Towards a Smart, Self-Scaling Cooperative Web Cache |
Giovanna J. Lavado and Giovanni Pighizzini: Parikh's Theorem and Descriptional Complexity |
| 11:50 – 12:15 |
Sacha Krug: On the Approximation Ratio of the Path Matching Christofides Algorithm |
Dries Vanoverberghe, Jonathan de Halleux, Nikolai Tillmann and Frank Piessens: State Coverage: Software Validation Metrics Beyond Code Coverage |
Emmanuel Filiot and Frédéric Servais: Visibly Pushdown Transducers with Look-Ahead |
| chaired by Jiří Wiedermann | chaired by Pavel Zezula | chaired by Jan van Leeuwen | |
| 12:15 – 13:30 | Lunch Break | ||
| Room A | Room B | Room C | |
| 15:30 – 15:55 |
Peter Damaschke and Azam Sheikh Muhammad: Randomized Group Testing Both Query-Optimal and Minimal Adaptive |
Elina Kalnina, Audris Kalnins, Agris Sostaks, Edgars Celms and Janis Iraids: Tree Based Domain‐Specific Mapping Languages |
Chenyi Zhang and Jun Pang: An Algorithm for Probabilistic Alternating Simulation |
| 15:55 – 16:20 |
Klaus Jansen: A Fast Approximation Scheme for the Multiple Knapsack Problem |
Peter Kajsa and Pavol Návrat: Design Pattern Support Based on Source Code Annotations and Feature Models |
Maciej W. Gazda and Tim A. C. Willemse: Consistent Consequence for Boolean Equation Systems |
| 16:20 – 16:45 |
Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, Romeo Rizzi and Florian Sikora: Complexity Insights of the Minimum Duplication Problem |
Prabhu Shankar Kaliappan and Hartmut Koenig: On the Formalization of UML Activities for Component-Based Protocol Design Specifications |
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 |
| chaired by Branislav Rovan | chaired by Keith Jeffery | chaired by Felipe Cucker | |
| 16:45 – 17:15 | Coffee Break | ||
| Room A | Room B | Room C | |
| 17:15 – 17:40 |
Petr A. Golovach, Daniël Paulusma and Jian Song: 4-Coloring H-Free Graphs When H Is Small |
Jaroslav Škrabálek, Petr Kunc and Tomáš Pitner: Inner Architecture of a Social Networking System |
Johannes Ebbing and Peter Lohmann: Complexity of Model Checking for Modal Dependence Logic |
| 17:40 – 18:05 |
Panagiotis Cheilaris, Balázs Keszegh and Dömötör Pálvölgyi: Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs |
Martin Jačala and Jozef Tvarožek: Named Entity Disambiguation Based on Explicit Semantics |
Ondřej Čepek, Petr Kučera and Václav Vlček: Properties of SLUR Formulae |
| 18:05 – 18:30 |
Konstanty Junosza-Szaniawski and Michal Tuczyński: Counting Maximal Independent Sets in Subcubic Graphs |
Tomáš Majer and Marián Šimko: Leveraging Microblogs for Resource Ranking |
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda: Computing q-Gram Non-Overlapping Frequencies on SLP Compressed Texts |
| chaired by György Turán | chaired by Július Štuller | chaired by Giuseppe F. Italiano | |
| 19:00 – 20:00 | Dinner | ||
| Tuesday January 24, 2012 | |||
| 9:00 – 10:30 Hall A |
Roberto Navigli: Don't Take Shortcuts! Computational Lexical Semantics and the Turing Test chaired by Gerhard Friedrich |
||
| 10:30 – 11:00 | Coffee Break | ||
| Room A | Room B | Room C | |
| 11:00 – 11:25 |
Jiří Isa, Zuzana Reitermanová and Ondřej Sýkora: Cost-sensitive Classification with Unconstrained Influence Diagrams |
Martin Pettai and Peeter Laud: Securing the Future – An Information Flow Analysis of a Distributed OO Language |
|
| 11:25 – 11:50 |
Lucas Bordeaux and Joao Marques-Silva: Knowledge Compilation with Empowerment |
Nikola Beneš, Ivana Černá and Filip Štefaňák: Factorization for Component-Interaction Automata |
|
| 11:50 – 12:15 |
Jacek Mandziuk and Maciej Swiechowski: Generic Heuristic Approach to General Game Playing |
||
| chaired by Roberto Navigli | chaired by Stefan Katzenbeisser | ||
| 12:15 – 13:30 | Lunch Break | ||
| 14:00 – 18:30 | Outdoor Activities | ||
| 18:45 | Meeting Point by the Hotel Reception | ||
| 19:00 – 22:30 | SOFSEM 2012 Dinner at Olympie Restaurant | ||
| 19:00 – 21:00 | Optional Dinner at Hotel Horal | ||
| Wednesday January 25, 2012 | |||
| 9:00 – 10:30 Hall A |
Peter van Emde Boas: Turing Machines for Dummies chaired by György Turán |
||
| 10:30 – 11:00 | Coffee Break | ||
| Room A | Room B | Room C | |
| 11:00 – 11:25 |
Turlough Neary and Damien Woods: The Complexity of Small Universal Turing Machines: A Survey |
Roman Barták, Con Sheahan and Ann Sheahan: MAK€ – A System for Modeling, Optimizing, and Analyzing Production in Small and Medium Enterprises |
Jan Stolarek and Piotr Lipiński: Improving Watermark Resistance Against Removal Attacks Using Orthogonal Wavelet Adaptation |
| 11:25 – 11:50 |
Ilir Capuni and Péter Gács: A Turing Machine Resisting Isolated Bursts of Faults |
Petr Jarušek and Radek Pelánek: Modeling and Predicting Students Problem Solving Times |
Maciej Gȩbala and Mirosław Kutyłowski: Optimizing Segment Based Document Protection |
| 11:50 – 12:15 |
Jun Yan: Complete Problem for Perfect Zero-Knowledge Quantum Proof |
Iulia Nica and Franz Wotawa: The SiMoL Modeling Language for Simulation and (Re-)Configuration |
|
| chaired by Peter van Emde Boas | chaired by Gerhard Friedrich | chaired by Stefan Katzenbeisser | |
| 12:15 – 13:30 | Lunch Break | ||
| Room B + C | |||
| 14:30 – 15:00 | Student Research Forum – Poster Preparation | ||
| Room A | |||
| 15:30 – 16:30 | Student Research Forum – Presenters Oral Introduction | ||
| Room B + C | |||
|
Fuyuan Zhang, Flemming Nielson and Hanne Riis Nielson: Fixpoints vs. Moore Families Robert Ganian: Using Neighborhood Diversity to Solve Hard Problems Michalis Christou, Maxime Crochemore and Costas Iliopoulos: Quasiperiodicities in Fibonacci Strings 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 Liliana Alexandre and Jorge Coelho: A High Level Approach to Web Content Verification Piotr Miklosik, Piotr Nowicki and Jerzy Nawrocki: Web-based Bibliometric Data Warehouse Ladislav Lenc and Pavel Král: Gabor Wavelets for Automatic Face Recognition |
|||
| 16:30 – 17:30 | Student Research Forum – Posters & Refreshment | ||
| Chaired by Roman Špánek | |||
| Room A | Room B + C | ||
| 17:30 – 17:55 |
Anna Gál and Jing-Tang Jang: A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators |
Věra Kůrková: Accuracy Estimates for Surrogate Solutions of Integral Equations by Neural Networks Nils Semmelrock: A Refinement Technique for Overlapping Over-Approximations of Cooperating Systems Przemysław Błaśkiewicz, Mirosław Kutyłowski, Marcin Zawada: Secure Size Estimation for Wireless Sensor Networks |
|
| 17:55 – 18:20 |
Omer Egecioglu, Oscar H. Ibarra and Nicholas Q. Tran: Multitape NFA: Weak Synchronization of the Input Heads |
||
| 18:20 – 18:45 |
Jiří Šíma and Stanislav Žák: A Sufficent Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 |
||
| chaired by Yuri Gurevich | chaired by Roman Špánek | ||
| 19:00 – 20:00 | Dinner | ||
| Thursday January 26, 2012 | |||
| 9:00 – 10:30 Hall A |
Jiří Wiedermann: Towards Computational Models of Artificial Cognitive Systems that Can, in Principle, Pass the Turing Test chaired by Jan van Leeuwen |
||
| 10:30 – 11:00 | Coffee Break | ||
| 11:00 – 12:30 Hall A |
Yuri Gurevich: What's an Algorithm? chaired by Georg Gottlob |
||
| 12:30 – 13:30 | Lunch Break | ||
| 15:30 – 17:00 Hall A |
Krzysztof Pietrzak: Efficient Cryptography from Hard Learning Problems chaired by Gerhard Friedrich |
||
| 17:00 – 17:30 | Coffee Break | ||
| 17:30 – 19:00 Hall A |
Giuseppe F. Italiano: Strong Bridges and Strong Articulation Points of Directed Graphs chaired by Jiří Wiedermann |
||
| 19:00 – 19:15 | SOFSEM 2012 Closing Session | ||
| 19:30 – 21:00 | Dinner | ||
| Friday January 27, 2012 | |||
| 6:00 | Bus 1 leaving from the hotel | ||
| 10:00 | Bus 2 leaving from the hotel | ||