[Lecture Notes in Computer Science] SOFSEM 2020: Theory and Practice of Computer Science Volume 12011 (46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020, Proceedings)

This book constitutes the refereed proceedings of the 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, held in Limassol, Cyprus, in January 2020. The 40 full papers presented together with 17 short papers and 3 invited papers were carefully reviewed and selected from 125 submissions. They presented new research results in the theory and practice of computer science in the each sub-area of SOFSEM 2020: foundations of computer science, foundations of data science and engineering, foundations of software engineering, and foundations of algorithmic computational biology. Preface Organization Contents Invited Papers Certified Machine-Learning Models 1 Introduction 2 State of the Art 2.1 Governance of AI/ML Systems 2.2 AI Ethics by Design 2.3 Software Certification 3 Methodology 3.1 Using MAB to Test Behavior of ML Models: A Meta-Learning Process 3.2 Open Issues 3.3 Ecosystem 4 Certifying Differential Privacy 5 Conclusions References The Lost Recipes from the Four Schools of Amathus 1 The Four Schools of Amathus 2 Deciphering the Scrolls 3 Computational Genomics and Read-Based Haplotype Phasing 4 Back to Amathus References Sharing Energy for Optimal Edge Performance 1 Introduction 2 EPN and Its G-Network Representation 2.1 The G-Network Model 3 The EPN System 3.1 Cost Function, Parameters and Optimization 3.2 An Example 4 Conclusions References Foundations of Computer Science – Regular Papers A Characterization of the Context-Free Languages by Stateless Ordered Restart-Delete Automata 1 Introduction 2 The Stateless Ordered Restart-Delete Automaton 3 Swift Stl-ORD-Automata Only Accept Context-Free Languages 4 Each Context-Free Language Is Accepted by a Swift-ORD-Automaton 5 Conclusion References A Constructive Arboricity Approximation Scheme 1 Introduction 2 Paper Outline and Contributions 3 Related Work 4 Notation and Preliminaries 5 The Surplus Graph 6 Exchanging Edges on Cycles 7 Finding the Exchange Edge Fast 8 (Near-)Exact Arboricity Algorithms 9 Conclusion and Outlook References A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity 1 Introduction 2 Graph Model and Game Rules 3 Determining the Winner of a Game of EPCR 3.1 Transformation 3.2 Proof of Theorem 1 4 An Upper Bound on the Length Required to Ensure an Edge-Periodic Cycle Is Robber-Win 5 Conclusion References Approximating Shortest Connected Graph Transformation for Trees 1 Introduction 2 Preliminaries 2.1 Symmetric Difference 2.2 Basic Facts Concerning Flips 3 Upper Bound 4 Discussion on the Tightness of the Lower Bound References Approximating Weighted Completion Time for Order Scheduling with Setup Times 1 Introduction 1.1 Contribution and Results 2 Model 3 Related Work 4 The One-Time Setup Problem 4.1 Transforming One-Time Setup Solutions 5 Approximations for Constant Number of Families 5.1 Series Parallel Digraph and Lawler's Algorithm 5.2 Simple Local Search Algorithm 6 Arbitrary Number of Families 6.1 Approximation Algorithm 6.2 Lower Bound on the Approximability 7 Future Work References Bounds for the Number of Tests in Non-adaptive Randomized Algorithms for Group Testing 1 Introduction 1.1 Old and New Results 2 The RID Model 3 The RrSD Model 4 The RsSD Model 5 Random Uniform Transversal Design Model References Burning Two Worlds 1 Introduction 2 Dense Graphs 3 Graphs of Small Pathlength or Treelength 3.1 Preliminaries 3.2 Burning Graphs of Small Pathlength 3.3 Burning Graphs of Small Treelength References Faster STR-EC-LCS Computation 1 Introduction 2 Preliminaries 2.1 Strings 2.2 STR-EC-LCS 3 Dynamic Programming Solution for the STR-EC-LCS Problem 3.1 Solution for LCS by Nakatsu et al. 3.2 Solution for STR-EC-LCS by Wang et al. 3.3 Our Solution for STR-EC-LCS 4 Algorithm References Kernels of Sub-classes of Context-Free Languages 1 Introduction 2 Preliminaries 3 Uniqueness of Kernels 4 Union of Kernels 5 Intersection of Kernels 6 Untouched Questions References Minimal Unique Substrings and Minimal Absent Words in a Sliding Window 1 Introduction 2 Preliminaries 3 Combinatorial Results on MUSs in a Sliding Window 3.1 Changes to MUSs When Appending a Character to the Right 3.2 Changes to MUSs When Deleting the Leftmost Character 4 Algorithm for Computing MUSs in a Sliding Window 4.1 Updating a Suffix Tree and Three Loci in a Suffix Tree 4.2 Computing sqpi-1,j 4.3 Detecting MUSs to Be Added/Deleted 5 Combinatorial Results on MAWs in a Sliding Window 5.1 Changes to MAWs When Appending Character to the Right 5.2 Changes to MAWs When Deleting the Leftmost Character 5.3 Total Changes of MAWs When Sliding the Window on a String References On Synthesis of Specifications with Arithmetic 1 Introduction 2 Preliminaries 3 Different Levels of Nondeterminism in NLWAs 4 Synthesis 4.1 The Synthesis Game 4.2 Solving the Synthesis Game References On the Average State Complexity of Partial Derivative Transducers 1 Introduction 2 Preliminares 3 2D Expressions 4 The Analytic Combinatorics Framework 5 Average Descriptional Complexity Results 5.1 Average State Complexity of TPD for 2D-RE 5.2 Average State Complexity of TPD for Pairs of REs 6 Conclusions References On the Difference Between Finite-State and Pushdown Depth 1 Introduction 2 Preliminaries 3 Models of Computation 3.1 Finite-State Transducers 3.2 Pushdown Compressors 4 Pushdown Depth 5 Finite-State Depth 5.1 Separation from ILPDC-depth 6 Final Remarks References Online Scheduling with Machine Cost and a Quadratic Objective Function 1 Introduction 2 Preliminaries 3 Lower Bound 4 Algorithm 4.1 Description 4.2 Properties of the Relaxed Optimum and Algorithm ALG 4.3 Modifying the Two Schedules 4.4 Competitivness References Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching 1 Introduction 2 Preliminaries 3 Parallel Duel-and-Sweep Algorithm for the OPPM Problem 3.1 Pattern Preprocessing 3.2 Pattern Searching 4 Discussion References Parameterized Complexity of Synthesizing b-Bounded (m,n)-T-Systems 1 Introduction 2 Preliminaries 3 W[1]-Hardness Parameterized by m+n 3.1 The Proof of Lemma 2.[lem:if]1 3.2 The Proof of Lemma 2.[lem:onlyspsif]2 4 Conclusion References Parameterized Dynamic Variants of Red-Blue Dominating Set 1 Introduction 2 Complexity of Dynamic Red Blue Dominating Set 3 The Partial Dynamic RBDS Set Problem 4 Concluding Remarks References Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs 1 Introduction 2 Structural Graph Parameters 3 A Kernel for the Number of Edges with Rare Colors 4 Parameterization by Color Subsets 4.1 Number of Path-Frequent Colors 4.2 Number of Colors in at Least Three Conflicts 4.3 Parameter Intersections References Simple Distributed Spanners in Dense Congest Networks 1 Introduction and Related Work 1.1 On Diversity and Neighborhood Independence 1.2 Quick Review of Our Results 1.3 Related Work 2 Preliminaries 3 Spanning Graphs with Bounded Neighborhood Independence in the CONGEST Model 4 A Small Size Small Stretch Spanner in Bounded Diversity Graphs 5 Conclusion References The Order Type of Scattered Context-Free Orderings of Rank One Is Computable 1 Introduction 2 Notation 3 Limits of Languages 3.1 Limits in General 3.2 Finitely Many Limits 4 Conclusion References Up-to Techniques for Branching Bisimilarity 1 Introduction 2 Preliminaries 3 The Abstract Framework for Bisimulations 4 Branching Bisimilarity: Expansion and Context 5 Respectfulness of Up-to Context: Coalgebraic Approach 5.1 Abstract GSOS Specifications and Their Models 5.2 Respectfulness of Contextual Closure 5.3 Application to Weak Similarity 6 Conclusion and Future Work References Foundations of Data Science and Engineering – Regular Papers Crowd Detection for Drone Safe Landing Through Fully-Convolutional Neural Networks 1 Introduction 2 Related Work 3 Proposed Approach 4 Experiment 4.1 Dataset Preparation 4.2 Experimental Results 5 Conclusion References Explaining Single Predictions: A Faster Method 1 Introduction 2 Related Works 3 Choosing a Basic Explanation Method 3.1 Prediction Explanation Methods 4 Toward a More Efficient Method 4.1 Finding New Estimators of the Complete Influence 4.2 Evaluating the Two New Heuristics 5 Conclusion References Inferring Deterministic Regular Expression with Unorder 1 Introduction 2 Preliminaries 2.1 Regular Expression with Unorder 2.2 SORE, uSORE, SOA 3 Unorder-Countable Finite Automaton (uCFA) 3.1 Counter States and Update Instructions 3.2 Unorder-Countable Finite Automaton 4 Inference of uSOREs 4.1 Constructing uCFA 4.2 Counting with uCFA 4.3 Generating uSORE 5 Experiments 5.1 Generalization Abilities 5.2 Time Performance 6 Conclusion References POI Recommendation Based on Locality-Specific Seasonality and Long-Term Trends 1 Introduction 2 Background and Related Work 3 Method Proposal 3.1 Hybrid Matrix Factorization Model 3.2 Seasonality Pre-filtering and Modelling 3.3 Long-Term Trends Modelling 3.4 Geographical Post-filtering 4 Experimental Evaluation 4.1 Dataset 4.2 Experiment Setup 4.3 Results 5 Conclusion and Future Work References Selection of a Green Logical Data Warehouse Schema by Anti-monotonicity Constraint 1 Introduction 2 Background 3 The Proposed Approach: LS-Energy 4 Algorithm 5 Experimental Study 6 Conclusion References The HyperBagGraph DataEdron: An Enriched Browsing Experience of Datasets 1 Introduction 2 Related Work and Mathematical Background 2.1 Information Space Discovery 2.2 Co-occurrence Networks 2.3 Multisets and Hb-Graphs 3 Hb-Graph Framework 3.1 Enhancing Navigation 3.2 Facet Visualisation Hb-Graphs 3.3 Navigability Through Facets 3.4 The Case of Multiple References 3.5 The DataHbEdronA video demo is available on: https://www.infos-informatique.net. 4 Results, Evaluation and Conclusion 4.1 Use Case 4.2 Evaluation 5 Future Work and Conclusion References Towards the Named Entity Recognition Methods in Biomedical Field 1 Introduction 2 Related Works of Named Entity Recognition in Biomedicine 3 Natural Language Processing 4 Research Methodology and Implementation of Selected Methods 5 Results and Discussion 6 Conclusions References Vietnamese Punctuation Prediction Using Deep Neural Networks 1 Introduction 2 Punctuation Prediction as Sequence Tagging 2.1 Problem Formulation 2.2 Punctuation Prediction with Conditional Random Field 3 Neural Networks for Punctuation Prediction 3.1 Network Architectures 3.2 Training with Focal Loss 4 Datasets for Vietnamese Punctuation Prediction 5 Experiments 6 Conclusion and Future Work References Foundations of Software Engineering – Regular Papers A Light-Weight Tool for the Self-assessment of Security Compliance in Software Development – An Industry Case 1 Introduction 2 Fundamentals and Related Work 2.1 The IEC 62443-4-1 Security Standard 2.2 The Security Standard Compliance Assessment Model - S2C-AM 2.3 Other Security Assessment Approaches 3 Security Compliance Self-assessment 4 Tool Implementation for a Self-assessment of Security Compliance 5 Preliminary Evaluation at Siemens 5.1 Design 5.2 Results 6 Conclusion References A Novel Hybrid Genetic Algorithm for the Two-Stage Transportation Problem with Fixed Charges Associated to the Routes 1 Introduction 2 Definition of the Two-Stage Fixed-Charges Transportation Problem 3 Description of the Hybrid Metaheuristic Algorithm 4 Computational Results 5 Conclusions References Do People Use Naming Conventions in SQL Programming? 1 Introduction 2 Related Work 3 Setup 3.1 Reference SQL Naming Style 3.2 Database Schemas 4 Research Questions and Answers 4.1 Is the Reference Style Followed by the Schemas? 4.2 Does the Adherence of the Schemas to the Reference Style Evolve? 4.3 Threats to Validity 5 Conclusion References Employing Costs in Multiagent Systems with Timed Migration and Timed Communication 1 Introduction 2 Syntax and Operational Semantics of cTiMO 3 Translating cTiMO into Weighted Timed Automata 4 Simulating cTiMO Multiagent Systems by using Uppaal 5 Conclusion and Related Work References Maintainability of Automatic Acceptance Tests for Web Applications—A Case Study Comparing Two Approaches to Organizing Code of Test Cases 1 Introduction 2 Case Study 2.1 Case Selection 2.2 Test Suite Implementation and Maintenance 2.3 Data Collection and Analysis 3 Results and Observations 4 Threats to Validity 5 Related Work 6 Conclusions References Recommending Trips in the Archipelago of Refactorings 1 Introduction 2 Related Work 3 Refactoring Trip Advisor 3.1 Modelling Refactoring Relations 3.2 Recommending Refactoring Trips 4 Validation 4.1 Fitness for Purpose 4.2 The Developers' Opinions 5 Conclusion References String Representations of Java Objects: An Empirical Study 1 Introduction 2 Method Outline 3 ToString Definitions 4 ToString Invocations 4.1 Explicit and Implicit Calls 4.2 Calls from Other ToStrings 4.3 Other Usage Scenarios 5 ToString Contents 5.1 Language Constructs 5.2 Reusing Superclass Implementations 5.3 Schematic Implementations 5.4 Member Variables Read 6 Threats to Validity 6.1 Construct Validity 6.2 External Validity 7 Related Work 8 Conclusion and Future Work References Foundations of Algorithmic Computational Biology – Regular Papers Fast Indexes for Gapped Pattern Matching 1 Introduction 2 VLG Matching via Sorting and Scanning Suffix Array Intervals 3 Filter, Filter, Sort, Scan 4 Direct Text Checking 5 Experimental Evaluation 6 Concluding Remarks References Linearizing Genomes: Exact Methods and Local Search 1 Introduction 2 Notation and Problem Description 3 Related Work 4 Hardness Using PLS-Reduction 5 Exact Methods 5.1 Integer Linear Programming 5.2 Dynamic Programming on Tree Decompositions 6 Experiments 7 Conclusion References Scanning Phylogenetic Networks Is NP-hard 1 Introduction 2 Preliminaries 3 NP-completeness 3.1 An Adaptation of a Known NP-hardness Proof 3.2 Reducing Nice Polytomies and Leaves References The Maximum Equality-Free String Factorization Problem: Gaps vs. No Gaps 1 Introduction 2 Preliminaries 3 A Better FPT Algorithm for MaxEFF-S 4 A 12-Approximation Algorithm for OptGEFF-s 5 ILP Formulations for OptEFF-S and OptGEFF-S 6 Heuristic and Approximation Algorithms for OptEFF-S 6.1 Description of Greedy1 6.2 Description of Greedyk 6.3 Experimental Results 7 Conclusions and Open Problems References Foundations of Computer Science – Short Papers A Calculus for Language Transformations 1 Introduction 2 A Calculus for Language Transformations 2.1 Syntax of L–Tr 2.2 Operational Semantics of L–Tr 2.3 Type System of L–Tr 3 Examples 4 Related Work 5 Conclusion References Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract) 1 Introduction 2 Preliminaries 3 Algorithms for the Directed Steiner Path Cover Problem 3.1 Computing the Optimal Number of Paths 3.2 Computing the Optimal Number of Steiner Vertices 3.3 Computing an Optimal Directed Steiner Path Cover 4 Conclusions References Counting Infinitely by Oritatami Co-transcriptional Folding 1 Introduction 2 Preliminaries 3 Folding an Infinite Binary Counter References On Synchronizing Tree Automata and Their Work–Optimal Parallel Run, Usable for Parallel Tree Pattern Matching 1 Introduction 2 Basic Notions 3 Synchronizing Term and k-Local DFTA 4 Parallel Run of k-local DFTA on EREW-PRAM References On the Hardness of Energy Minimisation for Crystal Structure Prediction 1 Introduction 2 Notation and Definitions 3 NP-Hardness for an Unbounded Number of Ion Species 4 NP-Hardness for a Bounded Number of Species References Practical Implementation of a Quantum Backtracking Algorithm 1 Introduction 2 Preliminaries 3 Variable Ordering Heuristics 4 Generic Implementation 4.1 How to Implement a Predicate 4.2 How to Check a Constraint 4.3 General Structure 5 Simulation Results 6 Conclusion References Simplified Emanation Graphs: A Sparse Plane Spanner with Steiner Points 1 Introduction 2 Simplification Method 3 Experimental Comparison 4 Discussion References Simultaneous FPQ-Ordering and Hybrid Planarity Testing 1 Introduction 2 Preliminaries 3 Fixedness and 1-Fixed Constrained Planarity 3.1 A New Definition of Fixedness 3.2 1-Fixed Constrained Planarity 4 Hybrid Planarity Testing Problems References Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium 1 Introduction 1.1 Related Work 1.2 Our Results 2 Preliminaries 2.1 Competitive Diffusion Game 2.2 Graph Classes 3 The Existence of a Nash Equilibrium 3.1 Split Graph 3.2 Block Graph 3.3 Interval Graph 4 Some Other Results References Foundations of Data Science and Engineering – Short Papers Automatic Text Generation in Slovak Language 1 Introduction 2 Related Work 3 Model 4 Evaluation 4.1 Dataset 4.2 Training 4.3 Article Generation 4.4 Results 5 Conclusions and Future Work References Connecting Galaxies: Bridging the Gap Between Databases and Applications 1 Introduction 2 Models and Conversions 3 Implementation 3.1 Application Considerations 3.2 Database Considerations 4 Field Measurements 5 Related Work 6 Conclusion References GRaCe: A Relaxed Approach for Graph Query Caching 1 Introduction 2 Problem Statement and GRaCe Architecture 3 Cache Selection Algorithm 3.1 Graph Query Matching and Cache Data Structure 3.2 Selection Algorithm 4 Extending the Planner 5 Experimental Evaluation 5.1 Experimental Setup 5.2 Experimental Results 6 Concluding Remarks References Modelling of the Fake Posting Recognition in On-Line Media Using Machine Learning 1 Introduction 2 Fake Reviews Detection 2.1 Fake Reviews in Online Space 2.2 State of the Art 3 Used Machine Learning Methods 4 Models Building 4.1 Data Source 4.2 Data Preprocessing 5 Models Testing 6 Conclusions References Two-Step Memory Networks for Deep Semantic Parsing of Geometry Word Problems 1 Introduction 2 Related Work 3 Two-Step Memory Networks 3.1 Task Definition 3.2 Limitations of Existing Memory Networks 3.3 Model Formulation 4 Experiments 4.1 Unary Rule Extraction 4.2 Binary Rule Extraction 4.3 On-Demand Fact Extraction 4.4 Relation Completion 5 Conclusion and Future Work References Foundations of Software Engineering – Short Papers A Case Study on a Hybrid Approach to Assessing the Maturity of Requirements Engineering Practices in Agile Projects (REMMA) 1 Introduction 2 Case Study 3 Results 4 Conclusions References Does Live Regression Testing Help? 1 Introduction and Related Work 2 Proposed Method 2.1 Regression Test Selection Method 2.2 Test Case Prioritization Method 3 Evaluation 3.1 Experiment Design 3.2 Evaluation Results 4 Findings and Discussion References Foundations of Algorithmic Computational Biology – Short Paper Dense Subgraphs in Biological Networks 1 Introduction 1.1 Related Works 1.2 Contribution 2 Definitions 2.1 Greedy and Constrained Greedy Algorithm for Densest-Subgraph 3 A Heuristic for Top-k-Overlapping Densest Subgraphs 4 Experimental Results 5 Conclusion References Author Index