This volume contains the contributed papers selected for presentation at the Doctoral Student Research Forum at SOFSEM 2020, the 46th International Conference on Current Trends in Theory and Practice of Computer Science, which was held during January 20-23, 2020, in Limassol, Cyprus. SOFSEM (originally SOFtware SEMinar) is an annual international winter conference devoted to the theory and practice of computer science. Its aim is to present the latest developments in research for professionals from academia and industry working in leading areas of computer science. While being a well-established and fully international conference, SOFSEM also maintains the best of its original Winter School aspects, such as a high number of invited talks, in-depth coverage of selected research areas, and ample opportunity to discuss and exchange new ideas. SOFSEM 2020 is organized around the following four tracks: - Foundations of Computer Science (chair: Christos Kapoutsis), - Foundations of Data Science and Engineering (chair: Herodotos Herodotou), - Foundations of Software Engineering (chair: Alexander Chatzigeorgiou), and - Foundations of Algorithmic Computational Biology (chairs: Ricardo Dondi and Florian Sikora). Notably, the fourth track of the above takes place for the first time in the framework of SOFSEM and it is expected to be continued over the next years. With these tracks, SOFSEM 2020 covered the latest advances in both theoretical and applied research in leading areas of computer science. An integral part of SOFSEM 2020 is the traditional Doctoral Student Research Forum (chair: Theodoros Tzouramanis) organized with the aim of giving students feedback on both the originality of their scientific results and on their work in progress. The papers presented at the Student Research Forum are available at the CEUR website (http://ceur-ws.org). The SOFSEM 2020 Program Committee (PC) consisted of 95 international experts from 35 countries, representing the track areas with outstanding expertise. Another 72 external reviewers contributed as well. The committee undertook the task of assembling a scientific program for the SOFSEM audience by selecting from 125 submissions from 40 countries entered in the EasyChair system in response to the call for papers. The submissions were carefully reviewed with 2.9 reviews/paper, and thoroughly discussed. Following strict criteria of quality and originality, 40 papers were accepted for presentation as regular research papers, as well as 17 papers for presentation as short papers. These 57 papers were contributed by authors from 26 countries. Thus, the acceptance ratio for regular papers was 32%, plus another 14% for short papers. Additionally, based on the recommendation of the chair of the Student Research Forum, 11 papers were accepted for presentation in the Student Research Forum.
I
As editors of these proceedings, we are grateful to everyone who contributed to the scientific program of the conference. We would like to thank the invited speakers: – Mikołaj Bojańczyk (University of Warsaw, Poland), – Ernesto Damiani (Khalifa University, UAE) – Erol Gelenbe (Polish Academy of Sciences, Poland) – Gunnar Klau (Heinrich Heine University Düsseldorf, Germany) – Elias Koutsoupias (University of Oxford, UK) for presenting their work to the audience of SOFSEM 2020. We thank all authors who submitted their papers for consideration. Many thanks are due to the PC members, and to all external referees, for their precise and detailed reviewing of the submissions. The work of the PC was carried out using the EasyChair system, and we gratefully acknowledge this contribution.
Special thanks are due to the SOFSEM Steering Committee headed by Július Štuller, for its support throughout the preparation of the conference. Finally, we want to thank Easyconferences.eu led by Petros Stratis, and the Deputy Ministry of Tourism of Cyprus for their services and support.
General Chairs
Program Committee Chairs Alexander Chatzigeorgiou Riccardo Dondi Herodotos Herodotou Christos Kapoutsis Florian Sikora University of Macedonia, Greece University of Bergamo, Italy Cyprus University of Technology, Cyprus Carnegie Mellon University in Qatar, Qatar University Paris-Dauphine, France Student Research Forum Chair
Steering Committee
Miroslaw Kutylowski Tiziana Margaria-Steffen Branislav Rovan Petr Šaloun Július Štuller (Chair) Jan van Leeuwen Program Committee
Fabio Anselmi Mukul S. Bansal Ladjel Bellatreche Sadok Ben Yahia Maria Bielikova
Hans-Joachim Böckenhauer Edouard Bonnet University of Genoa, Italy Wroclaw University of Technology, Poland University of Limerick, Ireland Comenius University, Slovakia Technical University of Ostrava, Czech Republic Academy of Sciences, Prague, Czech Republic Utrecht University, The Netherlands
Zhi-Zhong Chen Alfredo Cuzzocrea Peter Damaschke Bhaskar DasGupta Volker Diekert Martin Dietzfelbinger Johann Eder Mohammed El-Kebir Oliver Eulenstein Guillaume Fertin Pierre Fraigniaud Johann Gamper Loukas Georgiadis Pawel Gorecki Giovanna Guerrini Yo-Sub Han Theo Härder Danny Hermelin Irena Holubova Markus Holzer Kazuo Iwama Jesper Jansson
Mark Jones Tomasz Jurdzinski Iyad A. Kanj Jarkko Kari Selma Khouri Dennis Komm Christian Komusiewicz Georgia Koutrika Rastislav Kralovic Evangelos Kranakis Manuel Lafond Michael Lampis Sebastian Link Zsuzsanna Lipták Beatrice Markhoff Giancarlo Mauri Neeldhara Misra Elvira Mayordomo National University of Singapore, Singapore University of Reggio Calabria, Italy University of Paris-Est Marne-la-Vallée, CNRS, France Simon Fraser University, Canada Tokyo Denki University, Japan ICAR-CNR and University of Calabria, Italy Chalmers University, Sweden University of Illinois at Chicago, USA University of Stuttgart, Germany Technical University Ilmenau, Germany Alpen Adria University of Klagenfurt, Austria University of Illinois at Urbana-Champaign, USA Iowa State University, USA University of Nantes, France CNRS and University Paris Diderot, France Free University of Bozen-Bolzano, Italy University of Ioannina, Greece University of Warsaw, Poland University of Genova, Italy Yonsei University, South Korea University of Kaiserslautern, Germany Ben-Gurion University, Israel Charles University in Prague, Czech Republic University of Giessen, Germany Kyoto University, Japan The Hong Kong Polytechnic University, Hong Kong Utah State University, USA TU Delft, The Netherlands University of Wroclaw, Poland DePaul University, USA University of Turku, Finland ESI, Algeria ETH Zurich, Switzerland Philipps-University of Marburg, Germany Athena Research Center, Greece Comenius University, Slovakia Carleton University, Canada University of Sherbrooke, Canada University of Paris Dauphine, France The University of Auckland, New Zealand University of Verona, Italy University François Rabelais Tours, France University of Milano-Bicocca, Italy Indian Institute of Technology, India University of Zaragoza, Spain
Paolo Missier Luc Moreau Nelma Moreira Rim Moussa Alexander Okhotin Giovanni Pighizzini Nadia Pisanti Alberto Policriti Alex Popa Andrei Popescu Igor Potapov Eric Rivals Raffaella Rizzi Gunter Saake
Celine Scornavacca Shinnosuke Seki Ayumi Shinohara Ernest Teniente Olivier Teste Martin Theobald Eleftherios Tiakas Farouk Toumani Gabriel Valiente Athena Vakali Stephane Vialette
Tomoyuki Yamakami Christos Zaroliagis Meirav Zehavi Thomas Zeugmann Louxin Zhang University of Milan, Italy Newcastle University, UK King’s College London, UK University of Porto, Portugal ENI-Carthage, Tunisia St. Petersburg State University, Russia University of Milan, Italy University of Pisa, Italy University of Udine, Italy University of Bucharest, Romania Middlesex University London, UK University of Liverpool, UK University of Montpellier, CNRS, France University of Milano-Bicocca, Italy Otto-von-Guericke-University Magdeburg, Germany University of Tartu, Estonia Queen’s University, Canada Bogazici University, Turkey Otto-von-Guericke-University Magdeburg, Germany University of Palermo, Italy University of Montpellier, CNRS, France The University of Electro-Communications, Japan Tohoku University, Sendai, Japan Technical University of Catalonia, Spain University of Toulouse, France University of Luxemburg, Luxembourg Aristotle University of Thessaloniki, Greece Blaise Pascal University, Clermont-Ferrand, France Technical University of Catalonia, Spain Aristotle University of Thessaloniki, Greece University Paris-Est Marne-la-Vallée, CNRS, France University of Amsterdam, The Netherlands University of Twente, The Netherlands University of Ioannina, Greece University Paris-Est Marne-la-Vallée, CNRS, France University of Latvia, Latvia University of Fukui, Japan CTI and University of Patras, Greece Ben-Gurion University, Israel Hokkaido University, Japan National University of Singapore, Singapore Additional Reviewers
Marcella Anselmo Elvira-Maria Arvanitou Christel Baier Luca Bernardinello Nicolas Bonichon Sabine Broda Elisabet Burjons Cezar Campeanu Costanza Catalano Michele Chiari Sarah Christensen Ferdinando Cicalese Maxime Crochemore Federico Dassereto Gianluca De Marco Holger Dell Konstantinos Demertzis Emilio Di Giacomo Mike Domaratzki Riccardo Dondi Gabriele Fici Johannes Fischer Marco Franceschetti Fabian Frei Janosch Fuchs Esther Galbrun Paweł Garncarek Paweł Gawrychowski Konstantinos Giannis Szymon Grabowski Massimiliano Goldwurm Spyros Halkidis Artur Jeż Chris Keeler Vasilios Kelefouras Hwee Kim Jetty Kleijn Sang-Ki Ko VI
Athanasios Konstantinidis Julius Köpke Lukasz Kowalik Tomas Kulik Martin Kutrib Markus Lohrey Andreas Maletti Florin Manea Konstantinos Margaritis Wim Martens Radu-Stefan Mincu Tobias Mömke František Mráz Reino Niskanen Charis Papadopoulos Matthew Patitz Ilaria Pigazzini Luca Prigioniero Daniel Prusa Simon Puglisi Karol Rástočný Rogério Reis Traian Florin Serbanuta Florian Sikora Michiel Smid Taylor Smith Ana Paula Tomás Kostas Tsichlas Spyridon Tzimas Theodoros Tzouramanis Walter Unger Diego Valota Sergey Verlan Christina Volioti Kunihiro Wasa David Wehner Sebastian Wild Petra Wolf
Viktor Zamaraev Bit-Layers Text Encoding for Efficient Text Processing............................................ 13
Domenico Cantone, Simone Faro, and Stefano Scafiti Grammars and a Random Generator for Deterministic Chain Regular Expressions .. 49
Xinyu Chu, Ping Lu, and Haiming Chen Foundations of Software Engineering Early Prediction of Test Case Verdict with Word Embeddings vs. Bag-of-Words .... 61
Khaled Al-Sabbagh, Miroslaw Staron, Wilhelm Meding, and Miroslaw Ochodek Hybrid Analysis of BPEL Models with Grammars .................................................... 73
Erwin de Jager and Stijn de Gouw PointNet with Spin Images ......................................................................................... 85
Jakub Střelský Foundations of Data Science and Engineering An Extension of Linear-size Suffix Tries for Parameterized Strings.......................... 97 Katsuhito Nakashima, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara Data-Driven Powertrain Component Aging Prediction Using In-Vehicle Signals ... 109 Andreas Sass, Enes Esatbeyoglu, and Till Iwwerks
VII VIII Foundations of Algorithmic Computational Biology