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 Snezkou, 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 former 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 Pokorny) { Cryptography, Security, and Veri cation (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 di erent countries, representing the track areas with outstanding expertise.
An integral part of SOFSEM 2015 was the traditional SOFSEM Student Research Forum (chaired by Roman Spanek), organized with the aim of presenting 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 proceedings.
In response to the call for papers, SOFSEM 2015 received 101 submissions from 31 di erent 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 Veri cation. From these, 31 submissions fell in the student category.
In response to the call for posters, SOFSEM 2015 received next 10 submissions.
After a detailed reviewing process (using the EasyChair conference system for an electronic discussion), a careful selection procedure was carried out within 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 Veri cation. 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 scienti c 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 considerable e ort 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 Spanek for his preparation and handling of the Student Research
Forum { The SOFSEM Steering Committee, chaired by Julius Stuller, for guidance and support throughout the preparation of the conference { The Organizing Committee, consisting of Martin Rimnac (Chair), Julius Stuller, Pavel Tyl, Dana Kuzelova and Milena Zeithamlova, 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 Zeithamlova, for the local arrangements of SOFSEM 2015. We thank the Institute 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 nancial support of the Czech Society for Cybernetics and Informatics.
Tiziana Margaria
Jaroslav Pokorny Jean-Jacques Quisquater Roger Wattenhofer
Roman Spanek Martin Rimnac
s s s s s s s s s s s s
PC
Malgorzata Biernacka Laura Bocchi Goetz Botterweck Samia Bouzefrane Kevin Buchin Ivana Cerna Richard Chbeir Stephanie Delaune Masaryk University, Brno, Czech Republic STFC Rutherford Appleton Laboratory,
United Kingdom Wroclaw University of Technology, Poland Utrecht University, The Netherlands Comenius University, Bratislava, Slovakia Technical University of Ostrava,
Czech Republic Institute of Computer Science, Academy of Sciences, Czech Republic
Technical University of Liberec,
Czech Republic
Lamia, Greece Montpellier, France Prague, Czech Republic Wroclaw, Poland London, United Kingdom Limerick, Ireland Paris, France Eindhoven, The Netherlands Brno, Czech Republic Anglet, France Cachan, France
Michael Felderer Leszek Gasieniec Solange Ghernaouti Inge Li Goertz Hele-Mai Haav Stephan Holzer Falk Howar Theo Harder Taisuke Izumi Hannu Jaakkola Petteri Kaski Felix Klaedkte Stanislav Krajci Rastislav Kralovic Anton n Kucera Anna-Lena Lamprecht Maryline Laurent Oscar Pastor Lopez Yannis Manolopoulos Yves Metivier Tadeusz Morzy Kaisa Nyberg Gopal Pandurangan Tadeusz Pankowski Periklis Papakonstantinou Marina Papatrianta lou Dirk Pattinson Olivier Pereira Giuseppe Persiano Dimitris Pleousakis Mila Dalla Preda Andreas Rausch Harald Sack Ina Schafer Stefan Schmid Ulrich Schmid Markus Schordan Cristina Seceleanu Martin Stanek Srikanta Tirthapura Massimo Tisi
IST, Austria Klagenfurt, Austria Wien, Austria Innsbruck, Austria Liverpool, United Kingdom Lausanne, Switzerland Lyngby, Denmark Tallinn, Estonia MIT, USA Dortmund, Germany Kaiserslautern, Germany Nagoya, Japan Pori, Finland Aalto, Finland NEC Europe, Germany Kosice, Slovakia Bratislava, Slovakia Prague, Czech Republic Potsdam, Germany Paris, France Valencia, Spain Thessaloniki, Greece Bordeaux, France Poznan, Poland Aalto, Finland Nanyang, Singapore Poznan, Poland Tsinghua, China Gothenburg, Sweden Canberra, Australia Louvain, Belgium Salerno, Italy Heraklion, Greece Verona, Italy Clausthal-Zellerfeld, Germany Potsdam, Germany Braunschweig, Germany T-Labs, Germany Vienna, Austria Livermore, USA Vasteras, Sweden Bratislava, Slovakia Ames, USA Nantes, France
Remco Veltkamp Claire Vishik Peter Vojtas Manuel Wimmer Stefan Wolf Grigory Yaroslavtsev Franco Zambonelli s s
Utrecht, The Netherlands Wake eld, USA Prague, Czech Republic Wien, Austria USI, Switzerland Philadelphia, USA
Modena, Italy
Andre Schulz Manfred Schwarz Ayumi Shinohara Jiri Srba Frank Stephan Przemyslaw Stpiczynski Maria Svorenova Li-Yang Tan Bangsheng Tang
Yushi Uno S ren Vind Imrich Vrto Kira Vyatkina Magnus Wahlstrom Kyrill Winkler Abuzer Yakaryilmaz Anastasios Zouzias
Damien Zu erey 41st SOFSEM 2015 was organized by: Institute of Computer Science, Academy of Sciences of the Czech Republic,
Prague Action M Agency, Prague
Organizing Committee s s s s s s
CSKI { Czech Society for Cybernetics and Informatics SSCS { Slovak Society for Computer Science
Institute of Computer Science, Prague,
Czech Republic Institute of Computer Science, Prague,
Czech Republic Technical University Liberec,
Czech Republic Institute of Computer Science, Prague,
Czech Republic
Action M Agency, Prague, Czech Republic
Advantages of Ultrametric Counter Automata : : : : : : : : : : : : : : : : : : : : : : : : : Valdis Adamsons, Karlis Jerins, Rihards Krislauks, Marta Lapina, Andris Pakulis, and Rusins Freivalds 1 Ultrametric Automata with One Head Versus Multihead Nondeterministic Automata : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13
Maksims Dimitrijevs and Irina Scegulnaja Fast Primality Testing for Integers That Fit into a Machine Word : : : : : : : : 20
Michal Forisek and Jakub Jancina 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 Veri cation 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
Introduction to Android 5 Security : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 103
Lukas Aron and Petr Hanacek Author Index : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 163