SOFSEM 2021: Theory and Practice of Computer Science (Theoretical Computer Science and General Issues)

✍ Scribed by Tomáš Bureš (editor), Riccardo Dondi (editor), Johann Gamper (editor), Giovanna Guerrini (editor), Tomasz Jurdziński (editor), Claus Pahl (editor), Florian Sikora (editor), Prudence W.H. Wong (editor)

• Publisher: Springer
• Year: 2021
• Tongue: English
• Leaves: 628
• Category: Library

✦ Synopsis

This book contains the invited and contributed papers selected for presentation at SOFSEM 2021, the 47th International Conference on Current Trends in Theory and Practice of Computer Science, which was held online during January 25–28, 2021, hosted by the Free University of Bozen-Bolzano, Italy.

The 33 full and 7 short papers included in the volume were carefully reviewed and selected from 100 submissions. They were organized in topical sections on: foundations of computer science; foundations of software engineering; foundations of data science and engineering; and foundations of algorithmic computational biology. The book also contains 5 invited papers.

✦ Table of Contents

Preface
Organization
Reconstructing Phylogenetic Networks from Sequences: Where We Stand and What to Do Next (Abstract of Invited Paper)
Contents
Invited Papers
Algorithms that Access the Input via Queries
1 Introduction
2 Modeling and Analyzing a Problem with Queries
3 A Small Sample of Query Models and Results
4 Explorable Uncertainty
4.1 Parallel Queries
4.2 Untrusted Predictions
References
Towards Knowledge Exchange: State-of-the-Art and Open Problems
1 Introduction
2 Knowledge Exchange: Where Are We Now
3 Challenges and Opportunities
3.1 Mapping Generation: Input Evidence
3.2 Mapping Refinement
3.3 Knowledge Exchange
3.4 Scalability and Optimization
3.5 Application to Other Integration Problems
3.6 Evaluation
3.7 Evolution
4 Conclusions
References
Invited Talk: Resilient Distributed Algorithms
1 Introduction and Motivation
2 Graph-Based Resilient Simulation
3 Algorithms with Information-Theoretic Security
4 Algorithms Against Non-cryptographic Adversaries
5 Handling Multiple Corruptions
References
Towards Minimally Conscious Cyber-Physical Systems: A Manifesto
1 Introduction
2 Cognitive Cyber-Physical Systems
2.1 Architecture
2.2 Operation
3 Self-controlled Cognitive Cyber-Physical Systems and Minimal Machine Consciousness
3.1 Minimal Machine Consciousness
3.2 Self-controlled Cognitive Cyber-Physical Systems Are MMC
4 A Manifesto on Minimal Machine Consciousness
4.1 What Minimal Machine Consciousness Makes Possible
4.2 Design Considerations
4.3 Minimal Collective Machine Consciousness
4.4 Minimal Machine Consciousness and Industry 4.0
5 Conclusion
References
Foundations of Computer Science – Full Papers
Amnesiac Flooding: Synchronous Stateless Information Dissemination
1 Introduction
2 Notation
3 State of the Art
4 Amnesiac Flooding: Algorithm AAF
5 The Main Results
6 The Case |S|=1
6.1 The Auxiliary Graph G(v_0)
7 The Case |S|>1
7.1 Proof of Theorem 1 and Theorem 2
7.2 Proof of Theorem 3
7.3 Proof of Theorem 4
8 Conclusion and Future Work
References
Asymptotic Approximation by Regular Languages
1 Introduction
2 Densities of Formal Languages
3 Approximability and Measurability
4 REG-Measurability on Context-Free Languages
4.1 Null Context-Free Languages
4.2 Some Inherently Ambiguous Languages
4.3 K: A Language with Transcendental Density
4.4 Languages with Full REG-Gap
5 REG-Immesurability of Primitive Words
6 Conclusion and Open Problems
References
Balanced Independent and Dominating Sets on Colored Interval Graphs
1 Introduction
2 Complexity Results
2.1 f-Balanced Independent Set
2.2 f-Balanced Dominating Set
3 Algorithmic Results for the Balanced Independent Set
3.1 An FPT Algorithm Parameterized by (f,k)
3.2 An FPT Algorithm Parameterized by the Vertex Cover Number
4 Approximation Algorithms for the 1-Max-Colored Independent Set
4.1 A 2-Approximation for the 1-Max-Colored Independent Set
4.2 A PTAS for the 1-Max-Colored Independent Set
5 Conclusions
References
Bike Assisted Evacuation on a Line
1 Introduction
1.1 Model and Notation
1.2 Related Work
1.3 Outline and Results of the Paper
2 Evacuation in the Wireless (WiFi) Model
2.1 Opposite Direction with Max Speed
2.2 Opposite Direction with Optimal Speed
2.3 Slower Imitates Faster
3 Evacuation in the Face-to-Face (F2F) Model
3.1 Slower Pursues Faster
3.2 Slower Evacuation Close to Exit Without Aid
3.3 Nearest Meeting to Exit
4 Lower Bounds
5 Conclusions
References
Blocksequences of k-local Words
1 Introduction
2 Preliminaries and Initial Results
3 Neighbourless Marking Sequences and a Normal Form
4 The Case ||3
5 Conclusions
References
Complexity of Limit-Cycle Problems in Boolean Networks
1 Introduction
2 Definitions
3 State of the Art
4 Complexity of Limit-Cycle Problems
5 Conclusion
References
Concatenation Operations and Restricted Variants of Two-Dimensional Automata
1 Introduction
2 Preliminaries
3 Row and Column Concatenation
3.1 Two-Way Two-Dimensional Automata
3.2 Unary Two-Way Two-Dimensional Automata
4 Diagonal Concatenation
4.1 Two-Way Two-Dimensional Automata
4.2 Three-Way Two-Dimensional Automata
5 Conclusion
References
Distance Hedonic Games
1 Introduction
1.1 Our Contribution
1.2 Related Work
2 Model and Preliminaries
2.1 Preliminary Results: Quality of Equilibria
3 Hardness Results
3.1 Decreasing Vectors
3.2 Increasing Vectors
4 Price of Anarchy and Price of Stability
4.1 Decreasing Vectors
4.2 Increasing Vectors
5 Open Problems
References
Distributed Independent Sets in Interval and Segment Intersection Graphs
1 Introduction
1.1 Related Work
1.2 Our Contributions
2 Interval Graphs
2.1 Maximum Independent Set for Interval Graphs
2.2 Bi-interval Graphs
3 Axis-Parallel Segment Intersection Graph
3.1 The Algorithm
3.2 Analysis
4 Conclusion
References
Hierarchical b-Matching
1 Introduction
2 Preliminaries
3 Hierarchical b-Matching
3.1 A Pseudo-polynomial Algorithm
3.2 Polynomial-Time Algorithm
4 Conclusion and Open Problems
References
Improved Algorithms for Online Load Balancing
1 Introduction
2 Preliminaries
2.1 Online Load Balancing
2.2 Repeated Game with Vector Payoffs and Approachability
2.3 Online Convex Optimization
3 Main Result
3.1 Reduction to a Vector Payoff Game
3.2 Reduction to an OCO Problem
3.3 Reduction to Two OLO Problems
3.4 Putting All the Pieces Together
4 Algorithmic Details for L-norm
4.1 Computing t
4.2 Computing Subgradients gt for the -norm
5 Conclusion
References
Iterated Uniform Finite-State Transducers on Unary Languages
1 Introduction
2 Definitions and Preliminaries
3 Iterated Transduction and Unary Regular Languages
3.1 Unary Periodic Languages
3.2 Unary Finite Languages
3.3 General Unary Regular Languages
4 Beyond Constant Sweep Complexity
4.1 Characterizing Sweep Complexity by One-Way Cellular Automata Time Complexity
4.2 Reducing Sweeps on Unary Languages
4.3 Undecidability Results
References
New Bounds on the Half-Duplex Communication Complexity
1 Introduction
1.1 Background
1.2 Overview of Results
2 Half-Duplex Communication Complexity
3 Bounds for the Disjointness Function
4 Bounds on the Karchmer-Wigderson Games
5 Non-deterministic Half-Duplex Complexity
6 Open Problems
References
Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
1 Introduction
2 Basics
3 Fibonacci-Plus Words Have = (logn)
3.1 Bottom Part
3.2 Middle Part
3.3 Top Part
3.4 Putting It All Together
4 Standard-Plus Words Have = O(logn)
5 Conclusion and Outlook
References
On the Redundancy of D-Ary Fano Codes
1 Introduction
2 D-ary Fano Codes with Nice Aggregations
3 Nice Aggregations in Time O(Dlogn)
3.1 The Proof of Theorem 1
4 Final Remarks
References
On the Terminal Connection Problem
1 Introduction
2 Strongly Chordal Graphs
3 Cographs
4 Bounded Maximum Degree
4.1 Fixed Number of Linkers
4.2 Fixed Number of Routers
5 Concluding Remarks
References
Parameterized Complexity of d-Hitting Set with Quotas
1 Introduction
2 Preliminaries
3 Multi d-Hitting Set
4 Multi Feedback Vertex Set in Tournaments
5 Conclusion
References
Parameterizing Role Coloring on Forests
1 Introduction
2 Preliminaries
3 XP Algorithm for (n-k)-Role Coloring graphs
4 FPT Algorithm for (n-k)-Role Coloring Trees
4.1 Finding Degree Preserving Occurrence of F
5 Conclusions
References
The Balanced Satisfactory Partition Problem
1 Introduction
2 FPT Algorithm Parameterized by Neighbourhood Diversity
3 Hardness of Balanced Satisfactory Partition Parameterized by Treewidth
4 Conclusion
References
The Multiple Traveling Salesman Problem on Spiders
1 Introduction
2 Definitions and Basic Results
3 Canonical Solutions
4 PTAS for a Fixed Number m of Salespersons
4.1 The Algorithm
4.2 Complexity
4.3 Correctness
References
Tightness of Sensitivity and Proximity Bounds for Integer Linear Programs
1 Introduction
2 Sensitivity of ILPs
2.1 Sensitivity of General ILPs
2.2 Sensitivity of the Bin Packing ILP
3 Proximity of ILPs
3.1 Proximity of General ILPs
3.2 Proximity of the Bin Packing ILP
References
Using the Metro-Map Metaphor for Drawing Hypergraphs
1 Introduction
2 Complexity
3 Algorithms
4 Discussion
References
Weighted Microscopic Image Reconstruction
1 Introduction
2 Solving Weighted Minimum Surgical Probing
3 Number of Surgical Probes Depending on w
3.1 Negative Weights and the Laplacian Matrix
3.2 Positive Weights and the Signless Laplacian
4 Exclusive Probes vs Inclusive Probes
5 Future Directions
References
Foundations of Computer Science – Short Papers
A Normal Sequence Compressed by PPM But Not by Lempel-Ziv 78
1 Introduction
2 Preliminaries
3 Description of the PPM Algorithms
3.1 PPMk
3.2 PPM
3.3 Arithmetic Encoding
4 An Analysis of PPM*
4.1 de Bruijn Strings
4.2 Construction and Properties of S
4.3 Main Result
4.4 Comparison with PPMk
4.5 Comparison with Lempel-Ziv 78
5 Remarks
References
Clusters of Repetition Roots: Single Chains
1 Introduction
2 Clusters of Repetition Roots
3 Bound for Single Chains
References
Drawing Two Posets
1 Introduction
2 Preliminaries
3 Combinatorial View of Windrose Planarity
4 From xy-Drawings to Windrose Drawings
4.1 Simplifying Windrose Planar Embeddings
4.2 Special Windrose Planar Embeddings
5 An xy-Planarity Testing Algorithm
5.1 Finding a Windrose Planar Derived Graph
5.2 Correctness
6 Conclusion
References
Fair Division Is Hard Even for Amicable Agents
1 Introduction
2 Preliminaries
3 Hardness for Instances of Constant Degeneracy
4 Concluding Remarks
References
The Complexity of Flow Expansion and Electrical Flow Expansion
1 Introduction
2 Problem Definition
3 Networks with Variable Production
3.1 NP-Hardness on Trees
3.2 Approximation Hardness on General Graphs
4 Networks with Fixed Production
5 Single Source, Single Sink
6 Conclusion
References
Foundations of Software Engineering – Full papers
An Infrastructure for Platform-Independent Experimentation of Software Changes
1 Introduction
2 Related Work
3 Example Experiment Description
4 Experimentation Infrastructure for Platform-Independent Experimentation
4.1 Overview
4.2 Technological Stack
5 Methodology
5.1 Ideation
5.2 Design
5.3 Execution
5.4 Analysis
5.5 Learning
6 Conclusion
7 Future Work
References
Using Process Models to Understand Security Standards
1 Introduction
2 Model Implementation of the 4–1 Standard
3 Evaluation Design
3.1 Subject Selection
3.2 Survey Instrument
3.3 Data Analysis
4 Evaluation Results
5 Conclusion
5.1 Relation to Existing Evidence
5.2 Limitations and Threats to Validity
References
Web Test Automation: Insights from the Grey Literature
1 Introduction
2 Background
3 Related Work
4 Experimental Study
4.1 Procedure
5 Results
5.1 Technical Best Practices
5.2 Business-Level Best Practices
5.3 Findings
5.4 Threats to Validity
6 Conclusions and Future Work
References
Foundations of Data Science and Engineering – Full Papers
A Pipeline for Measuring Brand Loyalty Through Social Media Mining
1 Introduction
2 Related Work
3 A Pipeline for Brand Analysis
4 Data Annotation
5 A Data Warehouse for Brand Loyalty Analysis
6 Experimental Results
6.1 Experimental Setup
6.2 Results
7 Concluding Remarks
References
Predicting Tennis Match Outcomes with Network Analysis and Machine Learning
1 Introduction
1.1 Motivation
1.2 Related Work
2 Network Modeling and Surface-Specific Score
2.1 Network of Tennis Matches
2.2 Surface-Specific Score
3 Tennis Match Representation
3.1 Player's Features
3.2 Labelling - Experimental Design
3.3 Symmetric Representation
4 Machine Learning Methods
5 Experiments
5.1 Dataset Splitting
5.2 Classical Machine Learning Models Results
5.3 SVM and SVM+ Results
5.4 Multi-Output Regression Results
6 Conclusions
6.1 Contribution
6.2 Limitations
6.3 Future Work
References
Role-Based Access Control on Graph Databases
1 Introduction
2 Related Work
3 Architecture for Access Control on Graphs
4 Model for Access Control
5 Query Rewriting
6 Query Planning
7 Query Processing
8 Experimental Study
9 Conclusion
References
Semi-automatic Column Type Inference for CSV Table Understanding
1 Introduction
2 Type System and Type Recognizers
3 Type Inference Approach
4 Visualization and Type Adjustment
5 Experimental Results
6 Related Work
7 Conclusions and Future Work
References
Foundations of Data Science and Engineering – Short Papers
Metadata Management on Data Processing in Data Lakes
1 Introduction
2 Related Work and Motivating Example
3 An Extended Metadata Model for Data Processing
3.1 Meta-model
3.2 Operations
3.3 Application
4 Exploitation of the Metadata
5 Conclusion and Future Work
References
S2CFT: A New Approach for Paper Submission Recommendation
1 Introduction
2 Methodology
2.1 1D Convolutions Neural Networks
2.2 Long Short-Term Memory
2.3 Ensemble Methods
3 Experiments
3.1 Results
4 Conclusion and Further Works
References
Foundations of Algorithmic Computational Biology – Full Papers
Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
1 Introduction
2 Definitions
3 Computational (In-)Completeness Results
4 Conclusion
References
Sorting by Multi-cut Rearrangements
1 Introduction
2 Sorting by Multi-cut Rearrangements in Strings
3 Sorting by Multi-cut Rearrangements in Permutations
4 Conclusion
References
Graphs Cannot Be Indexed in Polynomial Time for Sub-quadratic Time String Matching, Unless SETH Fails
1 Introduction
1.1 Background
1.2 Results
2 Formalizing the Technique
2.1 Linear Independent-Components Reductions
2.2 Conditional Indexing Lower Bounds
2.3 Indexing Generalized Orthogonal Vectors
3 Indexing Labeled Graphs for String Matching
References
Author Index