Preface This volume contains the papers accepted for the Student Research Forum and Poster section at the 41st Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015), which was held January 24–29, 2015, in Pec pod Sněžkou, in the Czech Republic. SOFSEM (originally SOFtware SEMinar) is devoted to leading research and fosters cooperation among researchers and professionals from academia and industry in all areas of computer science. SOFSEM started in 1974 in the for- mer Czechoslovakia as a local conference and winter school combination. The renowned invited speakers and the growing interest of the authors from abroad gradually changed SOFSEM in the mid-1990s to an international conference with proceedings published in the Springer LNCS series. SOFSEM became a well-established and fully international conference maintaining the best of its original winter school aspects, such as a higher number of invited talks and an in-depth coverage of novel research results in selected areas of computer science. SOFSEM 2015 was organized around the following four tracks: – Foundations of Computer Science (chaired by Roger Wattenhofer) – Software and Web Engineering (chaired by Tiziana Margaria) – Data, Information, and Knowledge Engineering (chaired by Jaroslav Poko- rný) – Cryptography, Security, and Verification (chaired by Jean-Jacques Quisquater) With its four tracks, SOFSEM 2015 covered the latest advances in research, both theoretical and applied, in leading areas of computer science. The SOFSEM 2015 Program Committee consisted of 69 international experts from 23 different countries, representing the track areas with outstanding expertise. An integral part of SOFSEM 2015 was the traditional SOFSEM Student Research Forum (chaired by Roman Špánek), organized with the aim of pre- senting student projects on both the theory and practice of computer science, and to give the students feedback on the originality of their results. The papers presented at the Student Research Forum were published in separate local pro- ceedings. In response to the call for papers, SOFSEM 2015 received 101 submissions from 31 different countries. The submissions were distributed in the conference tracks as follows: 59 in the Foundations of Computer Science, 11 in the Software and Web Engineering, 17 in the Data, Information, and Knowledge Engineering, and 14 in the Cryptography, Security, and Verification. From these, 31 submis- sions fell in the student category. In response to the call for posters, SOFSEM 2015 received next 10 submis- sions. After a detailed reviewing process (using the EasyChair conference system for an electronic discussion), a careful selection procedure was carried out within IV Preface each track. Following strict criteria of quality and originality, 42 papers were selected for presentation, namely: 26 in the Foundations of Computer Science, four in the Software and Web Engineering, eight in the Data, Information, and Knowledge Engineering, and four in the Cryptography, Security, and Verification. Based on the recommendation of the chair of the Student Research Forum, 12 student papers were chosen for the SOFSEM 2015 Student Research Forum. As editors of these proceedings, we are grateful to everyone who contributed to the scientific program of the conference, especially the invited speakers and all the authors of contributed papers. We also thank the authors for their prompt responses to our editorial requests. SOFSEM 2015 was the result of a consider- able effort by many people. We would like to express our special thanks to: – The members of the SOFSEM 2015 Program Committee and all external reviewers for their careful reviewing of the submissions – Roman Špánek for his preparation and handling of the Student Research Forum – The SOFSEM Steering Committee, chaired by Július Štuller, for guidance and support throughout the preparation of the conference – The Organizing Committee, consisting of Martin Řimnáč (Chair), Július Štuller, Pavel Tyl, Dana Kuželová and Milena Zeithamlová, for the generous support and preparation of all aspects of the conference – Springer’s LNCS series for its continued support of the SOFSEM conferences – CEUR WS for publishing the student research forum papers and posters online We are greatly indebted to the Action M Agency, in particular Milena Zeithamlová, for the local arrangements of SOFSEM 2015. We thank the Insti- tute of Computer Science of the Academy of Sciences of the Czech Republic in Prague, for its invaluable support of all aspects of SOFSEM 2015. Finally, we are very grateful for the financial support of the Czech Society for Cybernetics and Informatics. January 2015 Giuseppe F. Italiano Tiziana Margaria Jaroslav Pokorný Jean-Jacques Quisquater Roger Wattenhofer Roman Špánek Martin Řimnáč SOFSEM 2015 Committees V ss Steering Committee Ivana Černá Masaryk University, Brno, Czech Republic Brian Matthews STFC Rutherford Appleton Laboratory, United Kingdom Miroslaw Kutylowski Wroclaw University of Technology, Poland Jan van Leeuwen Utrecht University, The Netherlands Branislav Rovan Comenius University, Bratislava, Slovakia Petr Šaloun Technical University of Ostrava, Czech Republic Július Štuller, Chair Institute of Computer Science, Academy of Sciences, Czech Republic ss Program Committee ss PC General Chair Giuseppe F. Italiano University of Rome “Tor Vergata”, Italy ss Track Chairs Roger Wattenhofer ETH Zurich, Switzerland Tiziana Margaria-Steffen University of Limerick, Ireland Jaroslav Pokorný Charles University in Prague, Czech Republic Jean-Jacques Quisquater Catholic University of Louvain, Belgium ss Student Research Forum Chair Roman Špánek Technical University of Liberec, Czech Republic ss PC Members Elena Andreeva Leuven-Heverlee, Belgium Zohra Anagnostopoulos Lamia, Greece Zohra Bellahsène Montpellier, France Petr Berka Prague, Czech Republic Malgorzata Biernacka Wroclaw, Poland Laura Bocchi London, United Kingdom Goetz Botterweck Limerick, Ireland Samia Bouzefrane Paris, France Kevin Buchin Eindhoven, The Netherlands Ivana Černá Brno, Czech Republic Richard Chbeir Anglet, France Stéphanie Delaune Cachan, France VI SOFSEM 2015 Committees Stefan Dobrev Bratislava, Slovakia Cezara Drǎgoi IST, Austria Johann Eder Klagenfurt, Austria Uwe Egly Wien, Austria Michael Felderer Innsbruck, Austria Leszek Gasieniec Liverpool, United Kingdom Solange Ghernaouti Lausanne, Switzerland Inge Li Goertz Lyngby, Denmark Hele-Mai Haav Tallinn, Estonia Stephan Holzer MIT, USA Falk Howar Dortmund, Germany Theo Härder Kaiserslautern, Germany Taisuke Izumi Nagoya, Japan Hannu Jaakkola Pori, Finland Petteri Kaski Aalto, Finland Felix Klaedkte NEC Europe, Germany Stanislav Krajči Košice, Slovakia Rastislav Královič Bratislava, Slovakia Antonı́n Kučera Prague, Czech Republic Anna-Lena Lamprecht Potsdam, Germany Maryline Laurent Paris, France Óscar Pastor López Valencia, Spain Yannis Manolopoulos Thessaloniki, Greece Yves Métivier Bordeaux, France Tadeusz Morzy Poznan, Poland Kaisa Nyberg Aalto, Finland Gopal Pandurangan Nanyang, Singapore Tadeusz Pankowski Poznan, Poland Periklis Papakonstantinou Tsinghua, China Marina Papatriantafilou Gothenburg, Sweden Dirk Pattinson Canberra, Australia Olivier Pereira Louvain, Belgium Giuseppe Persiano Salerno, Italy Dimitris Pleousakis Heraklion, Greece Mila Dalla Preda Verona, Italy Andreas Rausch Clausthal-Zellerfeld, Germany Harald Sack Potsdam, Germany Ina Schäfer Braunschweig, Germany Stefan Schmid T-Labs, Germany Ulrich Schmid Vienna, Austria Markus Schordan Livermore, USA Cristina Seceleanu Vasteras, Sweden Martin Stanek Bratislava, Slovakia Srikanta Tirthapura Ames, USA Massimo Tisi Nantes, France SOFSEM 2015 Committees VII A Min Tjoa Wien, Austria Remco Veltkamp Utrecht, The Netherlands Claire Vishik Wakefield, USA Peter Vojtáš Prague, Czech Republic Manuel Wimmer Wien, Austria Stefan Wolf USI, Switzerland Grigory Yaroslavtsev Philadelphia, USA Franco Zambonelli Modena, Italy ss Subreviewers Aghiles Adjaz Salvatore La Torre Andris Ambainis Anissa Lamani Nikola Benes Francois Le Gal Tomas Brazdil Lvzhou Li Broňa Brejová Yuanzhi Li Witold Charatonik Vahid Liaghat Yijia, Chen Kaitai Liang Rajesh Chitnis Peter Ljunglöf Patrick Hagge Cording Daniel Lokshtanov Francesco Corman Lukasik, Ewa Anindya De Ladislav Maršı́k Kord Eickmeyer Hernan Melgratti Constantin Enea Benjamin Mensing Patryk Filipiak Oscar Morales Klaus-Tycho Förster Ehab Morsy Matthias Függer Dejan Nickovic Ariel Gabizon Petr Novotný Georgios Georgiadis Thomas Nowak Mohsen Ghaffari Jan Obdrzalek Alexander Golovnev Svetlana Obraztsova Nick Gravin Gabriel Oksa Dusan Guller Hirotaka Ono Abel Gómez Jan Otop Christoph Haase Radha K.R. Pallavali Petr Hlineny Katarzyna Paluch Fatiha Houacine Debmalya Panigrahi Bart M.P. Jansen Panagiotis Papadakos Artur Jeż Dana Pardubska Christian Kissig Martin Perner Kim-Manuel Klein Oleg Prokopyev Haridimos Kondylakis Jibran Rashid Matthias Kowal Vojtech Rehak Kyriakos Kritikos Saket Saurabh Julius Köpke A.C. Cem Say Alceste Scalas VIII Organization Randolf Schaerfig Alceste Scalas André Schulz Yushi Uno Manfred Schwarz Søren Vind Ayumi Shinohara Imrich Vrto Jiri Srba Kira Vyatkina Frank Stephan Magnus Wahlström Przemyslaw Stpiczyński Kyrill Winkler Mária Svoreňová Abuzer Yakaryilmaz Li-Yang Tan Anastasios Zouzias Bangsheng Tang Damien Zufferey ss Organization 41st SOFSEM 2015 was organized by: Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague Action M Agency, Prague ss Organizing Committee Martin Řimnáč, Chair Institute of Computer Science, Prague, Czech Republic Július Štuller Institute of Computer Science, Prague, Czech Republic Pavel Tyl Technical University Liberec, Czech Republic Dana Kuželová Institute of Computer Science, Prague, Czech Republic Milena Zeithamlová Action M Agency, Prague, Czech Republic ss Supported by ČSKI – Czech Society for Cybernetics and Informatics SSCS – Slovak Society for Computer Science Table of Contents STUDENT PAPERS Foundations of Computer Science Advantages of Ultrametric Counter Automata . . . . . . . . . . . . . . . . . . . . . . . . . 1 Valdis Ādamsons, Kārlis Jēriņš, Rihards Krišlauks, Marta Lapiņa, Andris Pakulis, and Rūsiņš Freivalds Ultrametric Automata with One Head Versus Multihead Nondeterministic Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Maksims Dimitrijevs and Irina Ščeguļnaja Fast Primality Testing for Integers That Fit into a Machine Word . . . . . . . . 20 Michal Forišek and Jakub Jančina A Fixed-Parameter Algorithm for Max Edge Domination . . . . . . . . . . . . . . . 31 Tesshu Hanaka and Hirotaka Ono Position Heaps for Permuted Pattern Matching on Multi-Track Strings . . . 41 Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, and Ayumi Shinohara Software & Web Engineering Performance Analysis Patterns for Requirements Analysis . . . . . . . . . . . . . . . 54 Azadeh Alebrahim Cryptography, Security, and Verification An Improved Transformation between HILL and Metric Conditional Pseudoentropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Maciej Skorski Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs with Applications to Pseudoentropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Maciej Skorski Metric Pseudoentropy: Characterizations and Applications . . . . . . . . . . . . . . 90 Maciej Skorski X Table of Contents POSTERS Introduction to Android 5 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Lukáš Aron and Petr Hanáček Towards Indestructible Molecular Robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Ilir Çapuni, Anisa Halimi, and Dorjan Hitaj Experiments in Complexity of Probabilistic and Ultrametric Automata . . . 120 Kristı̄ne Cı̄pola, Andris Pakulis, and Rūsiņš Freivalds Measuring Complexity of Domain Standard Specifications using XML Schema Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 George Feuerlicht, Vladimir Kovar, David Hartman, Marek Beranek, and Pavel Bory Team Semantics and Recursive Enumerability . . . . . . . . . . . . . . . . . . . . . . . . . 132 Antti Kuusisto Superimposed Codes and Query Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 Anete Lāce, Muntis Rudzı̄tis, Ēriks Gopaks, and Rūsiņš Freivalds Frequency Pushdown Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Ilmārs Pužulis and Rūsiņš Freivalds Implementing the Aho-Corasick Automata for Phonetic Search . . . . . . . . . . 154 Ondřej Sýkora Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163